psList iterator API

[robert.desonia@…]

Upon reviewing the latest SDRS, I noticed that my implementation of
psListSetIterator, psListGetNext, and psListGetPrevious is lacking a
'iterator' integer parameter.

Since psList is defined in the SDRS as having only one iterator, I'm not sure
what this iterator is really for. Also, the current implementation of tightly
coupling the iterator to the list is not at all thread-safe.

What I suggest is changing the API so that another struct, psListIterator, is
used to iterate through the list, and that a psListIteratorAlloc function
replace psListSetIterator's functionality, i.e.,

psListIterator* psListIteratorAlloc(psList* list, int location);
void* psListGetNext(psListIterator* iter);
void* psListGetPrevious(psListIterator* iter);

psListIterator would look something like:

typedef struct
{

psList* list;
psListElem* cursor;
unsigned int cursorIndex;

}

[robert.desonia@…]

Upon further thought: if the iterator is decoupled from the list, psListAdd,
psListGet and psListRemove couldn't accept PS_LIST_PREVIOUS or PS_LIST_NEXT
without an iterator.

Another option to getting multiple iterators is to make iteration much more
fundemental to the list, i.e., use the psListElem building blocks directly as
an iterator pointer. Consider the following functionset:

psListElem* psListGet(psList* list, int location);
psListElem* psListFind(psList* list, void* data);
psListElem* psListGetPrevious(psListElem* elem); i.e., return elem->prev;
psListElem* psListGetNext(psListElem* elem); i.e., return elem->next;
psList* psListAdd(psList* list, psListElem* elem, void* data);
To add to head, psListAdd(list,NULL,data);
To add before an iter, psListAdd(list,psListGetPrevious(iter),data).
To add to tail, psListAdd(list,psListGet(list,PS_LIST_TAIL),data).
psList* psListRemove(psList* list, psListElem* elem);
To duplicate the PS_LIST_UNKNOWN of before, first use psListFind.

A third option is to just adjust the SDRS to the current implementation.

-rdd

[Paul Price]

It seems that we neglected to expand the specification of psList in the SDRS to
have multiple iterators, causing the confusion.

The specification of separate psListIterators seems fine. psListGetNext and
GetPrevious should certainly specify which iterator is of interest, and I
believe they are specified that way in the SDRS-07:

void *psListGetNext(psList *list, int iterator);
void *psListGetPrevious(psList *list, int iterator);

I suggest we implement your psListIterator idea, and change "int iterator"
everywhere to "psListIterator *iter". If you agree, I will go ahead and update
the SDRS.

[robert.desonia@…]

Per phone conversation with Price:

The suggestion of just replacing 'int iterator' with 'psListIterator* iter'
makes the use of PS_LIST_PREV and PS_LIST_NEXT for psListAdd, psListGet, and
psListRemove meaningless, as it wouldn't know which iterator to use.

The option of using psListElem* as an iterator is still my favourite right now!

It is just so clean, simple, and efficient. Since the psListElem* pointers

convey the list position very precisely, there seems no real need for
PS_LIST_PREV, PS_LIST_NEXT, and PS_LIST_UNKNOWN, either. Id further would claim
that all the enum PS_LIST_* values could be removed with the simple addition of
psListGetHead and psListGetTail functions. Just a thought.

Am I making trouble by suggesting a redesign of the API here?

-rdd

[Paul Price]

Updated the SDRS. The APIs defined are:

bool psListAdd(psList *list, int location, void *data);
bool psListAddAfter(psListIterator *iterator, void *data);
bool psListAddBefore(psListIterator *iterator, void *data);
void *psListGet(psList *list, int location);
void *psListGetNext(psListIterator *iterator);
void *psListGetPrevious(psListIterator *iterator);
bool psListRemove(psList *list, int location)
bool psListRemoveData(psList *list, void *data);

If any iterators are currently pointing at the item to be removed, the item
shall be removed and those iterators pointing at it shall be moved to the next,
and the function shall return \code{true}.