Daniel@0: .TH LIBCDT 3
Daniel@0: .SH NAME
Daniel@0: \fBCdt\fR \- container data types
Daniel@0: .SH SYNOPSIS
Daniel@0: .de Tp
Daniel@0: .fl
Daniel@0: .ne 2
Daniel@0: .TP
Daniel@0: ..
Daniel@0: .de Ss
Daniel@0: .fl
Daniel@0: .ne 2
Daniel@0: .SS "\\$1"
Daniel@0: ..
Daniel@0: .de Cs
Daniel@0: .nf
Daniel@0: .ft 5
Daniel@0: ..
Daniel@0: .de Ce
Daniel@0: .ft 1
Daniel@0: .fi
Daniel@0: ..
Daniel@0: .ta 1.0i 2.0i 3.0i 4.0i 5.0i
Daniel@0: .Cs
Daniel@0: #include <graphviz/cdt.h>
Daniel@0: .Ce
Daniel@0: .Ss "DICTIONARY TYPES"
Daniel@0: .Cs
Daniel@0: Void_t*;
Daniel@0: Dt_t;
Daniel@0: Dtdisc_t;
Daniel@0: Dtmethod_t;
Daniel@0: Dtlink_t;
Daniel@0: Dtstat_t;
Daniel@0: .Ce
Daniel@0: .Ss "DICTIONARY CONTROL"
Daniel@0: .Cs
Daniel@0: Dt_t*       dtopen(Dtdisc_t* disc, Dtmethod_t* meth);
Daniel@0: int         dtclose(Dt_t* dt);
Daniel@0: void        dtclear(dt);
Daniel@0: Dtmethod_t* dtmethod(Dt_t* dt, Dtmethod_t* meth);
Daniel@0: Dtdisc_t*   dtdisc(Dt_t* dt, Dtdisc_t* disc, int type);
Daniel@0: Dt_t*       dtview(Dt_t* dt, Dt_t* view);
Daniel@0: .Ce
Daniel@0: .Ss "STORAGE METHODS"
Daniel@0: .Cs
Daniel@0: Dtmethod_t* Dtset;
Daniel@0: Dtmethod_t* Dtbag;
Daniel@0: Dtmethod_t* Dtoset;
Daniel@0: Dtmethod_t* Dtobag;
Daniel@0: Dtmethod_t* Dtlist;
Daniel@0: Dtmethod_t* Dtstack;
Daniel@0: Dtmethod_t* Dtqueue;
Daniel@0: .Ce
Daniel@0: .Ss "DISCIPLINE"
Daniel@0: .Cs
Daniel@0: typedef Void_t*      (*Dtmake_f)(Dt_t*, Void_t*, Dtdisc_t*);
Daniel@0: typedef void         (*Dtfree_f)(Dt_t*, Void_t*, Dtdisc_t*);
Daniel@0: typedef int          (*Dtcompar_f)(Dt_t*, Void_t*, Void_t*, Dtdisc_t*);
Daniel@0: typedef unsigned int (*Dthash_f)(Dt_t*, Void_t*, Dtdisc_t*);
Daniel@0: typedef Void_t*      (*Dtmemory_f)(Dt_t*, Void_t*, size_t, Dtdisc_t*);
Daniel@0: typedef int          (*Dtevent_f)(Dt_t*, int, Void_t*, Dtdisc_t*);
Daniel@0: .Ce
Daniel@0: .Ss "OBJECT OPERATIONS"
Daniel@0: .Cs
Daniel@0: Void_t*   dtinsert(Dt_t* dt, Void_t* obj);
Daniel@0: Void_t*   dtdelete(Dt_t* dt, Void_t* obj);
Daniel@0: Void_t*   dtsearch(Dt_t* dt, Void_t* obj);
Daniel@0: Void_t*   dtmatch(Dt_t* dt, Void_t* key);
Daniel@0: Void_t*   dtfirst(Dt_t* dt);
Daniel@0: Void_t*   dtnext(Dt_t* dt, Void_t* obj);
Daniel@0: Void_t*   dtlast(Dt_t* dt);
Daniel@0: Void_t*   dtprev(Dt_t* dt, Void_t* obj);
Daniel@0: Void_t*   dtfinger(Dt_t* dt);
Daniel@0: Void_t*   dtrenew(Dt_t* dt, Void_t* obj);
Daniel@0: int       dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t*);
Daniel@0: Dtlink_t* dtflatten(Dt_t* dt);
Daniel@0: Dtlink_t* dtlink(Dt_t*, Dtlink_t* link);
Daniel@0: Void_t*   dtobj(Dt_t* dt, Dtlink_t* link);
Daniel@0: Dtlink_t* dtextract(Dt_t* dt);
Daniel@0: int       dtrestore(Dt_t* dt, Dtlink_t* link);
Daniel@0: .Ce
Daniel@0: .Ss "DICTIONARY STATUS"
Daniel@0: .Cs
Daniel@0: Dt_t*     dtvnext(Dt_t* dt);
Daniel@0: int       dtvcount(Dt_t* dt);
Daniel@0: Dt_t*     dtvhere(Dt_t* dt);
Daniel@0: int       dtsize(Dt_t* dt);
Daniel@0: int       dtstat(Dt_t* dt, Dtstat_t*, int all);
Daniel@0: .Ce
Daniel@0: .Ss "HASH FUNCTIONS"
Daniel@0: .Cs
Daniel@0: unsigned int dtstrhash(unsigned int h, char* str, int n);
Daniel@0: unsigned int dtcharhash(unsigned int h, unsigned char c);
Daniel@0: .Ce
Daniel@0: .SH DESCRIPTION
Daniel@0: .PP
Daniel@0: \fICdt\fP manages run-time dictionaries using standard container data types:
Daniel@0: unordered set/multiset, ordered set/multiset, list, stack, and queue.
Daniel@0: .PP
Daniel@0: .Ss "DICTIONARY TYPES"
Daniel@0: .PP
Daniel@0: .Ss "  Void_t*"
Daniel@0: This type is used to pass objects between \fICdt\fP and application code.
Daniel@0: \f5Void_t\fP is defined as \f5void\fP for ANSI-C and C++
Daniel@0: and \f5char\fP for other compilation environments.
Daniel@0: .PP
Daniel@0: .Ss "  Dt_t"
Daniel@0: This is the type of a dictionary handle.
Daniel@0: .PP
Daniel@0: .Ss "  Dtdisc_t"
Daniel@0: This defines the type of a discipline structure which describes
Daniel@0: object lay-out and manipulation functions.
Daniel@0: .PP
Daniel@0: .Ss "  Dtmethod_t"
Daniel@0: This defines the type of a container method.
Daniel@0: .PP
Daniel@0: .Ss "  Dtlink_t"
Daniel@0: This is the type of a dictionary object holder (see \f5dtdisc()\fP.)
Daniel@0: .PP
Daniel@0: .Ss "  Dtstat_t"
Daniel@0: This is the type of a structure to return dictionary statistics (see \f5dtstat()\fP.)
Daniel@0: .PP
Daniel@0: .Ss "DICTIONARY CONTROL"
Daniel@0: .PP
Daniel@0: .Ss "  Dt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth)"
Daniel@0: This creates a new dictionary.
Daniel@0: \f5disc\fP is a discipline structure to describe object format.
Daniel@0: \f5meth\fP specifies a manipulation method.
Daniel@0: \f5dtopen()\fP returns the new dictionary or \f5NULL\fP on error.
Daniel@0: .PP
Daniel@0: .Ss "  int dtclose(Dt_t* dt)"
Daniel@0: This deletes \f5dt\fP and its objects.
Daniel@0: Note that \f5dtclose()\fP fails if \f5dt\fP is being viewed by
Daniel@0: some other dictionaries (see \f5dtview()\fP).
Daniel@0: \f5dtclose()\fP returns \f50\fP on success and \f5-1\fP on error.
Daniel@0: .PP
Daniel@0: .Ss "  void dtclear(Dt_t* dt)"
Daniel@0: This deletes all objects in \f5dt\fP without closing \f5dt\fP.
Daniel@0: .PP
Daniel@0: .Ss "  Dtmethod_t dtmethod(Dt_t* dt, Dtmethod_t* meth)"
Daniel@0: If \f5meth\fP is \f5NULL\fP, \f5dtmethod()\fP returns the current method.
Daniel@0: Otherwise, it changes the storage method of \f5dt\fP to \f5meth\fP.
Daniel@0: Object order remains the same during a
Daniel@0: method switch among \f5Dtlist\fP, \f5Dtstack\fP and \f5Dtqueue\fP.
Daniel@0: Switching to and from \f5Dtset/Dtbag\fP and \f5Dtoset/Dtobag\fP may cause
Daniel@0: objects to be rehashed, reordered, or removed as the case requires.
Daniel@0: \f5dtmethod()\fP returns the previous method or \f5NULL\fP on error.
Daniel@0: .PP
Daniel@0: .Ss "  Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type)"
Daniel@0: If \f5disc\fP is \f5NULL\fP, \f5dtdisc()\fP returns the current discipline.
Daniel@0: Otherwise, it changes the discipline of \f5dt\fP to \f5disc\fP.
Daniel@0: Objects may be rehashed, reordered, or removed as appropriate.
Daniel@0: \f5type\fP can be any bit combination of \f5DT_SAMECMP\fP and \f5DT_SAMEHASH\fP.
Daniel@0: \f5DT_SAMECMP\fP means that objects will compare exactly the same as before
Daniel@0: thus obviating the need for reordering or removing new duplicates.
Daniel@0: \f5DT_SAMEHASH\fP means that hash values of objects remain the same
Daniel@0: thus obviating the need to rehash.
Daniel@0: \f5dtdisc()\fP returns the previous discipline on success
Daniel@0: and \f5NULL\fP on error.
Daniel@0: .PP
Daniel@0: .Ss "  Dt_t* dtview(Dt_t* dt, Dt_t* view)"
Daniel@0: A viewpath allows a search or walk starting from a dictionary to continue to another.
Daniel@0: \f5dtview()\fP first terminates any current view from \f5dt\fP to another dictionary.
Daniel@0: Then, if \f5view\fP is \f5NULL\fP, \f5dtview\fP returns the terminated view dictionary.
Daniel@0: If \f5view\fP is not \f5NULL\fP, a viewpath from \f5dt\fP to \f5view\fP is established.
Daniel@0: \f5dtview()\fP returns \f5dt\fP on success and \f5NULL\fP on error.
Daniel@0: .PP
Daniel@0: If two dictionaries on the same viewpath have the same values for the discipline fields
Daniel@0: \f5Dtdisc_t.link\fP, \f5Dtdisc_t.key\fP, \f5Dtdisc_t.size\fP, and \f5Dtdisc_t.hashf\fP,
Daniel@0: it is expected that key hashing will be the same.
Daniel@0: If not, undefined behaviors may result during a search or a walk.
Daniel@0: .PP
Daniel@0: .Ss "STORAGE METHODS"
Daniel@0: .PP
Daniel@0: Storage methods are of type \f5Dtmethod_t*\fP.
Daniel@0: \fICdt\fP supports the following methods:
Daniel@0: .PP
Daniel@0: .Ss "  Dtoset"
Daniel@0: .Ss "  Dtobag"
Daniel@0: Objects are ordered by comparisons.
Daniel@0: \f5Dtoset\fP keeps unique objects.
Daniel@0: \f5Dtobag\fP allows repeatable objects.
Daniel@0: .PP
Daniel@0: .Ss "  Dtset"
Daniel@0: .Ss "  Dtbag"
Daniel@0: Objects are unordered.
Daniel@0: \f5Dtset\fP keeps unique objects.
Daniel@0: \f5Dtbag\fP allows repeatable objects and always keeps them together
Daniel@0: (note the effect on dictionary walking.)
Daniel@0: .PP
Daniel@0: .Ss "  Dtlist"
Daniel@0: Objects are kept in a list.
Daniel@0: New objects are inserted either
Daniel@0: in front of \fIcurrent object\fP (see \f5dtfinger()\fP) if this is defined
Daniel@0: or at list front if there is no current object.
Daniel@0: .PP
Daniel@0: .Ss "  Dtstack"
Daniel@0: Objects are kept in a stack, i.e., in reverse order of insertion.
Daniel@0: Thus, the last object inserted is at stack top
Daniel@0: and will be the first to be deleted.
Daniel@0: .PP
Daniel@0: .Ss "  Dtqueue"
Daniel@0: Objects are kept in a queue, i.e., in order of insertion.
Daniel@0: Thus, the first object inserted is at queue head
Daniel@0: and will be the first to be deleted.
Daniel@0: .PP
Daniel@0: .Ss "DISCIPLINE"
Daniel@0: .PP
Daniel@0: Object format and associated management functions are
Daniel@0: defined in the type \f5Dtdisc_t\fP:
Daniel@0: .Cs
Daniel@0:     typedef struct
Daniel@0:     { int        key, size;
Daniel@0:       int        link;
Daniel@0:       Dtmake_f   makef;
Daniel@0:       Dtfree_f   freef;
Daniel@0:       Dtcompar_f comparf;
Daniel@0:       Dthash_f   hashf;
Daniel@0:       Dtmemory_f memoryf;
Daniel@0:       Dtevent_f  eventf;
Daniel@0:     } Dtdisc_t;
Daniel@0: .Ce
Daniel@0: .Ss "  int key, size"
Daniel@0: Each object \f5obj\fP is identified by a key used for object comparison or hashing.
Daniel@0: \f5key\fP should be non-negative and defines an offset into \f5obj\fP.
Daniel@0: If \f5size\fP is negative, the key is a null-terminated
Daniel@0: string with starting address \f5*(Void_t**)((char*)obj+key)\fP.
Daniel@0: If \f5size\fP is zero, the key is a null-terminated string with starting address
Daniel@0: \f5(Void_t*)((char*)obj+key)\fP.
Daniel@0: Finally, if \f5size\fP is positive, the key is a byte array of length \f5size\fP
Daniel@0: starting at \f5(Void_t*)((char*)obj+key)\fP.
Daniel@0: .PP
Daniel@0: .Ss "  int link"
Daniel@0: Let \f5obj\fP be an object to be inserted into \f5dt\fP as discussed below.
Daniel@0: If \f5link\fP is negative, an internally allocated object holder is used
Daniel@0: to hold \f5obj\fP. Otherwise, \f5obj\fP should have
Daniel@0: a \f5Dtlink_t\fP structure embedded \f5link\fP bytes into it,
Daniel@0: i.e., at address \f5(Dtlink_t*)((char*)obj+link)\fP.
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)"
Daniel@0: If \f5makef\fP is not \f5NULL\fP,
Daniel@0: \f5dtinsert(dt,obj)\fP will call it
Daniel@0: to make a copy of \f5obj\fP suitable for insertion into \f5dt\fP.
Daniel@0: If \f5makef\fP is \f5NULL\fP, \f5obj\fP itself will be inserted into \f5dt\fP.
Daniel@0: .PP
Daniel@0: .Ss "  void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)"
Daniel@0: If not \f5NULL\fP,
Daniel@0: \f5freef\fP is used to destroy data associated with \f5obj\fP.
Daniel@0: .PP
Daniel@0: .Ss "int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)"
Daniel@0: If not \f5NULL\fP, \f5comparf\fP is used to compare two keys.
Daniel@0: Its return value should be \f5<0\fP, \f5=0\fP, or \f5>0\fP to indicate
Daniel@0: whether \f5key1\fP is smaller, equal to, or larger than \f5key2\fP.
Daniel@0: All three values are significant for method \f5Dtoset\fP and \f5Dtobag\fP.
Daniel@0: For other methods, a zero value
Daniel@0: indicates equality and a non-zero value indicates inequality.
Daniel@0: If \f5(*comparf)()\fP is \f5NULL\fP, an internal function is used
Daniel@0: to compare the keys as defined by the \f5Dtdisc_t.size\fP field.
Daniel@0: .PP
Daniel@0: .Ss "  unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)"
Daniel@0: If not \f5NULL\fP,
Daniel@0: \f5hashf\fP is used to compute the hash value of \f5key\fP.
Daniel@0: It is required that keys compared equal will also have same hash values.
Daniel@0: If \f5hashf\fP is \f5NULL\fP, an internal function is used to hash
Daniel@0: the key as defined by the \f5Dtdisc_t.size\fP field.
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)"
Daniel@0: If not \f5NULL\fP, \f5memoryf\fP is used to allocate and free memory.
Daniel@0: When \f5addr\fP is \f5NULL\fP, a memory segment of size \f5size\fP is requested. 
Daniel@0: If \f5addr\fP is not \f5NULL\fP and \f5size\fP is zero, \f5addr\fP is to be freed.
Daniel@0: If \f5addr\fP is not \f5NULL\fP and \f5size\fP is positive,
Daniel@0: \f5addr\fP is to be resized to the given size.
Daniel@0: If \f5memoryf\fP is \f5NULL\fP, \fImalloc(3)\fP is used.
Daniel@0: When dictionaries share memory,
Daniel@0: a record of the first allocated memory segment should be kept
Daniel@0: so that it can be used to initialize new dictionaries (see below.)
Daniel@0: .PP
Daniel@0: .Ss "  int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)"
Daniel@0: If not \f5NULL\fP, \f5eventf\fP announces various events.
Daniel@0: If it returns a negative value, the calling operation will terminate with failure.
Daniel@0: Unless noted otherwise, a non-negative return value let the
Daniel@0: calling function proceed normally. Following are the events:
Daniel@0: .Tp
Daniel@0: \f5DT_OPEN\fP:
Daniel@0: \f5dt\fP is being opened.
Daniel@0: If \f5eventf\fP returns zero, the opening process proceeds normally.
Daniel@0: A positive return value indicates that \f5dt\fP
Daniel@0: uses memory already initialized by a different dictionary.
Daniel@0: In that case, \f5*(Void_t**)data\fP should be set to
Daniel@0: the first allocated memory segment as discussed in \f5memoryf\fP.
Daniel@0: \f5dtopen()\fP may fail if this segment is not returned or
Daniel@0: if it has not been properly initialized.
Daniel@0: .Tp
Daniel@0: \f5DT_CLOSE\fP:
Daniel@0: \f5dt\fP is being closed.
Daniel@0: .Tp
Daniel@0: \f5DT_DISC\fP:
Daniel@0: The discipline of \f5dt\fP is being changed to a new one given in
Daniel@0: \f5(Dtdisc_t*)data\fP.
Daniel@0: .Tp
Daniel@0: \f5DT_METH\fP:
Daniel@0: The method of \f5dt\fP is being changed to a new one given in
Daniel@0: \f5(Dtmethod_t*)data\fP.
Daniel@0: .PP
Daniel@0: .Ss "OBJECT OPERATIONS"
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* dtinsert(Dt_t* dt, Void_t* obj)"
Daniel@0: This inserts an object prototyped by \f5obj\fP into \f5dt\fP.
Daniel@0: If there is an existing object in \f5dt\fP matching \f5obj\fP
Daniel@0: and the storage method is \f5Dtset\fP or \f5Dtoset\fP,
Daniel@0: \f5dtinsert()\fP will simply return the matching object.
Daniel@0: Otherwise, a new object is inserted according to the method in use.
Daniel@0: See \f5Dtdisc_t.makef\fP for object construction.
Daniel@0: \f5dtinsert()\fP returns the new object, a matching object as noted,
Daniel@0: or \f5NULL\fP on error.
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* dtdelete(Dt_t* dt, Void_t* obj)"
Daniel@0: If \f5obj\fP is not \f5NULL\fP, the first object matching it is deleted.
Daniel@0: If \f5obj\fP is \f5NULL\fP, methods \f5Dtstack\fP and \f5Dtqueue\fP
Daniel@0: delete respectively stack top or queue head while other methods do nothing.
Daniel@0: See \f5Dtdisc_t.freef\fP for object destruction.
Daniel@0: \f5dtdelete()\fP returns the deleted object (even if it was deallocated)
Daniel@0: or \f5NULL\fP on error.
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* dtsearch(Dt_t* dt, Void_t* obj)"
Daniel@0: .Ss "  Void_t* dtmatch(Dt_t* dt, Void_t* key)"
Daniel@0: These functions find an object matching \f5obj\fP or \f5key\fP either from \f5dt\fP or
Daniel@0: from some dictionary accessible from \f5dt\fP via a viewpath (see \f5dtview()\fP.)
Daniel@0: \f5dtsearch()\fP and \f5dtmatch()\fP return the matching object or
Daniel@0: \f5NULL\fP on failure.
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* dtfirst(Dt_t* dt)"
Daniel@0: .Ss "  Void_t* dtnext(Dt_t* dt, Void_t* obj)"
Daniel@0: \f5dtfirst()\fP returns the first object in \f5dt\fP.
Daniel@0: \f5dtnext()\fP returns the object following \f5obj\fP.
Daniel@0: Objects are ordered based on the storage method in use.
Daniel@0: For \f5Dtoset\fP and \f5Dtobag\fP, objects are ordered by object comparisons.
Daniel@0: For \f5Dtstack\fP, objects are ordered in reverse order of insertion.
Daniel@0: For \f5Dtqueue\fP, objects are ordered in order of insertion.
Daniel@0: For \f5Dtlist\fP, objects are ordered by list position.
Daniel@0: For \f5Dtset\fP and \f5Dtbag\fP,
Daniel@0: objects use some internal ordering which
Daniel@0: may change on any search, insert, or delete operations.
Daniel@0: Therefore, these operations should not be used
Daniel@0: during a walk on a dictionary using either \f5Dtset\fP or \f5Dtbag\fP.
Daniel@0: .PP
Daniel@0: Objects in a dictionary or a viewpath can be walked using 
Daniel@0: a \f5for(;;)\fP loop as below.
Daniel@0: Note that only one loop can be used at a time per dictionary.
Daniel@0: Concurrent or nested loops may result in unexpected behaviors.
Daniel@0: .Cs
Daniel@0:     for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))
Daniel@0: .Ce
Daniel@0: .Ss "  Void_t* dtlast(Dt_t* dt)"
Daniel@0: .Ss "  Void_t* dtprev(Dt_t* dt, Void_t* obj)"
Daniel@0: \f5dtlast()\fP and \f5dtprev()\fP are like \f5dtfirst()\fP and \f5dtnext()\fP
Daniel@0: but work in reverse order.
Daniel@0: Note that dictionaries on a viewpath are still walked in order
Daniel@0: but objects in each dictionary are walked in reverse order.
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* dtfinger(Dt_t* dt)"
Daniel@0: This function returns the \fIcurrent object\fP of \f5dt\fP, if any.
Daniel@0: The current object is defined after a successful call to one of
Daniel@0: \f5dtsearch()\fP, \f5dtmatch()\fP, \f5dtinsert()\fP,
Daniel@0: \f5dtfirst()\fP, \f5dtnext()\fP, \f5dtlast()\fP, or \f5dtprev()\fP.
Daniel@0: As a side effect of this implementation of \fICdt\fP,
Daniel@0: when a dictionary is based on \f5Dtoset\fP and \f5Dtobag\fP,
Daniel@0: the current object is always defined and is the root of the tree.
Daniel@0: .PP
Daniel@0: .Ss "  Void_t* dtrenew(Dt_t* dt, Void_t* obj)"
Daniel@0: This function repositions and perhaps rehashes
Daniel@0: an object \f5obj\fP after its key has been changed.
Daniel@0: \f5dtrenew()\fP only works if \f5obj\fP is the current object (see \f5dtfinger()\fP).
Daniel@0: .PP
Daniel@0: .Ss "  dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)"
Daniel@0: This function calls \f5(*userf)(walk,obj,data)\fP on each object in \f5dt\fP and
Daniel@0: other dictionaries viewable from it.
Daniel@0: \f5walk\fP is the dictionary containing \f5obj\fP.
Daniel@0: If \f5userf()\fP returns a \f5<0\fP value,
Daniel@0: \f5dtwalk()\fP terminates and returns the same value.
Daniel@0: \f5dtwalk()\fP returns \f50\fP on completion.
Daniel@0: .PP
Daniel@0: .Ss "  Dtlink_t* dtflatten(Dt_t* dt)"
Daniel@0: .Ss "  Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)"
Daniel@0: .Ss "  Void_t* dtobj(Dt_t* dt, Dtlink_t* link)"
Daniel@0: Using \f5dtfirst()/dtnext()\fP or \f5dtlast()/dtprev()\fP
Daniel@0: to walk a single dictionary can incur significant cost due to function calls.
Daniel@0: For efficient walking of a single directory (i.e., no viewpathing),
Daniel@0: \f5dtflatten()\fP and \f5dtlink()\fP can be used.
Daniel@0: Objects in \f5dt\fP are made into a linked list and walked as follows:
Daniel@0: .Cs
Daniel@0:     for(link = dtflatten(dt); link; link = dtlink(dt,link) )
Daniel@0: .Ce
Daniel@0: .PP
Daniel@0: Note that \f5dtflatten()\fP returns a list of type \f5Dtlink_t*\fP,
Daniel@0: not \f5Void_t*\fP. That is, it returns a dictionary holder pointer,
Daniel@0: not a user object pointer
Daniel@0: (although both are the same if the discipline field \f5link\fP is non-negative.)
Daniel@0: The macro function \f5dtlink()\fP
Daniel@0: returns the dictionary holder object following \f5link\fP.
Daniel@0: The macro function \f5dtobj(dt,link)\fP
Daniel@0: returns the user object associated with \f5link\fP,
Daniel@0: Beware that the flattened object list is unflattened on any
Daniel@0: dictionary operations other than \f5dtlink()\fP.
Daniel@0: .PP
Daniel@0: .Ss "  Dtlink_t* dtextract(Dt_t* dt)"
Daniel@0: .Ss "  int dtrestore(Dt_t* dt, Dtlink_t* link)"
Daniel@0: \f5dtextract()\fP extracts all objects from \f5dt\fP and makes it appear empty.
Daniel@0: \f5dtrestore()\fP repopulates \f5dt\fP with
Daniel@0: objects previously obtained via \f5dtextract()\fP.
Daniel@0: \f5dtrestore()\fP will fail if \f5dt\fP is not empty.
Daniel@0: These functions can be used
Daniel@0: to share a same \f5dt\fP handle among many sets of objects.
Daniel@0: They are useful to reduce dictionary overhead
Daniel@0: in an application that creates concurrently many dictionaries.
Daniel@0: It is important that the same discipline and method are in use at both
Daniel@0: extraction and restoration. Otherwise, undefined behaviors may result.
Daniel@0: .PP
Daniel@0: .Ss "DICTIONARY INFORMATION"
Daniel@0: .PP
Daniel@0: .Ss "  Dt_t* dtvnext(Dt_t* dt)"
Daniel@0: This returns the dictionary that \f5dt\fP is viewing, if any.
Daniel@0: .Ss "  int dtvcount(Dt_t* dt)"
Daniel@0: This returns the number of dictionaries that view \f5dt\fP.
Daniel@0: .Ss "  Dt_t* dtvhere(Dt_t* dt)"
Daniel@0: This returns the dictionary \f5v\fP viewable from \f5dt\fP
Daniel@0: where an object was found from the most recent search or walk operation.
Daniel@0: .Ss "  int dtsize(Dt_t* dt)"
Daniel@0: This function returns the number of objects stored in \f5dt\fP.
Daniel@0: .PP
Daniel@0: .Ss "  int dtstat(Dt_t *dt, Dtstat_t* st, int all)"
Daniel@0: This function reports dictionary statistics.
Daniel@0: If \f5all\fP is non-zero, all fields of \f5st\fP are filled.
Daniel@0: Otherwise, only the \f5dt_type\fP and \f5dt_size\fP fields are filled.
Daniel@0: It returns \f50\fP on success and \f5-1\fP on error.
Daniel@0: .PP
Daniel@0: \f5Dtstat_t\fP contains the below fields:
Daniel@0: .Tp
Daniel@0: \f5int dt_type\fP:
Daniel@0: This is one of \f5DT_SET\fP, \f5DT_BAG\fP, \f5DT_OSET\fP, \f5DT_OBAG\fP,
Daniel@0: \f5DT_LIST\fP, \f5DT_STACK\fP, and \f5DT_QUEUE\fP.
Daniel@0: .Tp
Daniel@0: \f5int dt_size\fP:
Daniel@0: This contains the number of objects in the dictionary.
Daniel@0: .Tp
Daniel@0: \f5int dt_n\fP:
Daniel@0: For \f5Dtset\fP and \f5Dtbag\fP,
Daniel@0: this is the number of non-empty chains in the hash table.
Daniel@0: For \f5Dtoset\fP and \f5Dtobag\fP,
Daniel@0: this is the deepest level in the tree (counting from zero.)
Daniel@0: Each level in the tree contains all nodes of equal distance from the root node.
Daniel@0: \f5dt_n\fP and the below two fields are undefined for other methods.
Daniel@0: .Tp
Daniel@0: \f5int dt_max\fP:
Daniel@0: For \f5Dtbag\fP and \f5Dtset\fP, this is the size of a largest chain.
Daniel@0: For \f5Dtoset\fP and \f5Dtobag\fP, this is the size of a largest level.
Daniel@0: .Tp
Daniel@0: \f5int* dt_count\fP:
Daniel@0: For \f5Dtset\fP and \f5Dtbag\fP,
Daniel@0: this is the list of counts for chains of particular sizes.
Daniel@0: For example, \f5dt_count[1]\fP is the number of chains of size \f51\fP.
Daniel@0: For \f5Dtoset\fP and \f5Dtobag\fP, this is the list of sizes of the levels.
Daniel@0: For example, \f5dt_count[1]\fP is the size of level \f51\fP.
Daniel@0: .PP
Daniel@0: .Ss "HASH FUNCTIONS"
Daniel@0: .PP
Daniel@0: .Ss "  unsigned int dtcharhash(unsigned int h, char c)"
Daniel@0: .Ss "  unsigned int dtstrhash(unsigned int h, char* str, int n)"
Daniel@0: These functions compute hash values from bytes or strings.
Daniel@0: \f5dtcharhash()\fP computes a new hash value from byte \f5c\fP and seed value \f5h\fP.
Daniel@0: \f5dtstrhash()\fP computes a new hash value from string \f5str\fP and seed value \f5h\fP.
Daniel@0: If \f5n\fP is positive, \f5str\fP is a byte array of length \f5n\fP;
Daniel@0: otherwise, \f5str\fP is a null-terminated string.
Daniel@0: .PP
Daniel@0: .SH IMPLEMENTATION NOTES
Daniel@0: \f5Dtset\fP and \f5Dtbag\fP are based on hash tables with
Daniel@0: move-to-front collision chains.
Daniel@0: \f5Dtoset\fP and \f5Dtobag\fP are based on top-down splay trees.
Daniel@0: \f5Dtlist\fP, \f5Dtstack\fP and \f5Dtqueue\fP are based on doubly linked list.
Daniel@0: .PP
Daniel@0: .SH AUTHOR
Daniel@0: Kiem-Phong Vo, kpv@research.att.com