path: root/src/lib/libast/man/cdt.3

.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