psListRemove should not decrement reference

[robert.desonia@…]

The SDRS states "When elements are removed from a list with psListRemove, they
must have their reference counters decremented."

This, however, is not the case, as the return value of psListRemove returns the
element, so the reference is merely transferred back to the user.

Consider the following code:

list = psListAlloc(NULL);
...
psListAdd(list,data,PS_LIST_HEAD);
...
psFree(data);
user no longer needs it, though since it is in list, it doesn't actually go away
...
data2 = psListRemove(list,PS_LIST_HEAD); assume 'data' is still head of list

---

If I decremented the reference in psListRemove, no reference would then exist,
and psListRemove either returns a NULL or invalid pointer.

In other words, psListRemove transfers the reference from the list to the user
via the return value and no dereferencing actually occurs there.

-rdd

[eugene]

the question then becomes: should psListRemove actually return the value? is
that the natural usage of the function? it runs the risk that the programmer
calls psListRemove without an assignement and then drops the reference. having
this function return the removed value seems like a shortcut for:

value = psListGet (list, which); increments ref counter
psListRemove (list, NULL, which); decrements ref counter

in which case the return value of psListRemove would only describe the success
of failure of the operation. if we go with this, we should modify the
equivalents in psHash, psMetadata.

(also, shouldn't psListGet have the same format as psListRemove, with the data
argument as well as the which argument?)

[robert.desonia@…]

That makes sense. We can not have remove return the reference, in which case it
is logical to keep the reference decrement.

Also, it makes sense to add the search capability to psListGet as well as maybe
psListSetIterator.

The only concern that comes to mind is that that lends itself to thread-unsafe
usage; since the 'cursor' is part of the list structure, multiple threads could
cause havic when one thread positions the cursor in one call and assumes it to
be in the same position in the next call (but another thread moved it). STL
solved that by creating an 'iterator' type that is returned to the user-level so
that each thread has its own 'cursor'. That is not 100% thread safe either,
however, as elements are removed from the list, these iterators become invalid
(as they are nothing more than pointers to the nodes).

I guess a solution to the thread-safety problem is the user using a mutex on the
list. Future enhancements to psList could be an addition of a psListLock and
psListUnlock to simplify this task (An access mutex in psList would also need to
be added). This probably is valid for things like psHash too.

Above all, the behavior concerning reference counters should be consistent
between all containers in psLib, i.e., psList, psHash, psVector, and psImage (if
void* is ever supported).

-rdd

[robert.desonia@…]

Since we are talking about reference counting and psList, I thought I'd point
out that it turns out to be a bit queer in practice to have pslistAdd increment
the pointer's reference. In effect, that means that the pointer given to
psListAdd is still owned by the caller and it still needs to be psFreed. You
get code like:

list = psListAdd(list,data,PS_LIST_HEAD);
psFree(data);

every time you add something into a list and no longer need it outside the list.

It would probably be better if psListAdd didn't increment the reference counter

and if I wanted to keep the reference to data outside of the list, I'd do:

list = psListAdd(list,psMemIncrRefCounter(data),PS_LIST_HEAD);

[eugene]

I disagree with that point. The two cases seem equally likely, and it is just
as easy to occasionally write:

list = psListAdd(list,data,PS_LIST_HEAD);
psFree(data);

as:

list = psListAdd(list,psMemIncrRefCounter(data),PS_LIST_HEAD);

(which has 9 extra characters!!)

besides, I would claim that the former is clearer to the uninitiated than the
latter. but that is just my bias.

as for threads and locking, etc, i think we should keep it in mind but not put
in any real effort making things thread safe.

[robert.desonia@…]

Do you really think it is likely that one would add something to a
list/hash/etc. but continue to use it outside of the list/hash/etc. context?

Lists/etc., are very often implemented as containers in which
items/objects/references are deposited, and the container owns the item until it
is later removed from the list. I.e., the item is MOVED to the list, not
SHALLOW-COPIED to the list.

It is so easy to forget to psFree the item you just gave the list. Furthermore,
consider this example:

list = psListAdd(list,psImageAlloc(numCol,numRow,type),PS_LIST_TAIL);
...
psListFree(list,psImageFree);

That is a HUGE memory leak, but it is not real obvious why unless you are very
careful to note that the result of psImageAlloc needed to be freed after being
put in the list AND by psListFree (which seems to be counter-intuitive). You
can't just modify things with:

list =psListAdd(list,

psMemDecrRefCounter(psImageAlloc(numCol,numRow,type)),
PS_LIST_TAIL);

because the psImageAlloc result would lose all references before being added
into the list (this generates an error).

-rdd

[eugene]

i actually do think there will be many cases where things are copied rather than
moved to a list. particularly the metadata container, where you may put
something on the list and then continue to work with it (either as input or
output).

your example is an obvious error which i assumed would be addressed like:

foo = psImageAlloc(numCol,numRow,type);
list = psListAdd(list, foo, PS_LIST_TAIL);
psFree(foo);

but it does represent a danger that people will write it the way you did and
lose the reference.

the difference between these two options is the danger of memory leaking vs the
danger of referring to a dereferenced pointer. for example:

md = psMetadataAppend (md, "TIMELIST", PS_META_VECTOR, "times", timelist);
/* write out metadata structure */
psMetadataFree (md);

t = timelist[0].data.F32[50];

in this case, the programmer forgot the timelist gets derefernced after the
psMetadataFree and tried to refer to it later. In the base case, this will
cause a segfault, but in a more dangerous case the memory has been grabbed by
another function and has a valid data value. the result will be an incorrect
value for t.

I guess I am more concerned about the latter case because it can be harder to
catch. The memory manager can help track down memory leaks, but it will only
catch memory corruptions in some cases...

[robert.desonia@…]

Thanks for your consideration. Obviously, preferences differ here, but it is
obvious that you have selected the style of the functionality with due thought.

The question about if psListRemove should return the item remove, and should it
be dereferenced, still exists. I'd recommend either not returning the item or
not dereferencing it. Let me know what your team prefers.

For the Jun 15th release, I just removed the reference count decrement in
psListRemove. Doing the other option requires some time (tests would change,
etc.), so I don't think I will be able to change it before then.

-rdd

[eugene]

thanks for the input. it is clearly one of those places where there is a danger
no matter what you do. we should make sure that the user's docs for these
psListAdd-type functions clearly describes how we expect them to be used safely.
we should consider if the names sufficiently convey the behavior, or if we
should rename these type of functions. if we can come up with a more
descriptive naming, we might be able to clearly distinguish both behaviors.

as for psListRemove: for the next cycle, let's change the behavior so that it
does not return the item removed.