LIBCDT(3)

NAME
Cdt - container data types

SYNOPSIS
#include <cdt.h> void*; Dt_t; Dtdisc_t; Dtmethod_t; Dtlink_t; Dtstat_t; Dtuser_t; Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth); int dtclose(Dt_t* dt); void dtclear(dt); Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type); Dtmethod_t* dtmethod(Dt_t* dt, const Dtmethod_t* meth); Dt_t* dtview(Dt_t* dt, Dt_t* view); int dtcustomize(Dt_t* dt, int type, int action); int dtuserlock(Dt_t* dt, unsigned int key, int action); void* dtuserdata(Dt_t* dt, void* data, int set); int dtuserevent(Dt_t* dt, int flags, void* data); Dtmethod_t* Dtset; Dtmethod_t* Dtbag; Dtmethod_t* Dtrhset; Dtmethod_t* Dtrhbag; Dtmethod_t* Dtoset; Dtmethod_t* Dtobag; Dtmethod_t* Dtlist; Dtmethod_t* Dtstack; Dtmethod_t* Dtqueue; Dtmethod_t* Dtdeque; #define DTOFFSET(struct_s,member) #define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf) typedef void* (*Dtmake_f)(Dt_t*, void*, Dtdisc_t*); typedef void (*Dtfree_f)(Dt_t*, void*, Dtdisc_t*); typedef int (*Dtcompar_f)(Dt_t*, void*, void*, Dtdisc_t*); typedef unsigned int (*Dthash_f)(Dt_t*, void*, Dtdisc_t*); typedef void* (*Dtmemory_f)(Dt_t*, void*, size_t, Dtdisc_t*); typedef int (*Dtevent_f)(Dt_t*, int, void*, Dtdisc_t*); void* dtinsert(Dt_t* dt, void* obj); void* dtinstall(Dt_t* dt, void* obj); void* dtappend(Dt_t* dt, void* obj); void* dtdelete(Dt_t* dt, void* obj); void* dtremove(Dt_t* dt, void* obj); void* dtattach(Dt_t* dt, void* obj); void* dtdetach(Dt_t* dt, void* obj); void* dtsearch(Dt_t* dt, void* obj); void* dtmatch(Dt_t* dt, void* key); void* dtfirst(Dt_t* dt); void* dtnext(Dt_t* dt, void* obj); void* dtlast(Dt_t* dt); void* dtprev(Dt_t* dt, void* obj); void* dtatleast(Dt_t* dt, void* obj); void* dtatmost(Dt_t* dt, void* obj); int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, void*, void*), void*); void* dtstart(Dt_t* dt, void* obj); void* dtstep(Dt_t* dt, void* path); void* dtstop(Dt_t* dt, void* path); Dtlink_t* dtflatten(Dt_t* dt); Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link); void* dtobj(Dt_t* dt, Dtlink_t* link); Dtlink_t* dtextract(Dt_t* dt); Dtlink_t* dtrestore(Dt_t* dt, Dtlink_t* link); Dt_t* dtvnext(Dt_t* dt); ssize_t dtvcount(Dt_t* dt); Dt_t* dtvhere(Dt_t* dt); ssize_t dtsize(Dt_t* dt); ssize_t dtstat(Dt_t* dt, Dtstat_t* st); unsigned int dtstrhash(unsigned int h, char* str, int n);

DESCRIPTION

