Re: Fast Removal of List Members

[Roger M. Burkhart]

Manor Askenazi writes:

>        Fast Removal of List Members
>        ----------------------------
> I received the following question (from Wengui Su) about some code in
> arborgames. I think the answer would be relevant to anybody using Lists.

> I think the best thing to do is to explain the idea first and then
> attempt to point out where these things are defined in the collections
> library, because I've tried to look up one coherent reference to
> this feature and I'm a bit lost myself...

Thanks for the summary of what's there and what's going on inside it.
I'll try to summarize the current status and future intent.

The ability to imbed membership information at a fixed offset inside a
collection member is used extensively by the activity library to manage the
actions of a schedule or action group.  The details of doing this have
not yet been documented for general public use, however.  Until they are,
any code which uses this feature should be regarded as subject to change
in future versions.

Note that it's wrong to speak of using an internal member slot for a
general list.  The feature is valid only for members of a set, since a
single membership slot inherently restricts the members to being contained
in a collection only once.  (For a general list, the same member can be
contained as many times as you want at different positions in the
collection.)  That's just one example of defining the finer points of this
feature that are partially reflected in documentation but not yet in the
current implementation.

A new release of collections didn't make it into Swarm 1.0.0 but is still
in progress, and will contain a final documented version of this special
optimization feature.  It'll always be a special feature for advanced use
only; specifically it breaks encapsulation of collection members so it's
not part of the pure object-oriented style recommended for Swarm
applications.

>   Note: the offsetof(Agent, listMembership) is a macro which returns the
>         offset of the listMembership block within the Agent.

The offsetof macro is part of the standard C library and is provided by any
ANSI-standard C compiler.  It returns the offset in bytes of a member within
a structure.

> How to do it in V1.0 (and beyond)
> ---------------------------------
> 
> Well, I'm not really sure how that is supposed to happen in V1.0, but
> here is what I've found...

For the time being, the implementation is the same as it's been in
previous releases, and the internal names differ from the interface
reference docs.

> In collections.h the method "setIndexFromMemberLoc:" can be found at
> the bottom of the file and is described as an 'obselete message' name.
> Indeed if you look in KeyedCollection there is a variant on this theme
> which may be relevant called "setIndexFromMember:". However, I haven't
> found any matching implementation for this message, so I'm not sure it
> really exists...
> 
> The situation is more interesting in the documentation where methods
> called 'setMemberSlot:' and 'getMemberSlot' are defined (and getMember
> Slot is even documented):
> 
> http://www.santafe.edu/projects/swarm/swarmdocs/src/collections/KeyedCltn.html
> 
> But they are not yet implemented and are not in the collections.h of the
> current release. If there is a new way to do this internal slot 'trick'
> which will work in future releases of collection _and_ in the current
> one, Roger would be the one to ask about that...

The documented message names for using internal member or key slots are
for a future version of the collections library.  For the time being, the
undocumented names you mentioned are the only ones that are present.
Future releases will replace them with new names, but the old names will
also continue to be supported for some period of transition.

-Roger