.. .fl
.... .Cs #include <cdt.h> .Ce .Ss "DICTIONARY TYPES" .Cs Void_t*; Dt_t; Dtdisc_t; Dtmethod_t; Dtlink_t; Dtstat_t; .Ce .Ss "DICTIONARY CONTROL" .Cs Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth); int dtclose(Dt_t* dt); void dtclear(dt); Dtmethod_t* dtmethod(Dt_t* dt, const Dtmethod_t* meth); Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type); Dt_t* dtview(Dt_t* dt, Dt_t* view); int dttreeset(Dt_t* dt, int minp, int balance); .Ce .Ss "STORAGE METHODS" .Cs Dtmethod_t* Dtset; Dtmethod_t* Dtbag; Dtmethod_t* Dtoset; Dtmethod_t* Dtobag; Dtmethod_t* Dtlist; Dtmethod_t* Dtstack; Dtmethod_t* Dtqueue; .Ce .Ss "DISCIPLINE" .Cs #define DTOFFSET(struct_s,member) #define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf) typedef Void_t* (*Dtmake_f)(Dt_t*, Void_t*, Dtdisc_t*); typedef void (*Dtfree_f)(Dt_t*, Void_t*, Dtdisc_t*); typedef int (*Dtcompar_f)(Dt_t*, Void_t*, Void_t*, Dtdisc_t*); typedef unsigned int (*Dthash_f)(Dt_t*, Void_t*, Dtdisc_t*); typedef Void_t* (*Dtmemory_f)(Dt_t*, Void_t*, size_t, Dtdisc_t*); typedef int (*Dtevent_f)(Dt_t*, int, Void_t*, Dtdisc_t*); .Ce .Ss "OBJECT OPERATIONS" .Cs Void_t* dtinsert(Dt_t* dt, Void_t* obj); Void_t* dtdelete(Dt_t* dt, Void_t* obj); Void_t* dtattach(Dt_t* dt, Void_t* obj); Void_t* dtdetach(Dt_t* dt, Void_t* obj); Void_t* dtsearch(Dt_t* dt, Void_t* obj); Void_t* dtmatch(Dt_t* dt, Void_t* key); Void_t* dtfirst(Dt_t* dt); Void_t* dtnext(Dt_t* dt, Void_t* obj); Void_t* dtlast(Dt_t* dt); Void_t* dtprev(Dt_t* dt, Void_t* obj); Void_t* dtfinger(Dt_t* dt); Void_t* dtrenew(Dt_t* dt, Void_t* obj); int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t*); Dtlink_t* dtflatten(Dt_t* dt); Dtlink_t* dtlink(Dt_t*, Dtlink_t* link); Void_t* dtobj(Dt_t* dt, Dtlink_t* link); Dtlink_t* dtextract(Dt_t* dt); int dtrestore(Dt_t* dt, Dtlink_t* link); #define DTTREESEARCH(Dt_t* dt, Void_t* obj, action) #define DTTREEMATCH(Dt_t* dt, Void_t* key, action) .Ce .Ss "DICTIONARY STATUS" .Cs Dt_t* dtvnext(Dt_t* dt); int dtvcount(Dt_t* dt); Dt_t* dtvhere(Dt_t* dt); int dtsize(Dt_t* dt); int dtstat(Dt_t* dt, Dtstat_t*, int all); .Ce .Ss "HASH FUNCTIONS" .Cs unsigned int dtstrhash(unsigned int h, char* str, int n); unsigned int dtcharhash(unsigned int h, unsigned char c); .Ce
Cdt manages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, stack, and queue.
.Ss "DICTIONARY TYPES"
.Ss " Void_t*" This type is used to pass objects between Cdt and application code. \f5Void_t is defined as \f5void for ANSI-C and C++ and \f5char for other compilation environments.
.Ss " Dt_t" This is the type of a dictionary handle.
.Ss " Dtdisc_t" This defines the type of a discipline structure which describes object lay-out and manipulation functions.
.Ss " Dtmethod_t" This defines the type of a container method.
.Ss " Dtlink_t" This is the type of a dictionary object holder (see \f5dtdisc().)
.Ss " Dtstat_t" This is the type of a structure to return dictionary statistics (see \f5dtstat().)
.Ss "DICTIONARY CONTROL"
.Ss " Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth)" This creates a new dictionary. \f5disc is a discipline structure to describe object format. \f5meth specifies a manipulation method. \f5dtopen() returns the new dictionary or \f5NULL on error. See also the events \f5DT_OPEN and \f5DT_ENDOPEN below.
.Ss " int dtclose(Dt_t* dt)" This deletes \f5dt and its objects. Note that \f5dtclose() fails if \f5dt is being viewed by some other dictionaries (see \f5dtview()). \f5dtclose() returns \f50 on success and \f5-1 on error. See also the events \f5DT_CLOSE and \f5DT_ENDCLOSE below.
.Ss " void dtclear(Dt_t* dt)" This deletes all objects in \f5dt without closing \f5dt.
.Ss " Dtmethod_t dtmethod(Dt_t* dt, const Dtmethod_t* meth)" If \f5meth is \f5NULL, \f5dtmethod() returns the current method. Otherwise, it changes the storage method of \f5dt to \f5meth. Object order remains the same during a method switch among \f5Dtlist, \f5Dtstack and \f5Dtqueue. Switching to and from \f5Dtset/Dtbag and \f5Dtoset/Dtobag may cause objects to be rehashed, reordered, or removed as the case requires. \f5dtmethod() returns the previous method or \f5NULL on error.
.Ss " Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type)" If \f5disc is \f5NULL, \f5dtdisc() returns the current discipline. Otherwise, it changes the discipline of \f5dt to \f5disc. Objects may be rehashed, reordered, or removed as appropriate. \f5type can be any bit combination of \f5DT_SAMECMP and \f5DT_SAMEHASH. \f5DT_SAMECMP means that objects will compare exactly the same as before thus obviating the need for reordering or removing new duplicates. \f5DT_SAMEHASH means that hash values of objects remain the same thus obviating the need to rehash. \f5dtdisc() returns the previous discipline on success and \f5NULL on error.
.Ss " Dt_t* dtview(Dt_t* dt, Dt_t* view)" A viewpath allows a search or walk starting from a dictionary to continue to another. \f5dtview() first terminates any current view from \f5dt to another dictionary. Then, if \f5view is \f5NULL, \f5dtview returns the terminated view dictionary. If \f5view is not \f5NULL, a viewpath from \f5dt to \f5view is established. \f5dtview() returns \f5dt on success and \f5NULL on error.
If two dictionaries on the same viewpath have the same values for the discipline fields \f5Dtdisc_t.link, \f5Dtdisc_t.key, \f5Dtdisc_t.size, and \f5Dtdisc_t.hashf, it is expected that key hashing will be the same. If not, undefined behaviors may result during a search or a walk.
.Ss " int dttreeset(Dt_t* dt, int minp, int balance)" This function only applies to dictionaries operated under the method \f5Dtoset which uses top-down splay trees (see below). It returns 0 on success and -1 on error. .Tp \f5minp: This parameter defines the minimum path length before a search path is adjusted. For example, \f5minp equal 0 would mean that search paths are always adjusted. If \f5minp is negative, the minimum search path is internally computed based on a function of the current dictionary size. This computed value is such that if the tree is balanced, it will never require adjusting. .Tp \f5balance: If this is non-zero, the tree will be made balanced.
.Ss "STORAGE METHODS"
Storage methods are of type \f5Dtmethod_t*. Cdt supports the following methods:
.Ss " Dtoset" .Ss " Dtobag" Objects are ordered by comparisons. \f5Dtoset keeps unique objects. \f5Dtobag allows repeatable objects.
.Ss " Dtset" .Ss " Dtbag" Objects are unordered. \f5Dtset keeps unique objects. \f5Dtbag allows repeatable objects and always keeps them together (note the effect on dictionary walking.) These methods use a hash table with chaining to manage the objects. See also the event \f5DT_HASHSIZE below on how to manage hash table resizing when objects are inserted.
.Ss " Dtlist" Objects are kept in a list. New objects are inserted either in front of current object (see \f5dtfinger()) if this is defined or at list front if there is no current object.
.Ss " Dtstack" 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.
.Ss " Dtqueue" 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.
.Ss "DISCIPLINE"
Object format and associated management functions are defined in the type \f5Dtdisc_t: .Cs typedef struct { int key, size; int link; Dtmake_f makef; Dtfree_f freef; Dtcompar_f comparf; Dthash_f hashf; Dtmemory_f memoryf; Dtevent_f eventf; } Dtdisc_t; .Ce .Ss " int key, size" Each object \f5obj is identified by a key used for object comparison or hashing. \f5key should be non-negative and defines an offset into \f5obj. If \f5size is negative, the key is a null-terminated string with starting address \f5*(Void_t**)((char*)obj+key). If \f5size is zero, the key is a null-terminated string with starting address \f5(Void_t*)((char*)obj+key). Finally, if \f5size is positive, the key is a byte array of length \f5size starting at \f5(Void_t*)((char*)obj+key).
.Ss " int link" Let \f5obj be an object to be inserted into \f5dt as discussed below. If \f5link is negative, an internally allocated object holder is used to hold \f5obj. Otherwise, \f5obj should have a \f5Dtlink_t structure embedded \f5link bytes into it, i.e., at address \f5(Dtlink_t*)((char*)obj+link).
.Ss " Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)" If \f5makef is not \f5NULL, \f5dtinsert(dt,obj) will call it to make a copy of \f5obj suitable for insertion into \f5dt. If \f5makef is \f5NULL, \f5obj itself will be inserted into \f5dt.
.Ss " void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)" If not \f5NULL, \f5freef is used to destroy data associated with \f5obj.
.Ss "int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)" If not \f5NULL, \f5comparf is used to compare two keys. Its return value should be \f5<0, \f5=0, or \f5>0 to indicate whether \f5key1 is smaller, equal to, or larger than \f5key2. All three values are significant for method \f5Dtoset and \f5Dtobag. For other methods, a zero value indicates equality and a non-zero value indicates inequality. If \f5(*comparf)() is \f5NULL, an internal function is used to compare the keys as defined by the \f5Dtdisc_t.size field.
.Ss " unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)" If not \f5NULL, \f5hashf is used to compute the hash value of \f5key. It is required that keys compared equal will also have same hash values. If \f5hashf is \f5NULL, an internal function is used to hash the key as defined by the \f5Dtdisc_t.size field.
.Ss " Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)" If not \f5NULL, \f5memoryf is used to allocate and free memory. When \f5addr is \f5NULL, a memory segment of size \f5size is requested. If \f5addr is not \f5NULL and \f5size is zero, \f5addr is to be freed. If \f5addr is not \f5NULL and \f5size is positive, \f5addr is to be resized to the given size. If \f5memoryf is \f5NULL, malloc(3) is used. When dictionaries share memory, a record of the first allocated memory segment should be kept so that it can be used to initialize other dictionaries (see below.)
.Ss " int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)" If not \f5NULL, \f5eventf announces various events. Each event may have particular handling of the return values from \f5eventf. But a negative return value typically means failure. Following are the events: .Tp \f5DT_OPEN: \f5dt is being opened. If \f5eventf returns negative, the opening process terminates with failure. If \f5eventf returns zero, the opening process proceeds normally. A positive return value indicates special treatment of memory as follows. If \f5*(Void_t**)data is set to point to some memory segment as discussed in \f5memoryf, that segment of memory is used to start the dictionary. If \f5*(Void_t**)data is not set, this indicates that \f5dtopen() should allocate the dictionary handle itself with \f5memoryf so that all memories pertained to the dictionary are allocated via this function. .Tp \f5DT_ENDOPEN: This event announces that \f5dtopen() has successfully opened a dictionary and is about to return. The \f5data argument of \f5eventf should be the new dictionary handle itself. .Tp \f5DT_CLOSE: \f5dt is about to be closed. If \f5eventf returns zero, the closing process proceeds normally. This means that all objects in the dictionary will be deleted and all associated memories freed. If \f5eventf returns a positive value, objects will not be deleted. However, the dictionary handle itself will still be deallocated unless it was allocated via \f5memoryf during \f5dtopen(). This allows shared/persistent memory dictionaries to retain the relevant memories across dictionary openings and closings. .Tp \f5DT_ENDCLOSE: This event announces that \f5dtclose() has successfully closed a dictionary and is about to return. .Tp \f5DT_DISC: The discipline of \f5dt is being changed to a new one given in \f5(Dtdisc_t*)data. .Tp \f5DT_METH: The method of \f5dt is being changed to a new one given in \f5(Dtmethod_t*)data. .Tp \f5DT_HASHSIZE: The hash table (for \f5Dtset and \f5Dtbag) is being resized. In this case, \f5*(int*)data has the current size of the table. The application can set the new table size by first changing \f5*(int*)data to the desired size, then return a positive value. The application can also fix the table size at the current value forever by setting \f5*(int*)data to a negative value, then again return a positive value. A non-positive return value from the event handling function means that Cdt will be responsible for choosing the hash table size.
.Ss "#define DTOFFSET(struct_s,member)" This macro function computes the offset of \f5member from the start of structure \f5struct_s. It is useful for getting the offset of a \f5Dtlink_t embedded inside an object.
.Ss "#define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)" This macro function initializes the discipline pointed to by \f5disc with the given values.
.Ss "OBJECT OPERATIONS"
.Ss " Void_t* dtinsert(Dt_t* dt, Void_t* obj)" This inserts an object prototyped by \f5obj into \f5dt. If there is an existing object in \f5dt matching \f5obj and the storage method is \f5Dtset or \f5Dtoset, \f5dtinsert() will simply return the matching object. Otherwise, a new object is inserted according to the method in use. See \f5Dtdisc_t.makef for object construction. \f5dtinsert() returns the new object, a matching object as noted, or \f5NULL on error.
.Ss " Void_t* dtdelete(Dt_t* dt, Void_t* obj)" If \f5obj is \f5NULL, methods \f5Dtstack and \f5Dtqueue delete respectively stack top or queue head while other methods do nothing. If \f5obj is not \f5NULL, there are two cases. If the method in use is not \f5Dtbag or \f5Dtobag, the first object matching \f5obj is deleted. On the other hand, if the method in use is \f5Dtbag or \f5Dtobag, the library check to see if \f5obj is in the dictionary and delete it. If \f5obj is not in the dictionary, some object matching it will be deleted. See \f5Dtdisc_t.freef for object destruction. \f5dtdelete() returns the deleted object (even if it was deallocated) or \f5NULL on error.
.Ss " Void_t* dtattach(Dt_t* dt, Void_t* obj)" This function is similar to \f5dtinsert() but \f5obj itself will be inserted into \f5dt even if a discipline function \f5makef is defined.
.Ss " Void_t* dtdetach(Dt_t* dt, Void_t* obj)" This function is similar to \f5dtdelete() but the object to be deleted from \f5dt will not be freed (via the discipline \f5freef function).
.Ss " Void_t* dtsearch(Dt_t* dt, Void_t* obj)" .Ss " Void_t* dtmatch(Dt_t* dt, Void_t* key)" These functions find an object matching \f5obj or \f5key either from \f5dt or from some dictionary accessible from \f5dt via a viewpath (see \f5dtview().) \f5dtsearch() and \f5dtmatch() return the matching object or \f5NULL on failure.
.Ss " Void_t* dtfirst(Dt_t* dt)" .Ss " Void_t* dtnext(Dt_t* dt, Void_t* obj)" \f5dtfirst() returns the first object in \f5dt. \f5dtnext() returns the object following \f5obj. Objects are ordered based on the storage method in use. For \f5Dtoset and \f5Dtobag, objects are ordered by object comparisons. For \f5Dtstack, objects are ordered in reverse order of insertion. For \f5Dtqueue, objects are ordered in order of insertion. For \f5Dtlist, objects are ordered by list position. For \f5Dtset and \f5Dtbag, objects are ordered by some internal order (more below). Thus, objects in a dictionary or a viewpath can be walked using a \f5for(;;) loop as below. .Cs for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj)) .Ce When a dictionary uses \f5Dtset or \f5Dtbag, the object order is determined upon a call to \f5dtfirst()/\f5dtlast(). This order is frozen until a call \f5dtnext()/\f5dtprev() returns \f5NULL or when these same functions are called with a \f5NULL object argument. It is important that a \f5dtfirst()/dtlast() call be balanced by a \f5dtnext()/dtprev() call as described. Nested loops will require multiple balancing, once per loop. If loop balancing is not done carefully, either performance is degraded or unexpected behaviors may result. .Ss " Void_t* dtlast(Dt_t* dt)" .Ss " Void_t* dtprev(Dt_t* dt, Void_t* obj)" \f5dtlast() and \f5dtprev() are like \f5dtfirst() and \f5dtnext() but work in reverse order. Note that dictionaries on a viewpath are still walked in order but objects in each dictionary are walked in reverse order.
.Ss " Void_t* dtfinger(Dt_t* dt)" This function returns the current object of \f5dt, if any. The current object is defined after a successful call to one of \f5dtsearch(), \f5dtmatch(), \f5dtinsert(), \f5dtfirst(), \f5dtnext(), \f5dtlast(), or \f5dtprev(). As a side effect of this implementation of Cdt, when a dictionary is based on \f5Dtoset and \f5Dtobag, the current object is always defined and is the root of the tree.
.Ss " Void_t* dtrenew(Dt_t* dt, Void_t* obj)" This function repositions and perhaps rehashes an object \f5obj after its key has been changed. \f5dtrenew() only works if \f5obj is the current object (see \f5dtfinger()).
.Ss " dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)" This function calls \f5(*userf)(walk,obj,data) on each object in \f5dt and other dictionaries viewable from it. \f5walk is the dictionary containing \f5obj. If \f5userf() returns a \f5<0 value, \f5dtwalk() terminates and returns the same value. \f5dtwalk() returns \f50 on completion.
.Ss " Dtlink_t* dtflatten(Dt_t* dt)" .Ss " Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)" .Ss " Void_t* dtobj(Dt_t* dt, Dtlink_t* link)" Using \f5dtfirst()/dtnext() or \f5dtlast()/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), \f5dtflatten() and \f5dtlink() can be used. Objects in \f5dt are made into a linked list and walked as follows: .Cs for(link = dtflatten(dt); link; link = dtlink(dt,link) ) .Ce
Note that \f5dtflatten() returns a list of type \f5Dtlink_t*, not \f5Void_t*. That is, it returns a dictionary holder pointer, not a user object pointer (although both are the same if the discipline field \f5link is zero.) The macro function \f5dtlink() returns the dictionary holder object following \f5link. The macro function \f5dtobj(dt,link) returns the user object associated with \f5link, Beware that the flattened object list is unflattened on any dictionary operations other than \f5dtlink().
.Ss " Dtlink_t* dtextract(Dt_t* dt)" .Ss " int dtrestore(Dt_t* dt, Dtlink_t* link)" \f5dtextract() extracts all objects from \f5dt and makes it appear empty. \f5dtrestore() repopulates \f5dt with objects previously obtained via \f5dtextract(). \f5dtrestore() will fail if \f5dt is not empty. These functions can be used to share a same \f5dt handle among many sets of objects. They are useful to reduce dictionary overhead in an application that creates many concurrent dictionaries. It is important that the same discipline and method are in use at both extraction and restoration. Otherwise, undefined behaviors may result.
.Ss " #define DTTREESEARCH(Dt_t* dt, Void_t* obj, action)" .Ss " #define DTTREEMATCH(Dt_t* dt, Void_t* key, action)" These macro functions are analogues of \f5dtsearch() and \f5dtmatch() but they can only be used on a dictionary based on a binary search tree, i.e., \f5Dtoset or \f5Dtobag. .Tp \f5obj or \f5key: These are used to find a matching object. If there is no match, the result is \f5NULL. .Tp \f5action: The matching object \f5o (which may be \f5NULL) will be processed as follow: .Cs action (o); .Ce Since \f5action is used verbatim, it can be any C code fragment combinable with \f5(o) to form a syntactically correct C statement. For example, suppose that the matching object is an integer, the below code accumulates the integer value in a variable \f5total: .Cs DTTREEMATCH(dt, key, total += (int)); .Ce
.Ss "DICTIONARY INFORMATION"
.Ss " Dt_t* dtvnext(Dt_t* dt)" This returns the dictionary that \f5dt is viewing, if any. .Ss " int dtvcount(Dt_t* dt)" This returns the number of dictionaries that view \f5dt. .Ss " Dt_t* dtvhere(Dt_t* dt)" This returns the dictionary \f5v viewable from \f5dt where an object was found from the most recent search or walk operation. .Ss " int dtsize(Dt_t* dt)" This function returns the number of objects stored in \f5dt.
.Ss " int dtstat(Dt_t *dt, Dtstat_t* st, int all)" This function reports dictionary statistics. If \f5all is non-zero, all fields of \f5st are filled. Otherwise, only the \f5dt_type and \f5dt_size fields are filled. It returns \f50 on success and \f5-1 on error.
\f5Dtstat_t contains the below fields: .Tp \f5int dt_type: This is one of \f5DT_SET, \f5DT_BAG, \f5DT_OSET, \f5DT_OBAG, \f5DT_LIST, \f5DT_STACK, and \f5DT_QUEUE. .Tp \f5int dt_size: This contains the number of objects in the dictionary. .Tp \f5int dt_n: For \f5Dtset and \f5Dtbag, this is the number of non-empty chains in the hash table. For \f5Dtoset and \f5Dtobag, this is the deepest level in the tree (counting from zero.) Each level in the tree contains all nodes of equal distance from the root node. \f5dt_n and the below two fields are undefined for other methods. .Tp \f5int dt_max: For \f5Dtbag and \f5Dtset, this is the size of a largest chain. For \f5Dtoset and \f5Dtobag, this is the size of a largest level. .Tp \f5int* dt_count: For \f5Dtset and \f5Dtbag, this is the list of counts for chains of particular sizes. For example, \f5dt_count[1] is the number of chains of size \f51. For \f5Dtoset and \f5Dtobag, this is the list of sizes of the levels. For example, \f5dt_count[1] is the size of level \f51.
.Ss "HASH FUNCTIONS"
.Ss " unsigned int dtcharhash(unsigned int h, char c)" .Ss " unsigned int dtstrhash(unsigned int h, char* str, int n)" These functions compute hash values from bytes or strings. \f5dtcharhash() computes a new hash value from byte \f5c and seed value \f5h. \f5dtstrhash() computes a new hash value from string \f5str and seed value \f5h. If \f5n is positive, \f5str is a byte array of length \f5n; otherwise, \f5str is a null-terminated string.