Cdt manages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, stack, and queue. This type is used to pass objects between Cdt and application code. This is the type of a dictionary handle. It contains a field Dt_t.user of type Dtuser_t* (see below). This defines the type of a discipline structure which define the lay-out of an object and functions to compare, hash, make, delete objects, etc. (see dtdisc()). This defines the type of a container method. This is the type of a dictionary object holder (see dtdisc()). This is the type of a structure to return dictionary statistics (see dtstat()). This is the type of a structure pointed to by Dt_t.user. If a discipline function memoryf() was defined, this structure will reside in memory allocated via memoryf. Although the structure is intended to be used by an application outside of CDT operations, the functions dtuserlock() and dtuserdata() are provided for certain common usages of the defined fields. It should be emphasized, however, that a particular application can choose to use this structure in anyway that it sees fit.
    typedef struct
    { unsigned int lock; /* for locking a shared dictionary */
        void* data; /* for application-specific data */
    } Dtuser_t; This creates a new dictionary. disc is a discipline structure to describe object format. meth specifies a manipulation method. dtopen() returns the new dictionary or NULL on error. See also the events DT_OPEN and DT_ENDOPEN below. This deletes dt and its objects. Note that dtclose() fails if dt is being viewed by some other dictionaries (see dtview()). dtclose() returns 0 on success and -1 on error. See also the events DT_CLOSE and DT_ENDCLOSE below. This deletes all objects in dt without closing dt. If disc is NULL, dtdisc() returns the current discipline. Otherwise, it changes the discipline of dt to disc. Objects may be rehashed, reordered, or removed as appropriate. type can be any bit combination of DT_SAMECMP and DT_SAMEHASH. DT_SAMECMP means that objects will compare exactly the same as before thus obviating the need for reordering or removing new duplicates. DT_SAMEHASH means that hash values of objects remain the same thus obviating the need to rehash. dtdisc() returns the previous discipline on success and NULL on error. If meth is NULL, dtmethod() returns the current method. Otherwise, it changes the storage method of dt to meth. Objects may be rehashed, reordered, or removed as appropriate. dtmethod() returns the previous method or NULL on error. A viewpath allows a search or walk starting from a dictionary to continue to another. dtview() first terminates any current view from dt to another dictionary. Then, if view is NULL, dtview returns the terminated view dictionary. If view is not NULL, a viewpath from dt to view is established. dtview() returns dt on success and NULL on error.

It is an error to have dictionaries on a viewpath with different storage methods. In addition, dictionaries on the same view path should treat objects in a consistent manner with respect to comparison or hashing. If not, undefined behaviors may result. This customizes a storage method. The type argument is composed of bits indicating different types of customization. The action argument, if positive, turns on the desired customization; else, turning it off. The return value is a bit vector telling the customization types successfully performed. Here are the types: DT_SHARE: This controls the shared or concurrent mode for a dictionary. Shared mode allows concurrent threads or processes to safely access objects in a dictionary. DT_ANNOUNCE: This requires each dictionary access operation to invoke the discipline eventf function to announce an object found or constructed by the operation before returning (See the DISCIPLINE section below). DT_OPTIMIZE: This causes the underlying method to optimize its internal data structure. For example, the splay tree underlying Dtoset would be balanced. This manipulates the lock dt->user->lock. It returns 0 on success and -1 on failure. The value of key must be non-zero. The argument action is used as follows: action < 0: Unlock dt->user.lock if it was locked with key. An error will result if dt->user->lock was locked with a different key. action == 0: Attempt to lock dt->user->lock with key if it is unlocked. An error will result if the dictionary was already locked with a different key. action > 0: Attempt to lock dt->user->lock with key. If dt->user.lock is already locked with a different key, the call will block until dt->user->lock can be locked with the given key. Note that obtaining or removing a lock with dtuserlock() is just a service provided to the application for their own use and has nothing to do with dictionary operations which may or may not employ their own locking schemes based on the semantics of the container data structures in use. This function returns the current value of dt->user->data. In addition, if set is non-zero, the value of dt->user->data will be changed to data. This function invokes the discipline event function with the event DT_ANNOUNCE|DT_USER|flags and the given data.

Storage methods are of type Dtmethod_t*. Cdt supports the following methods: Objects are ordered by comparisons. Dtoset keeps unique objects. Dtobag allows repeatable objects. Objects are unordered. Dtset keeps unique objects. Dtbag allows repeatable objects. The underlying data structure is a hash table with chaining to handle collisions. These methods are like Dtset and Dtbag but are based on a recursive hashing data structure that allows table extension without object relocation. The data structure also supports lock-free concurrent search operations for shared dictionaries and nearly lock-free insertions and deletions. Objects are kept in a list. A current object is always defined to be either the head of the list or an object resulting from a recent search or insert operation. The calls dtinsert() and dtinstall() will insert a new object in front of such a current object while the call dtappend() will append in back of it. Objects are kept in a deque. This is similar to Dtlist except that objects are always inserted at the front and appended at the tail of the list. Objects are kept in a stack, i.e., in reverse order of insertion. Thus, the last object inserted is at stack top and will be the first to be deleted. Objects are kept in a queue, i.e., in order of insertion. Thus, the first object inserted is at queue head and will be the first to be deleted.

