da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.TH LIBCDT 3
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\fBCdt\fR \- container data types
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.SH SYNOPSIS
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.ta 1.0i 2.0i 3.0i 4.0i 5.0i
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DICTIONARY TYPES"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DICTIONARY CONTROL"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtclose(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinvoid dtclear(dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* dtmethod(Dt_t* dt, const Dtmethod_t* meth);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dtview(Dt_t* dt, Dt_t* view);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dttreeset(Dt_t* dt, int minp, int balance);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "STORAGE METHODS"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* Dtset;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* Dtbag;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* Dtoset;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* Dtobag;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* Dtlist;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* Dtstack;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtmethod_t* Dtqueue;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DISCIPLINE"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTOFFSET(struct_s,member)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef Void_t* (*Dtmake_f)(Dt_t*, Void_t*, Dtdisc_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef void (*Dtfree_f)(Dt_t*, Void_t*, Dtdisc_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef int (*Dtcompar_f)(Dt_t*, Void_t*, Void_t*, Dtdisc_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef unsigned int (*Dthash_f)(Dt_t*, Void_t*, Dtdisc_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef Void_t* (*Dtmemory_f)(Dt_t*, Void_t*, size_t, Dtdisc_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef int (*Dtevent_f)(Dt_t*, int, Void_t*, Dtdisc_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "OBJECT OPERATIONS"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtinsert(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtdelete(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtattach(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtdetach(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtsearch(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtmatch(Dt_t* dt, Void_t* key);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtfirst(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtnext(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtlast(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtprev(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtfinger(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtrenew(Dt_t* dt, Void_t* obj);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtlink_t* dtflatten(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtlink_t* dtlink(Dt_t*, Dtlink_t* link);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtobj(Dt_t* dt, Dtlink_t* link);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtlink_t* dtextract(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtrestore(Dt_t* dt, Dtlink_t* link);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTTREESEARCH(Dt_t* dt, Void_t* obj, action)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTTREEMATCH(Dt_t* dt, Void_t* key, action)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DICTIONARY STATUS"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dtvnext(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtvcount(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dtvhere(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtsize(Dt_t* dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtstat(Dt_t* dt, Dtstat_t*, int all);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "HASH FUNCTIONS"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinunsigned int dtstrhash(unsigned int h, char* str, int n);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinunsigned int dtcharhash(unsigned int h, unsigned char c);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.SH DESCRIPTION
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\fICdt\fP manages run-time dictionaries using standard container data types:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinunordered set/multiset, ordered set/multiset, list, stack, and queue.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DICTIONARY TYPES"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t*"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis type is used to pass objects between \fICdt\fP and application code.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Void_t\fP is defined as \f5void\fP for ANSI-C and C++
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinand \f5char\fP for other compilation environments.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dt_t"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis is the type of a dictionary handle.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtdisc_t"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis defines the type of a discipline structure which describes
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinobject lay-out and manipulation functions.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtmethod_t"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis defines the type of a container method.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtlink_t"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis is the type of a dictionary object holder (see \f5dtdisc()\fP.)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtstat_t"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis is the type of a structure to return dictionary statistics (see \f5dtstat()\fP.)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DICTIONARY CONTROL"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis creates a new dictionary.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5disc\fP is a discipline structure to describe object format.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5meth\fP specifies a manipulation method.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtopen()\fP returns the new dictionary or \f5NULL\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSee also the events \f5DT_OPEN\fP and \f5DT_ENDOPEN\fP below.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int dtclose(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis deletes \f5dt\fP and its objects.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinNote that \f5dtclose()\fP fails if \f5dt\fP is being viewed by
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinsome other dictionaries (see \f5dtview()\fP).
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtclose()\fP returns \f50\fP on success and \f5-1\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSee also the events \f5DT_CLOSE\fP and \f5DT_ENDCLOSE\fP below.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " void dtclear(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis deletes all objects in \f5dt\fP without closing \f5dt\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtmethod_t dtmethod(Dt_t* dt, const Dtmethod_t* meth)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5meth\fP is \f5NULL\fP, \f5dtmethod()\fP returns the current method.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinOtherwise, it changes the storage method of \f5dt\fP to \f5meth\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObject order remains the same during a
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinmethod switch among \f5Dtlist\fP, \f5Dtstack\fP and \f5Dtqueue\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSwitching to and from \f5Dtset/Dtbag\fP and \f5Dtoset/Dtobag\fP may cause
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinobjects to be rehashed, reordered, or removed as the case requires.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtmethod()\fP returns the previous method or \f5NULL\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5disc\fP is \f5NULL\fP, \f5dtdisc()\fP returns the current discipline.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinOtherwise, it changes the discipline of \f5dt\fP to \f5disc\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects may be rehashed, reordered, or removed as appropriate.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5type\fP can be any bit combination of \f5DT_SAMECMP\fP and \f5DT_SAMEHASH\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_SAMECMP\fP means that objects will compare exactly the same as before
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthus obviating the need for reordering or removing new duplicates.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_SAMEHASH\fP means that hash values of objects remain the same
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthus obviating the need to rehash.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtdisc()\fP returns the previous discipline on success
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinand \f5NULL\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dt_t* dtview(Dt_t* dt, Dt_t* view)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinA viewpath allows a search or walk starting from a dictionary to continue to another.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtview()\fP first terminates any current view from \f5dt\fP to another dictionary.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThen, if \f5view\fP is \f5NULL\fP, \f5dtview\fP returns the terminated view dictionary.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5view\fP is not \f5NULL\fP, a viewpath from \f5dt\fP to \f5view\fP is established.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtview()\fP returns \f5dt\fP on success and \f5NULL\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf two dictionaries on the same viewpath have the same values for the discipline fields
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtdisc_t.link\fP, \f5Dtdisc_t.key\fP, \f5Dtdisc_t.size\fP, and \f5Dtdisc_t.hashf\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinit is expected that key hashing will be the same.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf not, undefined behaviors may result during a search or a walk.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int dttreeset(Dt_t* dt, int minp, int balance)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function only applies to dictionaries operated under the method \f5Dtoset\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinwhich uses top-down splay trees (see below). It returns 0 on success and -1 on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5minp\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis parameter defines the minimum path length before a search path is adjusted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor example, \f5minp\fP equal 0 would mean that search paths are always adjusted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5minp\fP is negative, the minimum search path is internally computed based
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinon a function of the current dictionary size. This computed value is such that
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinif the tree is balanced, it will never require adjusting.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5balance\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf this is non-zero, the tree will be made balanced.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "STORAGE METHODS"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinStorage methods are of type \f5Dtmethod_t*\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\fICdt\fP supports the following methods:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtoset"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtobag"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects are ordered by comparisons.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtoset\fP keeps unique objects.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtobag\fP allows repeatable objects.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtset"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtbag"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects are unordered.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtset\fP keeps unique objects.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtbag\fP allows repeatable objects and always keeps them together
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin(note the effect on dictionary walking.)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThese methods use a hash table with chaining to manage the objects.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSee also the event \f5DT_HASHSIZE\fP below on how to manage hash table
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinresizing when objects are inserted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtlist"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects are kept in a list.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinNew objects are inserted either
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinin front of \fIcurrent object\fP (see \f5dtfinger()\fP) if this is defined
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinor at list front if there is no current object.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtstack"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects are kept in a stack, i.e., in reverse order of insertion.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThus, the last object inserted is at stack top
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinand will be the first to be deleted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtqueue"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects are kept in a queue, i.e., in order of insertion.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThus, the first object inserted is at queue head
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinand will be the first to be deleted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DISCIPLINE"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObject format and associated management functions are
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chindefined in the type \f5Dtdisc_t\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin typedef struct
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { int key, size;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtmake_f makef;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtfree_f freef;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtcompar_f comparf;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dthash_f hashf;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtmemory_f memoryf;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtevent_f eventf;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin } Dtdisc_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int key, size"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinEach object \f5obj\fP is identified by a key used for object comparison or hashing.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5key\fP should be non-negative and defines an offset into \f5obj\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5size\fP is negative, the key is a null-terminated
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstring with starting address \f5*(Void_t**)((char*)obj+key)\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5size\fP is zero, the key is a null-terminated string with starting address
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5(Void_t*)((char*)obj+key)\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFinally, if \f5size\fP is positive, the key is a byte array of length \f5size\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstarting at \f5(Void_t*)((char*)obj+key)\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int link"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinLet \f5obj\fP be an object to be inserted into \f5dt\fP as discussed below.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5link\fP is negative, an internally allocated object holder is used
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinto hold \f5obj\fP. Otherwise, \f5obj\fP should have
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968china \f5Dtlink_t\fP structure embedded \f5link\fP bytes into it,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chini.e., at address \f5(Dtlink_t*)((char*)obj+link)\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5makef\fP is not \f5NULL\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtinsert(dt,obj)\fP will call it
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinto make a copy of \f5obj\fP suitable for insertion into \f5dt\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5makef\fP is \f5NULL\fP, \f5obj\fP itself will be inserted into \f5dt\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf not \f5NULL\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5freef\fP is used to destroy data associated with \f5obj\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf not \f5NULL\fP, \f5comparf\fP is used to compare two keys.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIts return value should be \f5<0\fP, \f5=0\fP, or \f5>0\fP to indicate
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinwhether \f5key1\fP is smaller, equal to, or larger than \f5key2\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinAll three values are significant for method \f5Dtoset\fP and \f5Dtobag\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor other methods, a zero value
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinindicates equality and a non-zero value indicates inequality.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5(*comparf)()\fP is \f5NULL\fP, an internal function is used
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinto compare the keys as defined by the \f5Dtdisc_t.size\fP field.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf not \f5NULL\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5hashf\fP is used to compute the hash value of \f5key\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIt is required that keys compared equal will also have same hash values.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5hashf\fP is \f5NULL\fP, an internal function is used to hash
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe key as defined by the \f5Dtdisc_t.size\fP field.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf not \f5NULL\fP, \f5memoryf\fP is used to allocate and free memory.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinWhen \f5addr\fP is \f5NULL\fP, a memory segment of size \f5size\fP is requested.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5addr\fP is not \f5NULL\fP and \f5size\fP is zero, \f5addr\fP is to be freed.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5addr\fP is not \f5NULL\fP and \f5size\fP is positive,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5addr\fP is to be resized to the given size.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5memoryf\fP is \f5NULL\fP, \fImalloc(3)\fP is used.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinWhen dictionaries share memory,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968china record of the first allocated memory segment should be kept
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinso that it can be used to initialize other dictionaries (see below.)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf not \f5NULL\fP, \f5eventf\fP announces various events.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinEach event may have particular handling of the return values from \f5eventf\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinBut a negative return value typically means failure.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFollowing are the events:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_OPEN\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dt\fP is being opened.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5eventf\fP returns negative, the opening process terminates with failure.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5eventf\fP returns zero, the opening process proceeds normally.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinA positive return value indicates special treatment of memory as follows.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5*(Void_t**)data\fP is set to point to some memory segment
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinas discussed in \f5memoryf\fP, that segment of memory is used to start
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe dictionary. If \f5*(Void_t**)data\fP is not set, this indicates that
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtopen()\fP should allocate the dictionary handle itself with
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5memoryf\fP so that all memories pertained to the dictionary are allocated
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinvia this function.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_ENDOPEN\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis event announces that \f5dtopen()\fP has successfully opened
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968china dictionary and is about to return. The \f5data\fP argument of
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5eventf\fP should be the new dictionary handle itself.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_CLOSE\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dt\fP is about to be closed. If \f5eventf\fP returns zero,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe closing process proceeds normally. This means that all objects
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinin the dictionary will be deleted and all associated memories freed.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5eventf\fP returns a positive value, objects will not be deleted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinHowever, the dictionary handle itself will still be deallocated
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinunless it was allocated via \f5memoryf\fP during \f5dtopen()\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis allows shared/persistent memory dictionaries to retain
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe relevant memories across dictionary openings and closings.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_ENDCLOSE\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis event announces that \f5dtclose()\fP has successfully closed
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968china dictionary and is about to return.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_DISC\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe discipline of \f5dt\fP is being changed to a new one given in
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5(Dtdisc_t*)data\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_METH\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe method of \f5dt\fP is being changed to a new one given in
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5(Dtmethod_t*)data\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_HASHSIZE\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe hash table (for \f5Dtset\fP and \f5Dtbag\fP) is being resized.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIn this case, \f5*(int*)data\fP has the current size of the table.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe application can set the new table size by first changing
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5*(int*)data\fP to the desired size, then return a positive value.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe application can also fix the table size at the current value
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinforever by setting \f5*(int*)data\fP to a negative value, then
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinagain return a positive value. A non-positive return value from
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe event handling function means that Cdt will be responsible
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinfor choosing the hash table size.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "#define DTOFFSET(struct_s,member)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis macro function computes the offset of \f5member\fP from the start
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinof structure \f5struct_s\fP. It is useful for getting the offset of
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968china \f5Dtlink_t\fP embedded inside an object.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "#define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis macro function initializes the discipline pointed to by \f5disc\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinwith the given values.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "OBJECT OPERATIONS"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtinsert(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis inserts an object prototyped by \f5obj\fP into \f5dt\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf there is an existing object in \f5dt\fP matching \f5obj\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinand the storage method is \f5Dtset\fP or \f5Dtoset\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtinsert()\fP will simply return the matching object.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinOtherwise, a new object is inserted according to the method in use.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSee \f5Dtdisc_t.makef\fP for object construction.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtinsert()\fP returns the new object, a matching object as noted,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinor \f5NULL\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtdelete(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5obj\fP is \f5NULL\fP, methods \f5Dtstack\fP and \f5Dtqueue\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chindelete respectively stack top or queue head while other methods do nothing.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5obj\fP is not \f5NULL\fP, there are two cases.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf the method in use is not \f5Dtbag\fP or \f5Dtobag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe first object matching \f5obj\fP is deleted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinOn the other hand, if the method in use is \f5Dtbag\fP or \f5Dtobag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe library check to see if \f5obj\fP is in the dictionary and delete it.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5obj\fP is not in the dictionary, some object matching it will be deleted.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSee \f5Dtdisc_t.freef\fP for object destruction.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtdelete()\fP returns the deleted object (even if it was deallocated)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinor \f5NULL\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtattach(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function is similar to \f5dtinsert()\fP but \f5obj\fP itself
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinwill be inserted into \f5dt\fP even if a discipline
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinfunction \f5makef\fP is defined.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtdetach(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function is similar to \f5dtdelete()\fP but the object to be deleted
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinfrom \f5dt\fP will not be freed (via the discipline \f5freef\fP function).
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtsearch(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtmatch(Dt_t* dt, Void_t* key)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThese functions find an object matching \f5obj\fP or \f5key\fP either from \f5dt\fP or
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinfrom some dictionary accessible from \f5dt\fP via a viewpath (see \f5dtview()\fP.)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtsearch()\fP and \f5dtmatch()\fP return the matching object or
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5NULL\fP on failure.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtfirst(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtnext(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtfirst()\fP returns the first object in \f5dt\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtnext()\fP returns the object following \f5obj\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects are ordered based on the storage method in use.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtoset\fP and \f5Dtobag\fP, objects are ordered by object comparisons.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtstack\fP, objects are ordered in reverse order of insertion.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtqueue\fP, objects are ordered in order of insertion.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtlist\fP, objects are ordered by list position.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtset\fP and \f5Dtbag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinobjects are ordered by some internal order (more below).
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThus, objects in a dictionary or a viewpath can be walked using
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968china \f5for(;;)\fP loop as below.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinWhen a dictionary uses \f5Dtset\fP or \f5Dtbag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe object order is determined upon a call to \f5dtfirst()\fP/\f5dtlast()\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis order is frozen until a call \f5dtnext()\fP/\f5dtprev()\fP returns \f5NULL\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinor when these same functions are called with a \f5NULL\fP object argument.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIt is important that a \f5dtfirst()/dtlast()\fP call be
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinbalanced by a \f5dtnext()/dtprev()\fP call as described.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinNested loops will require multiple balancing, once per loop.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf loop balancing is not done carefully, either performance is degraded
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinor unexpected behaviors may result.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtlast(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtprev(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtlast()\fP and \f5dtprev()\fP are like \f5dtfirst()\fP and \f5dtnext()\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinbut work in reverse order.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinNote that dictionaries on a viewpath are still walked in order
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinbut objects in each dictionary are walked in reverse order.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtfinger(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function returns the \fIcurrent object\fP of \f5dt\fP, if any.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe current object is defined after a successful call to one of
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtsearch()\fP, \f5dtmatch()\fP, \f5dtinsert()\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtfirst()\fP, \f5dtnext()\fP, \f5dtlast()\fP, or \f5dtprev()\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinAs a side effect of this implementation of \fICdt\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinwhen a dictionary is based on \f5Dtoset\fP and \f5Dtobag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe current object is always defined and is the root of the tree.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtrenew(Dt_t* dt, Void_t* obj)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function repositions and perhaps rehashes
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinan object \f5obj\fP after its key has been changed.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtrenew()\fP only works if \f5obj\fP is the current object (see \f5dtfinger()\fP).
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function calls \f5(*userf)(walk,obj,data)\fP on each object in \f5dt\fP and
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinother dictionaries viewable from it.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5walk\fP is the dictionary containing \f5obj\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5userf()\fP returns a \f5<0\fP value,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtwalk()\fP terminates and returns the same value.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtwalk()\fP returns \f50\fP on completion.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtlink_t* dtflatten(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Void_t* dtobj(Dt_t* dt, Dtlink_t* link)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinUsing \f5dtfirst()/dtnext()\fP or \f5dtlast()/dtprev()\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinto walk a single dictionary can incur significant cost due to function calls.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor efficient walking of a single directory (i.e., no viewpathing),
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtflatten()\fP and \f5dtlink()\fP can be used.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinObjects in \f5dt\fP are made into a linked list and walked as follows:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(link = dtflatten(dt); link; link = dtlink(dt,link) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinNote that \f5dtflatten()\fP returns a list of type \f5Dtlink_t*\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinnot \f5Void_t*\fP. That is, it returns a dictionary holder pointer,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinnot a user object pointer
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin(although both are the same if the discipline field \f5link\fP is zero.)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe macro function \f5dtlink()\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreturns the dictionary holder object following \f5link\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe macro function \f5dtobj(dt,link)\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreturns the user object associated with \f5link\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinBeware that the flattened object list is unflattened on any
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chindictionary operations other than \f5dtlink()\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dtlink_t* dtextract(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int dtrestore(Dt_t* dt, Dtlink_t* link)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtextract()\fP extracts all objects from \f5dt\fP and makes it appear empty.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtrestore()\fP repopulates \f5dt\fP with
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinobjects previously obtained via \f5dtextract()\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtrestore()\fP will fail if \f5dt\fP is not empty.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThese functions can be used
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinto share a same \f5dt\fP handle among many sets of objects.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThey are useful to reduce dictionary overhead
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinin an application that creates many concurrent dictionaries.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIt is important that the same discipline and method are in use at both
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextraction and restoration. Otherwise, undefined behaviors may result.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " #define DTTREESEARCH(Dt_t* dt, Void_t* obj, action)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " #define DTTREEMATCH(Dt_t* dt, Void_t* key, action)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThese macro functions are analogues of \f5dtsearch()\fP and \f5dtmatch()\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinbut they can only be used on a dictionary based on a binary
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinsearch tree, i.e., \f5Dtoset\fP or \f5Dtobag\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5obj\fP or \f5key\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThese are used to find a matching object. If there is no match,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthe result is \f5NULL\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5action\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThe matching object \f5o\fP (which may be \f5NULL\fP) will be processed as follow:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin action (o);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSince \f5action\fP is used verbatim, it can be any C code
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinfragment combinable with \f5(o)\fP to form a syntactically correct C statement.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor example, suppose that the matching object is an integer, the below code
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinaccumulates the integer value in a variable \f5total\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin DTTREEMATCH(dt, key, total += (int));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "DICTIONARY INFORMATION"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dt_t* dtvnext(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis returns the dictionary that \f5dt\fP is viewing, if any.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int dtvcount(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis returns the number of dictionaries that view \f5dt\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " Dt_t* dtvhere(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis returns the dictionary \f5v\fP viewable from \f5dt\fP
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinwhere an object was found from the most recent search or walk operation.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int dtsize(Dt_t* dt)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function returns the number of objects stored in \f5dt\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " int dtstat(Dt_t *dt, Dtstat_t* st, int all)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis function reports dictionary statistics.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5all\fP is non-zero, all fields of \f5st\fP are filled.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinOtherwise, only the \f5dt_type\fP and \f5dt_size\fP fields are filled.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIt returns \f50\fP on success and \f5-1\fP on error.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtstat_t\fP contains the below fields:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5int dt_type\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis is one of \f5DT_SET\fP, \f5DT_BAG\fP, \f5DT_OSET\fP, \f5DT_OBAG\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5DT_LIST\fP, \f5DT_STACK\fP, and \f5DT_QUEUE\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5int dt_size\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThis contains the number of objects in the dictionary.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5int dt_n\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtset\fP and \f5Dtbag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthis is the number of non-empty chains in the hash table.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtoset\fP and \f5Dtobag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthis is the deepest level in the tree (counting from zero.)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinEach level in the tree contains all nodes of equal distance from the root node.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dt_n\fP and the below two fields are undefined for other methods.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5int dt_max\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtbag\fP and \f5Dtset\fP, this is the size of a largest chain.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtoset\fP and \f5Dtobag\fP, this is the size of a largest level.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5int* dt_count\fP:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtset\fP and \f5Dtbag\fP,
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinthis is the list of counts for chains of particular sizes.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor example, \f5dt_count[1]\fP is the number of chains of size \f51\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor \f5Dtoset\fP and \f5Dtobag\fP, this is the list of sizes of the levels.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinFor example, \f5dt_count[1]\fP is the size of level \f51\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss "HASH FUNCTIONS"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " unsigned int dtcharhash(unsigned int h, char c)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.Ss " unsigned int dtstrhash(unsigned int h, char* str, int n)"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinThese functions compute hash values from bytes or strings.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtcharhash()\fP computes a new hash value from byte \f5c\fP and seed value \f5h\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5dtstrhash()\fP computes a new hash value from string \f5str\fP and seed value \f5h\fP.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinIf \f5n\fP is positive, \f5str\fP is a byte array of length \f5n\fP;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinotherwise, \f5str\fP is a null-terminated string.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin.SH IMPLEMENTATION NOTES
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtset\fP and \f5Dtbag\fP are based on hash tables with
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinmove-to-front collision chains.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtoset\fP and \f5Dtobag\fP are based on top-down splay trees.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin\f5Dtlist\fP, \f5Dtstack\fP and \f5Dtqueue\fP are based on doubly linked list.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinKiem-Phong Vo, kpv@research.att.com