diff options
Diffstat (limited to 'src/lib/libast/man/cdt.3')
| -rw-r--r-- | src/lib/libast/man/cdt.3 | 617 |
1 files changed, 617 insertions, 0 deletions
diff --git a/src/lib/libast/man/cdt.3 b/src/lib/libast/man/cdt.3 new file mode 100644 index 0000000..46bfe13 --- /dev/null +++ b/src/lib/libast/man/cdt.3 @@ -0,0 +1,617 @@ +.fp 5 CW +.TH LIBCDT 3 +.SH NAME +\fBCdt\fR \- container data types +.SH SYNOPSIS +.de Tp +.fl +.ne 2 +.TP +.. +.de Ss +.fl +.ne 2 +.SS "\\$1" +.. +.de Cs +.nf +.ft 5 +.. +.de Ce +.ft 1 +.fi +.. +.ta 1.0i 2.0i 3.0i 4.0i 5.0i +.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); +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, Void_t* arg); +int dtoptimize(Dt_t* dt); +int dtshare(Dt_t* dt, int type); +int dtlock(Dt_t* dt, unsigned int key, int type); +.Ce +.Ss "STORAGE METHODS" +.Cs +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; +.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* dtappend(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* dtleast(Dt_t* dt, Void_t* obj); +Void_t* dtmost(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* dt, Dtlink_t* link); +Void_t* dtobj(Dt_t* dt, Dtlink_t* link); +Dtlink_t* dtextract(Dt_t* dt); +Dtlink_t* dtrestore(Dt_t* dt, Dtlink_t* link); +.Ce +.Ss "DICTIONARY STATUS" +.Cs +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); +.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 +.SH DESCRIPTION +.PP +\fICdt\fP manages run-time dictionaries using standard container data types: +unordered set/multiset, ordered set/multiset, list, stack, and queue. +.PP +.Ss "DICTIONARY TYPES" +.PP +.Ss " Void_t*" +This type is used to pass objects between \fICdt\fP and application code. +\f5Void_t\fP is defined as \f5void\fP for ANSI-C and C++ +and \f5char\fP for older C compilation environments. +.PP +.Ss " Dt_t" +This is the type of a dictionary handle. +.PP +.Ss " Dtdisc_t" +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 \f5dtdisc()\fP). +.PP +.Ss " Dtmethod_t" +This defines the type of a container method. +.PP +.Ss " Dtlink_t" +This is the type of a dictionary object holder (see \f5dtdisc()\fP.) +.PP +.Ss " Dtstat_t" +This is the type of a structure to return dictionary statistics (see \f5dtstat()\fP.) +.PP +.Ss "DICTIONARY CONTROL" +.PP +.Ss " Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth)" +This creates a new dictionary. +\f5disc\fP is a discipline structure to describe object format. +\f5meth\fP specifies a manipulation method. +\f5dtopen()\fP returns the new dictionary or \f5NULL\fP on error. +See also the events \f5DT_OPEN\fP and \f5DT_ENDOPEN\fP below. +.PP +.Ss " int dtclose(Dt_t* dt)" +This deletes \f5dt\fP and its objects. +Note that \f5dtclose()\fP fails if \f5dt\fP is being viewed by +some other dictionaries (see \f5dtview()\fP). +\f5dtclose()\fP returns \f50\fP on success and \f5-1\fP on error. +See also the events \f5DT_CLOSE\fP and \f5DT_ENDCLOSE\fP below. +.PP +.Ss " void dtclear(Dt_t* dt)" +This deletes all objects in \f5dt\fP without closing \f5dt\fP. +.PP +.Ss " Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type)" +If \f5disc\fP is \f5NULL\fP, \f5dtdisc()\fP returns the current discipline. +Otherwise, it changes the discipline of \f5dt\fP to \f5disc\fP. +Objects may be rehashed, reordered, or removed as appropriate. +\f5type\fP can be any bit combination of \f5DT_SAMECMP\fP and \f5DT_SAMEHASH\fP. +\f5DT_SAMECMP\fP means that objects will compare exactly the same as before +thus obviating the need for reordering or removing new duplicates. +\f5DT_SAMEHASH\fP means that hash values of objects remain the same +thus obviating the need to rehash. +\f5dtdisc()\fP returns the previous discipline on success +and \f5NULL\fP on error. +.PP +.Ss " Dtmethod_t dtmethod(Dt_t* dt, const Dtmethod_t* meth)" +If \f5meth\fP is \f5NULL\fP, \f5dtmethod()\fP returns the current method. +Otherwise, it changes the storage method of \f5dt\fP to \f5meth\fP. +Objects may be rehashed, reordered, or removed as appropriate. +\f5dtmethod()\fP returns the previous method or \f5NULL\fP on error. +.PP +.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()\fP first terminates any current view from \f5dt\fP to another dictionary. +Then, if \f5view\fP is \f5NULL\fP, \f5dtview\fP returns the terminated view dictionary. +If \f5view\fP is not \f5NULL\fP, a viewpath from \f5dt\fP to \f5view\fP is established. +\f5dtview()\fP returns \f5dt\fP on success and \f5NULL\fP on error. +.PP +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. +.PP +.Ss " int dtcustomize(Dt_t* dt, int type, Void_t* arg)" +This customizes a storage method. The \f5type\fP argument +indicates the type of customization and \f5arg\fP gives additional +information for the operation. Here are the types: +.Tp +\f5DT_SHARE\fP: +This turns on/off the share mode for a dictionary. +Concurrent accesses of a dictionary not in share mode +may exhibit undefined behaviors including memory segmentation. + +Share mode allows multiple accessors, threads or processes, to access objects. +Such objects could be in the same directory in the case of threads or shared +memory in the case of processes. +.Tp +\f5DT_OPTIMIZE\fP: +This causes the underlying method to optimize its internal +data structure. For example, the splay tree underlying \f5Dtoset\fP +would be balanced. +.PP +.Ss " int dtoptimize(Dt_t* dt)" +This is a short-hand for invoking \f5dtcustomize()\fP with the \f5DT_OPTIMIZE\fP event. +.PP +.Ss " int dtshare(Dt_t* dt, int type)" +This turns on or off share mode for dictionary \f5dt\fP depending on whether \f5type\fP +is positive or non-positive. It returns -1 on failure. +.PP +.Ss " int dtlock(Dt_t* dt, unsigned int key, int type)" +This globally locks/unlocks a dictionary using the given \f5key\fP. +It returns 0 on success and -1 on failure. +The value of \f5key\fP must not be 0. +The argument \f5type\fP is used as follows: +.Tp +\f5type < 0\fP: +Unlock the dictionary if it was locked with \f5key\fP. +An error will result if the dictionary was locked with a different key. +.Tp +\f5type == 0\fP: +Attempt to lock the dictionary with \f5key\fP if it is unlocked. +An error will result if the dictionary was already locked with a different key. +.Tp +\f5type > 0\fP: +Attempt to lock the dictionary with \f5key\fP. +If the dictionary is already locked with a different key, +the call will loop and wait until the lock is open to lock it. + +.PP +.Ss "STORAGE METHODS" +.PP +Storage methods are of type \f5Dtmethod_t*\fP. +\fICdt\fP supports the following methods: +.PP +.Ss " Dtoset" +.Ss " Dtobag" +Objects are ordered by comparisons. +\f5Dtoset\fP keeps unique objects. +\f5Dtobag\fP allows repeatable objects. +.PP +.Ss " Dtset" +.Ss " Dtbag" +Objects are unordered. +\f5Dtset\fP keeps unique objects. +\f5Dtbag\fP allows repeatable objects. +The underlying data structure is a hash table with chaining to handle collisions. +.PP +.Ss " Dtrhset" +.Ss " Dtrhbag" +These methods are like \f5Dtset\fP and \f5Dtbag\fP 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 share dictionaries. +.PP +.Ss " Dtlist" +Objects are kept in a list. +\fIA current object\fP is always defined to be either the head of +the list or an object resulting from a recent search or insert operation. +The call \f5dtinsert()\fP will insert a new object +in front of such a current object +while the call \f5dtappend()\fP will append in back of it. +.PP +.Ss " Dtdeque" +Objects are kept in a deque. This is similar to \f5Dtlist\fP +except that objects are always inserted at the front and appended at the tail +of the list. +.PP +.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. +.PP +.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. +.PP +.Ss "DISCIPLINE" +.PP +Object format and associated management functions are +defined in the type \f5Dtdisc_t\fP: +.Cs + 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; +.Ce +.Ss " ssize_t key, size" +Each object \f5obj\fP is identified by a key used for object comparison or hashing. +\f5key\fP should be non-negative and defines an offset into \f5obj\fP. +If \f5size\fP is negative, the key is a null-terminated +string with starting address \f5*(Void_t**)((char*)obj+key)\fP. +If \f5size\fP is zero, the key is a null-terminated string with starting address +\f5(Void_t*)((char*)obj+key)\fP. +Finally, if \f5size\fP is positive, the key is a byte array of length \f5size\fP +starting at \f5(Void_t*)((char*)obj+key)\fP. +.PP +.Ss " ssize_t link" +Let \f5obj\fP be an object to be inserted into \f5dt\fP. +If \f5link\fP is negative, an object holder of type \f5Dtlink_t\fP +will be allocated to hold \f5obj\fP. +Otherwise, \f5obj\fP should have +a \f5Dtlink_t\fP structure embedded \f5link\fP bytes into it, +i.e., at address \f5(Dtlink_t*)((char*)obj+link)\fP. +.PP +.Ss " Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)" +If \f5makef\fP is not \f5NULL\fP, +\f5dtinsert(dt,obj)\fP or \f5dtappend()\fP will call it +to make a copy of \f5obj\fP suitable for insertion into \f5dt\fP. +If \f5makef\fP is \f5NULL\fP, \f5obj\fP itself will be inserted into \f5dt\fP. +.PP +.Ss " void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)" +If not \f5NULL\fP, +\f5freef\fP is used to destroy data associated with \f5obj\fP. +.PP +.Ss "int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)" +If not \f5NULL\fP, \f5comparf\fP is used to compare two keys. +Its return value should be \f5<0\fP, \f5=0\fP, or \f5>0\fP to indicate +whether \f5key1\fP is smaller, equal to, or larger than \f5key2\fP. +All three values are significant for method \f5Dtoset\fP and \f5Dtobag\fP. +For other methods, a zero value +indicates equality and a non-zero value indicates inequality. +If \f5(*comparf)()\fP is \f5NULL\fP, an internal function is used +to compare the keys as defined by the \f5Dtdisc_t.size\fP field. +.PP +.Ss " unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)" +If not \f5NULL\fP, +\f5hashf\fP is used to compute the hash value of \f5key\fP. +It is required that keys compared equal will also have same hash values. +If \f5hashf\fP is \f5NULL\fP, an internal function is used to hash +the key as defined by the \f5Dtdisc_t.size\fP field. +.PP +.Ss " Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)" +If not \f5NULL\fP, \f5memoryf\fP is used to allocate and free memory. +When \f5addr\fP is \f5NULL\fP, a memory segment of size \f5size\fP is requested. +If \f5addr\fP is not \f5NULL\fP and \f5size\fP is zero, \f5addr\fP is to be freed. +If \f5addr\fP is not \f5NULL\fP and \f5size\fP is positive, +\f5addr\fP is to be resized to the given size. +If \f5memoryf\fP is \f5NULL\fP, \fImalloc(3)\fP is used. +.PP +.Ss " int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)" +If not \f5NULL\fP, \f5eventf\fP announces various events. +Each event may have particular handling of the return values from \f5eventf\fP. +But a negative return value typically means failure. +Following are the events: +.Tp +\f5DT_OPEN\fP: +This event is raised at the start of the process to open a new dictionary. +The argument \f5data\fP will be a pointer to an object of type \f5Void_t*\fP +initialized to \f5NULL\fP before the call. The return value of \f5eventf()\fP +is significant as follows: + +On a negative return value, \f5dtopen()\fP will return failure. + +On a zero return value, \f5eventf()\fP may set \f5*(Void_t**)data\fP to some non-\f5NULL\fP +value to indicate that the dictionary structure itself should be allocated +along with the \f5Dtdisc_t.data\fP section. +Otherwise, it will be allocated separately with \f5malloc(3)\fP. + +On a positive return value, the dictionary is being reconstructed +based on existing states of some previous dictionary. +In this case, \f5eventf()\fP should set \f5*(Void_t**)data\fP to point to +the field \f5Dt_t.data\fP of the corresponding previous dictionary (see \f5DT_CLOSE\fP 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 \f5malloc()\fP. +The ability to create different dictionaries sharing the same set of objects +allows for managing objects in shared and/or persistent memory. +.Tp +\f5DT_ENDOPEN\fP: +This event is raised at the end of the process to open a dictionary. +The return value of \f5eventf()\fP will be ignored. +.Tp +\f5DT_CLOSE\fP: +This event is raised at the start of the process to close dictionary \f5dt\fP. +The return value of \f5eventf\fP is significant as follows: + +On a negative return value, \f5dtclose()\fP will return failure. + +On a zero return value, all dictionary objects will be deleted and +and all associated memory will be freed. + +On a positive return value, allocated objects and memory will be kept intact. +This means that \f5dt->data\fP remains intact and can be reused in some future +dictionary (see \f5DT_OPEN\fP above). +Note, however, that \f5dt\fP itself would still be freed if it was allocated with \f5malloc(3)\fP. +.Tp +\f5DT_ENDCLOSE\fP: +This event is raised at the end of the process to close a dictionary. +The return value of \f5eventf()\fP will be ignored. +.Tp +\f5DT_DISC\fP: +The discipline of \f5dt\fP is being changed to a new one given in +\f5(Dtdisc_t*)data\fP. +.Tp +\f5DT_METH\fP: +The method of \f5dt\fP is being changed to a new one given in +\f5(Dtmethod_t*)data\fP. +.Tp +\f5DT_HASHSIZE\fP: +This event is applicable to +the methods \f5Dtset\fP, \f5Dtbag\fP, \f5Dtrhset\fP and \f5Dtrhbag\fP. +It is typically issued when the respective internal data structure of +a method is about to be initialized. +If the return value of the event handling function is positive, +\f5*(ssize_t*)data\fP is examined for further action; +else, it is ignored. +A positive return value means that the event function wishes to suggest a table size. +It does that by setting \f5*(ssize_t*)data\fP to the desired size. +Then, the actual table size will be the maximum of the absolute value +of \f5*(ssize_t*)data\fP and some predefined value set by the method. +In addition, if \f5*(ssize_t*)data\fP was negative, +the \f5Dtset\fP and \f5Dtbag\fP methods will never resize the hash table. +.Tp +\f5DT_ERROR\fP: +This event announces an error that occurred during some operations. +The argument \f5(char*)data\fP is a null-terminated string describing the error. +.PP +.Ss "#define DTOFFSET(struct_s,member)" +This macro function computes the offset of \f5member\fP from the start +of structure \f5struct_s\fP. It is useful for getting the offset of +a \f5Dtlink_t\fP embedded inside an object. +.PP +.Ss "#define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)" +This macro function initializes the discipline pointed to by \f5disc\fP +with the given values. +.PP +.Ss "OBJECT OPERATIONS" +.PP +.Ss " Void_t* dtinsert(Dt_t* dt, Void_t* obj)" +.Ss " Void_t* dtappend(Dt_t* dt, Void_t* obj)" +These functions add an object prototyped by \f5obj\fP into \f5dt\fP. +\f5dtinsert()\fP and \f5dtappend()\fP perform the same function +for all methods except for \f5Dtlist\fP (see \f5Dtlist\fP for details). +If there is an existing object in \f5dt\fP matching \f5obj\fP +and the storage method is \f5Dtset\fP, \f5Dtrhset\fP or \f5Dtoset\fP, +\f5dtinsert()\fP and \f5dtappend()\fP will simply return the matching object. +Otherwise, a new object is inserted according to the method in use. +See \f5Dtdisc_t.makef\fP for object construction. +The new object or a matching object as noted will be returned on success +while \f5NULL\fP is returned on error. +.PP +.Ss " Void_t* dtdelete(Dt_t* dt, Void_t* obj)" +If \f5obj\fP is \f5NULL\fP, methods \f5Dtstack\fP and \f5Dtqueue\fP +delete respectively stack top or queue head while other methods do nothing. +If \f5obj\fP is not \f5NULL\fP, an object matching \f5obj\fP is deleted. +See \f5Dtdisc_t.freef\fP for object destruction. +\f5dtdelete()\fP returns the deleted object (even if it was deallocated) +or \f5NULL\fP on error. +.PP +.Ss " Void_t* dtattach(Dt_t* dt, Void_t* obj)" +This function is similar to \f5dtinsert()\fP but \f5obj\fP itself +will be inserted into \f5dt\fP even if a discipline +function \f5makef\fP is defined. +.PP +.Ss " Void_t* dtdetach(Dt_t* dt, Void_t* obj)" +This function is similar to \f5dtdelete()\fP but the object to be deleted +from \f5dt\fP will not be freed (via the discipline \f5freef\fP function). +.PP +.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\fP or \f5key\fP either from \f5dt\fP or +from some dictionary accessible from \f5dt\fP via a viewpath (see \f5dtview()\fP.) +\f5dtsearch()\fP and \f5dtmatch()\fP return the matching object or +\f5NULL\fP on failure. +.PP +.Ss " Void_t* dtfirst(Dt_t* dt)" +.Ss " Void_t* dtnext(Dt_t* dt, Void_t* obj)" +\f5dtfirst()\fP returns the first object in \f5dt\fP. +\f5dtnext()\fP returns the object that follows an object matching \f5obj\fP. +Objects are ordered based on the storage method in use. +For \f5Dtoset\fP and \f5Dtobag\fP, objects are ordered by object comparisons. +For \f5Dtstack\fP, objects are ordered in reverse order of insertion. +For \f5Dtqueue\fP, objects are ordered in order of insertion. +For \f5Dtlist\fP, objects are ordered by list position. +For \f5Dtset\fP, \f5Dtbag\fP, \f5Dtrhset\fP and \f5Dtrhbag\fP, +objects are ordered by some internal order defined at the time when these +functions are called. + +Objects in a dictionary or a viewpath can be walked using +a \f5for(;;)\fP loop as below. +.Cs + for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj)) +.Ce +.PP +.Ss " Void_t* dtlast(Dt_t* dt)" +.Ss " Void_t* dtprev(Dt_t* dt, Void_t* obj)" +\f5dtlast()\fP and \f5dtprev()\fP are like \f5dtfirst()\fP and \f5dtnext()\fP +but work in reverse order. +For \f5Dtset\fP, \f5Dtbag\fP, \f5Dtrhset\fP and \f5Dtrhbag\fP, +both reverse and forward orders are the same. +Note that dictionaries on a viewpath are still walked in the order +of the viewpath. +.PP +.Ss " Void_t* dtleast(Dt_t* dt, Void_t* obj)" +.Ss " Void_t* dtmost(Dt_t* dt, Void_t* obj)" +\f5dtleast()\fP returns the smallest object greater or equal to \f5obj\fP. +\f5dtmost()\fP returns the largest object smaller or equal to \f5obj\fP. +Again, object ordering depends on the storage method in use. +For example, with \f5Dtoset\fP and \f5Dtobag\fP, the ordering of objects +is well-defined and it is possible to call \f5dtleast()\fP or \f5dtmost()\fP +on an object not in the dictionary and still get a meaningful result. +On the other hand, with \f5Dtset\fP or \f5Dtrhset\fP, such a call will +essentially be the same as \f5dtsearch()\fP because without matching +an object, it cannot be determined what comes before or after. +.PP +.Ss " dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)" +This function calls \f5(*userf)(walk,obj,data)\fP on each object in \f5dt\fP and +other dictionaries viewable from it. +\f5walk\fP is the dictionary containing \f5obj\fP. +If \f5userf()\fP returns a \f5<0\fP value, +\f5dtwalk()\fP terminates and returns the same value. +\f5dtwalk()\fP returns \f50\fP on completion. +.PP +.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()\fP or \f5dtlast()/dtprev()\fP +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()\fP and \f5dtlink()\fP can be used. +Objects in \f5dt\fP are made into a linked list and walked as follows: +.Cs + for(link = dtflatten(dt); link; link = dtlink(dt,link) ) +.Ce +.PP +Note that \f5dtflatten()\fP returns a list of type \f5Dtlink_t*\fP, +not \f5Void_t*\fP. That is, it returns a dictionary holder pointer, +not a user object pointer +(although both are the same if the discipline field \f5link\fP is zero.) +The macro function \f5dtlink()\fP +returns the dictionary holder object following \f5link\fP. +The macro function \f5dtobj(dt,link)\fP +returns the user object associated with \f5link\fP, +Beware that the flattened object list is unflattened on any +dictionary operations other than \f5dtlink()\fP. +.PP +.Ss " Dtlink_t* dtextract(Dt_t* dt)" +.Ss " Dtlink_t* dtrestore(Dt_t* dt, Dtlink_t* list)" +\f5dtextract()\fP extracts the list of objects from \f5dt\fP and makes it appear empty. +\f5dtrestore()\fP repopulates \f5dt\fP with +a list of objects previously obtained via \f5dtextract()\fP. +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 \f5NULL\fP on error. + +.PP +.Ss "DICTIONARY INFORMATION" +.PP +.Ss " Dt_t* dtvnext(Dt_t* dt)" +This returns the dictionary that \f5dt\fP is viewing, if any. +.Ss " ssize_t dtvcount(Dt_t* dt)" +This returns the number of dictionaries that view \f5dt\fP. +.Ss " Dt_t* dtvhere(Dt_t* dt)" +This returns the dictionary \f5v\fP viewable from \f5dt\fP +where an object was found from the most recent search or walk operation. +.Ss " ssize_t dtsize(Dt_t* dt)" +This function returns the number of objects stored in \f5dt\fP. +.PP +.Ss " ssize_t dtstat(Dt_t *dt, Dtstat_t* st)" +This function reports dictionary statistics. +It returns the number of objects stored in \f5dt\fP. +.PP +\f5Dtstat_t\fP contains the below fields: +.Tp +\f5int meth\fP: +This returns the method used for the dictionary, e.g., \f5DT_SET\fP, \f5DT_OSET\fP, etc. +.Tp +\f5ssize_t size\fP: +This has the number of objects in the dictionary. +.Tp +\f5ssize_t mlev\fP: +This returns the maximum number of levels in the data structure used for object storage, i.e., +the binary tree or the recursive hash table. +For a hash table with chaining (i.e., \f5Dtset\fP and \f5Dtbag\fP), +it gives the length of the longest chain. +.Tp +\f5ssize_t lsize[]\fP: +This gives the object counts at each level. +For a hash table with chaining (i.e., \f5Dtset\fP and \f5Dtbag\fP), +a level is defined as objects at that position in their chains. +Since chains can be arbitrarily long, the report is limited +to objects at a level less than \f5DT_MAXSIZE\fP. +.Tp +\f5ssize_t tsize[]\fP: +For a hash table using a trie structure, this counts the number of +sub-tables at each level. For example, \f5tsize[0]\fP should be 1 +only for this hash table type. +.PP +.Ss "HASH FUNCTIONS" +.PP +.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()\fP computes a new hash value from byte \f5c\fP and seed value \f5h\fP. +\f5dtstrhash()\fP computes a new hash value from string \f5str\fP and seed value \f5h\fP. +If \f5n\fP is positive, \f5str\fP is a byte array of length \f5n\fP; +otherwise, \f5str\fP is a null-terminated string. +.PP +.SH IMPLEMENTATION NOTES +\f5Dtlist\fP, \f5Dtstack\fP and \f5Dtqueue\fP are based on doubly linked list. +\f5Dtoset\fP and \f5Dtobag\fP are based on top-down splay trees. +\f5Dtset\fP and \f5Dtbag\fP are based on hash tables with +move-to-front collision chains. +\f5Dtrhset\fP and \f5Dtrhbag\fP are based on a recursive hashing data structure +that avoids table resizing. +.PP +.SH AUTHOR +Kiem-Phong Vo, kpv@research.att.com |