Object format and associated management functions are defined in the type Dtdisc_t:
    typedef struct
    { ssize_t key, size;
      ssize_t link;
      Dtmake_f makef;
      Dtfree_f freef;
      Dtcompar_f comparf;
      Dthash_f hashf;
      Dtmemory_f memoryf;
      Dtevent_f eventf;
    } Dtdisc_t; Each object obj is identified by a key used for object comparison or hashing. key should be non-negative and defines an offset into obj. If size is negative, the key is a null-terminated string with starting address *(void**)((char*)obj+key). If size is zero, the key is a null-terminated string with starting address (void*)((char*)obj+key). Finally, if size is positive, the key is a byte array of length size starting at (void*)((char*)obj+key). Let obj be an object to be inserted into dt. If link is negative, an object holder of type Dtlink_t will be allocated to hold obj. Otherwise, obj should have a Dtlink_t structure embedded link bytes into it, i.e., at address (Dtlink_t*)((char*)obj+link). If makef is not NULL, dtinsert(), dtinstall() or dtappend() will call it to make a copy of obj suitable for insertion into dt. If makef is NULL, obj itself will be inserted into dt. If not NULL, freef is used to destroy data associated with obj. If not NULL, comparf is used to compare two keys. Its return value should be <0, =0, or >0 to indicate whether key1 is smaller, equal to, or larger than key2. All three values are significant for method Dtoset and Dtobag. For other methods, a zero value indicates equality and a non-zero value indicates inequality. If (*comparf)() is NULL, an internal function is used to compare the keys as defined by the Dtdisc_t.size field. If not NULL, hashf is used to compute the hash value of key. It is required that keys compared equal will also have same hash values. If hashf is NULL, an internal function is used to hash the key as defined by the Dtdisc_t.size field. If not NULL, memoryf is used to allocate and free memory. When addr is NULL, a memory segment of size size is requested. If addr is not NULL and size is zero, addr is to be freed. If addr is not NULL and size is positive, addr is to be resized to the given size. If memoryf is NULL, malloc(3) is used. If not NULL, eventf announces various events. Each event may have particular handling of the return values from eventf. But a negative return value typically means failure. Following are the events: DT_OPEN: This event is raised at the start of the process to open a new dictionary. The argument data will be a pointer to an object of type void* initialized to NULL before the call. The return value of eventf() is significant as follows: On a negative return value, dtopen() will return failure. On a zero return value, eventf() may set *(void**)data to some non-NULL value to indicate that the dictionary structure itself should be allocated along with the Dt_t.data section. Otherwise, it will be allocated separately with malloc(3). On a positive return value, the dictionary is being reconstructed based on the existing states of some previous dictionary. In this case, eventf() should set *(void**)data to point to the field Dt_t.data of the corresponding previous dictionary (see DT_CLOSE below). If the handle of the previous dictionary was created as discussed above in the case of the zero return value, it will be exactly restored. Otherwise, a new handle will be allocated with malloc(). The ability to create different dictionaries sharing the same set of objects allows for managing objects in shared and/or persistent memory. DT_ENDOPEN: This event is raised at the end of the process to open a dictionary. The return value of eventf() will be ignored. DT_CLOSE: This event is raised at the start of the process to close dictionary dt. The return value of eventf is significant as follows: On a negative return value, dtclose() will return failure. On a zero return value, all dictionary objects will be deleted and and associated memory freed. On a positive return value, allocated objects and memory will be kept intact. This means that dt->data remains intact and can be reused in some future dictionary (see DT_OPEN above). Note, however, that dt itself would still be freed if it was allocated with malloc(3). DT_ENDCLOSE: This event is raised at the end of the process to close a dictionary. The return value of eventf() will be ignored. DT_DISC: This event indicates that the discipline of dt is being changed to a new one given in (Dtdisc_t*)data. DT_METH: This event indicates that the method of dt is being changed to a new one given in (Dtmethod_t*)data. DT_HASHSIZE: This event is raised by the methods Dtset, Dtbag, Dtrhset and Dtrhbag to ask an application to suggest a size (measured in objects) for the data structure in use. This is useful, for example, to set a initial size for a hash table to reduce collisions and rehashing. On each call, *(ssize_t*)data will initially have the current size (which should be 0 on the first call). The return value of the event handling function indicates actions to be taken. If non-positive, the method will proceed with its default actions. Otherwise, the application may set *(ssize_t*)data to suggest a table size. The actual table size will be based on the absolute value of *(ssize_t*)data but may be modified to suit for the data structure in use. Further, if *(ssize_t*)data was negative, the size of the hash table will be fixed going forward. DT_ERROR: This event states an error that occurred during some operations, e.g., dtinsert() or dtinstall() failing to create a new object due to a memory allocation error. The argument (char*)data is a null-terminated string describing the problem. DT_ANNOUNCE: The event will be a combination of this bit and a bit indicating a successful operation. For example, DT_ANNOUNCE|DT_SEARCH announces that dtsearch() found the object that was searched for. The data argument points to the object itself. The bits representing operations that can cause an announcement are: DT_INSERT, DT_DELETE, DT_REMOVE, DT_SEARCH, DT_NEXT, DT_PREV, DT_FIRST, DT_LAST, DT_MATCH, DT_ATTACH, DT_DETACH, DT_APPEND, DT_INSTALL, DT_LEAST, and DT_MOST. Note that a call to dtinsert() or dtattach() may return a successfully inserted new object or a found matching object. For dtinsert(), the former case will be announced as DT_ANNOUNCE|DT_INSERT while the latter as DT_ANNOUNCE|DT_INSERT|DT_SEARCH. For dtattach(), the events will be similarly announced as DT_ANNOUNCE|DT_ATTACH and DT_ANNOUNCE|DT_ATTACH|DT_SEARCH. This macro function computes the offset of member from the start of structure struct_s. It is useful for getting the offset of a Dtlink_t embedded inside an object. This macro function initializes the discipline pointed to by disc with the given values. These functions add an object prototyped by obj into dt. See Dtdisc_t.makef for object construction. dtinsert() and dtappend() perform the same function for all methods except for Dtlist (see Dtlist for details). For Dtset, Dtrhset or Dtoset, if there is an object in dt matching obj dtinsert() and dtappend() will not insert a new object. On the other hand, dtinstall() remove such a matching object then insert the new object. On failure, dtinsert() and dtinstall() return NULL. Otherwise, the return value is either the newly inserted object or the matching object as noted. When obj is not NULL, dtdelete() removes some object matching obj while dtremove() removes obj itself if it exists. When obj is NULL, if the method is Dtstack or Dtqueue then the stack top or queue head is respectively deleted. See Dtdisc_t.freef for object destruction. dtdelete() and dtremove() return the deleted object or NULL. This function is similar to dtinsert() but obj itself will be inserted into dt even if a discipline function makef is defined. This function is similar to dtdelete() but the object to be deleted from dt will not be freed (via the discipline freef function). These functions find an object matching obj or key either from dt or from some dictionary accessible from dt via a viewpath (see dtview()). The return value is the matching object or NULL. These functions assume some object ordering (more below) and can be used to iterate over all objects. dtfirst() returns the first object in dt or NULL if the dictionary is empty. dtnext() returns the object coming after obj or NULL if there is no such object. dtlast() and dtprev() are like dtfirst() and dtnext() but work in reverse order. Objects are ordered based on the storage method in use. For Dtoset and Dtobag, objects are ordered by object comparisons. For Dtstack, objects are ordered in reverse order of insertion. For Dtqueue, objects are ordered in order of insertion. For Dtlist, objects are ordered by list position. For Dtset, Dtbag, Dtrhset and Dtrhbag, objects are ordered by some internal order defined at the time when these functions are called. In fact, both forward and reverse orders are defined to be the same for these methods. Objects in a dictionary or a viewpath of dictionaries can be walked using for(;;) loops as below:
    for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj)) or
    for(obj = dtlast(dt); obj; obj = dtprev(dt,obj)) The argument obj of dtnext() or dtprev() is treated specially for a method that allows multiple equal elements such as Dtobag or Dtbag. If it is in the dictionary, then the returned object will be respectively immediately before or after it in the implicitly defined object ordering. If it is not in the dictionary but still matching a group of objects, then the returned object will be immediately after the last or before the first of the group respectively.

dtatleast() returns the smallest object greater or equal to obj. dtatmost() returns the largest object smaller or equal to obj. In addition, if there are multiple such objects in dt (i.e., when a bag method was used), then dtatmost() returns the first instance of such an object while dtatleast() returns the last one. Both functions return NULL if the desired object does not exist. Again, object ordering depends on the storage method in use. With Dtoset and Dtobag, objects are linearly ordered by the discipline comparison function. As such, it is possible to call dtatleast() or dtatmost() on an object not in the dictionary and still get a meaningful result. Storage methods other than Dtoset and Dtobag do not have an explicit ordering so dtatmost() and dtatleast() will return NULL when there are no matching objects. This function calls (*userf)(walk,obj,data) on each object in dt and other dictionaries viewable from it. walk is the dictionary containing obj. If userf() returns a <0 value, dtwalk() terminates and returns the same value. dtwalk() returns 0 on completion. Using dtfirst()/dtnext() or dtlast()/dtprev() to walk a single dictionary can incur significant cost due to function calls. For efficient walking of a single directory (i.e., no viewpathing), dtflatten() and dtlink() can be used. Objects in dt are made into a linked list and walked as follows:
    for(link = dtflatten(dt); link; link = dtlink(dt,link) )

Note that dtflatten() returns a list of type Dtlink_t*, not void*. That is, it returns a dictionary holder pointer, not a user object pointer (although both are the same if the discipline field link is zero). The macro function dtlink() returns the dictionary holder object following link and the macro function dtobj(dt,link) returns the user object associated with link, Beware that a flattened object list is not guaranteed to maintain integrity if any dictionary operation other than dtlink() is performed (for example, this is important to watch out for if a dictionary is in DT_SHARE mode). This function starts a path for walking a dictionary. Note that such a path is restricted to dt only while disregarding all viewpath dictionaries (see dtview()). On success, a structure to be used in dtstep() for walking the path is returned. Otherwise, NULL is returned. If obj is NULL, the path starts at the same object returned by dtfirst(). If obj is not NULL, it must match some object in the dictionary dt and the path will start there. No matching object will result in error. This function ends a path and releases all memory source associated with it. This function returns the object at current position in the given path. Successive calls move forward one object at a time in the same order that dtnext() does in the example for(;;) loop above. If there is no more object in the path, dtstep() returns NULL. Below is a code fragment showing how to create and walk a path of objects. This object walking method is more restricted than the dtfirst()/dtnext() method since viewpathed dictionaries are ignored. However, it allows multiple paths to be traversed concurrently in the most efficient manner possible as supported by the underlying data structures.
    path = dtstart(dt, firstobj);
    for(obj = dtstep(dt, path); obj; obj = dtstep(dt,path))
    {
        ...
    }
    dtstop(dt, path); dtextract() extracts the list of objects from dt and makes it appear empty. dtrestore() repopulates dt with a list of objects previously obtained via dtextract(). It is important that the same discipline and method are in use at both extraction and restoration. Otherwise, undefined behaviors may result. These functions return NULL on error. This returns the dictionary that dt is viewing, if any. This returns the number of dictionaries that view dt. This returns the dictionary v viewable from dt where an object was found from the most recent search or walk operation. This function returns the number of objects stored in dt. This function reports dictionary statistics. It returns the number of objects stored in dt.

Dtstat_t contains the below fields: int meth: This returns the method used for the dictionary, e.g., DT_SET, DT_OSET, etc. ssize_t size: This has the number of objects in the dictionary. ssize_t mlev: This returns the maximum number of levels in the data structure used for object storage, i.e., the binary tree (e.g., Dtoset) or the recursive hash table based on a trie structure (e.g., Dtrhset). For a hash table with chaining (e.g., Dtset and Dtbag), it gives the length of the longest chain. ssize_t lsize[]: This gives the object counts at each level. For a hash table with chaining (e.g., Dtset and Dtbag), a level is defined as objects at that position in their chains. The reported levels is limited to less than DT_MAXSIZE. ssize_t tsize[]: For a recursive hash table using a trie structure (Dtrehash), this counts the number of sub-tables at each level. For example, tsize[0] should be 1 only for this hash table type. The reported levels is limited to less than DT_MAXSIZE. char* mesg: A summary message of some of the statistics. This function computes a new hash value from string str and seed value h. If n is positive, str is a byte array of length n; otherwise, str is a null-terminated string.

CONCURRENCY PROGRAMMING NOTES
Applications requiring concurrent accesses of a dictionary whether via separate threads or processes using shared memory should turn on shared mode for the dictionary. CDT uses locking and lockless data structures to provide safe concurrent accesses of objects. Much of this work is based on the atomic scalar operations available in libaso(3). Even though CDT only considers objects via the attributes specified in a discipline structure, practical objects will often have many more attributes germane to the needs of an application. Thus, beyond safe concurrent dictionary operations, an application must also protect objects in concurrent computations outside of CDT. In particular, both object deletion and object creation should be handled with care. The deletion case is relatively simple. No object should be destroyed as long as there is a reference to it. This guarantee is automatic when some garbage collection scheme is in place. Otherwise, some form of reference counting could be used to make sure that only objects with no reference would be deleted. An example to be given below discusses how reference counting could be done using the DT_ANNOUNCE feature of CDT to ensure correct timing for object deletion. In general, object attributes should be well-defined before they are used. The simplest way to ensure this is to completely construct an object before before inserting it into a shared dictionary. However, an application using complex objects may try to avoid unnecessary construction work as follows. First, only a partial object with minimal information needed for dictionary operations is constructed. Then, eitherdtinsert() or dtattach() is called to insert this partial object into the dictionary. If the call returns this same object, then it was properly inserted and the rest of its attributes could then be filled in. If only a matching object is returned, then the new object is simply discarded. Although this object construction strategy works well in single-threaded code, it can cause references to uninitialized data in concurrent computations because objects are accessible by concurrent code as soon as dtinsert() or dtattach() returns. A way to solve this problem is to make sure that an incomplete object is completed before allowing any dictionary operation accessing such an object to return it to the application. Both reference counting for safe objection deletion and ensuring readiness on object creation can be coordinate with CDT via the event DT_ANNOUNCE. An example of how to do this is given next. Objects are assumed to be of type Obj_t and have two fields: ready to indicate the readiness of an object and refn for reference counting. Both fields ready and refn are initialized to zero. Below are the relevant discipline functions Dtdisc_t.eventf and Dtdisc_t.freef to handle events and to free an object:
    int eventf(Dt_t* dt, int type, void* arg, Dtdisc_t* disc)
    {
        if(type & DT_ANNOUNCE)
        {
            if(!(type & DT_DELETE) )
            {
                Obj_t *obj = (Obj_t*)arg;
                if(type & ~(DT_ANNOUNCE|DT_INSERT|DT_ATTACH))
                    while(asogetchar(&obj->ready) == 0 )
                        asorelax(1);
                asoaddint(&obj->refn, 1);
            }
            return 0;
        }
        ...
    }
    void freef(Dt_t* dt, void* arg, Dtdisc_t* disc)
    {
        Obj_t *obj = (Obj_t*)arg;
        while(asogetchar(&obj->ready) == 0 )
            asorelax(1);
        while(asogetint(&obj->refn) > 0 )
            asorelax(1);
        ... destroy the object ...
    } Recall that each operation announcement is composed of DT_ANNOUNCE and some bits to indicate the operation itself. The test to exclude dtdelete() (indicated by the bit DT_DELETE) in eventf() is needed because an announcement always occurs right before the relevant CDT operation returns and, in the case of dtdelete(), the object may/will be already destroyed at that time. The while() loops in both eventf() and freef() cause the relevant operations to wait until the object is ready (i.e., all of its attributes are constructed) before proceeding. The asorelax(1) call yields control of the processor for 1 nanosecond so other processes can do their work. Note that the test for ~(DT_ANNOUNCE|DT_INSERT|DT_ATTACH) in eventf() means that the loop will execute for all CDT operations except for the dtinsert() or dtattach() call that actually inserts obj into the dictionary (more on this below). When the while loop finished, the construction of object obj is known to be completed. eventf() increases the reference count obj->refn by one before the respective operation returns obj to the calling code. On the other hand, freef() waits for the reference count to reach zero before proceeding to destroy the object. Waiting for object readiness in freef() before object destruction is necessary to avoid any issues with deleting uninitialized data. Again, it should be emphasized that reference counting is needed only for a memory management model where objects can be freed regardless of whether or not there are any references to them. Applications that use some form of garbage collection in general or for dictionary objects may ignore doing reference counting as done in this example. Next, consider a fragment of code to access objects concurrently from different threads or processes:
    if((obj = dtmatch(dt, "key_string")) != NULL)
    {
         ...process the object obj...
         asosubint(&obj->refn, 1);
         dtdelete(dt, obj);
    } The sequence of activities is as follows. First, the call dtmatch() retrieves an object obj. An announcement would be made during the call just before obj is returned causing the reference count of obj to be increased by one. After processing obj, the reference count is decreased by one using the atomic subtraction operator asosubint(). Then, dtdelete() is called to delete the object. A possible danger is that concurrent calls to dtdelete() may end up causing the same memory to be freed more than once. Fortunately, this cannot happen. CDT guarantees that, of all the concurrent calls to dtdelete() on obj, only one will get far enough to make the freef() call while others do nothing. Finally, consider a code fragment to construct and use the object obj:
    ... construct a partial object obj ...
    if((insobj = dtinsert(dt, obj)) == obj )
    {
        ... fully construct obj ...
        asocaschar(&obj->ready, 0, 1);
        ... compute based on obj...
        asosubint(&obj->refn, 1);
    }
    else
    { ... destroy the partial obj ...
        ... compute based on insobj...
        asosubint(&insobj->refn, 1);
    } After the dtinsert() call returns, all other concurrent computations invoking dictionary operations to access obj will be blocked in the eventf() function until obj->ready is set to 1 by the above asocaschar() call. As this is a concurrent computing application, the above code fragment itself can be executed in parallel with different but equivalent versions of obj. In that case, only one dtinsert() call will succeed in inserting a new object while the others will report a matching object, i.e., the one actually inserted. The announcement of the successful case is DT_ANNOUNCE|DT_INSERT while the announcement of the other cases is DT_ANNOUNCE|DT_INSERT|DT_SEARCH. The bit DT_SEARCH causes eventf() to to run the loop waiting for object completion. Thus, overall, except for the single case of a successful insertion of a new object, all other dictionary accesses that involve this object will return only when the object is ready. Note that, for simplicity, the possibility of failure was ignored in the example. In both successful outcomes of dtinsert(), the reference count of an appropriate object will be increased by one. Thus, care must be taken to reduce that reference count for the object after it is no longer needed. Else, per this example implementation, a deletion of such an object will cause an infinite loop in the discipline freef() function. It is possible to implement a delayed object destruction scheme that avoids an infinite loop waiting for the reference count to drop to zero. However, a discussion of that is beyond the scope of this document.

IMPLEMENTATION NOTES
Dtlist, Dtstack, Dtdeque and Dtqueue are based on doubly linked list. Dtoset and Dtobag are based on top-down splay trees. Dtset and Dtbag are based on hash tables with collision chains. Dtrhset and Dtrhbag are based on a recursive hashing data structure that avoids table resizing.

SEE ALSO
libaso(3), libvmalloc(3)

AUTHOR
Kiem-Phong Vo, kpv@research.att.com