Cdt manages run-time dictionaries using standard container data types: unordered set/multiset, ordered
set/multiset, list, stack, and queue.
DICTIONARYTYPESDt_t
This is the type of a dictionary handle.
Dtdisc_t
This defines the type of a discipline structure which describes object lay-out and manipulation
functions.
Dtmethod_t
This defines the type of a container method.
Dtlink_t
This is the type of a dictionary object holder (see dtdisc().)Dtstat_t
This is the type of a structure to return dictionary statistics (see dtstat().)DICTIONARYCONTROLDt_t*dtopen(constDtdisc_t*disc,constDtmethod_t*meth)
This creates a new dictionary. disc isadisciplinestructuretodescribeobjectformat.meth specifies
a manipulation method. dtopen() returnsthenewdictionaryorNULL on error. See also the events
DT_OPEN andDT_ENDOPEN below.
intdtclose(Dt_t*dt)
This deletes dt anditsobjects.Notethatdtclose() fails if dt isbeingviewedbysomeotherdictionaries(seedtview()). dtclose() returns0 on success and -1 onerror.SeealsotheeventsDT_CLOSE and DT_ENDCLOSE below.voiddtclear(Dt_t*dt)
This deletes all objects in dt withoutclosingdt.
Dtmethod_tdtmethod(Dt_t*dt,constDtmethod_t*meth)
If meth isNULL, dtmethod() returnsthecurrentmethod.Otherwise,itchangesthestoragemethodofdt
to meth.ObjectorderremainsthesameduringamethodswitchamongDtlist, Dtstack,Dtqueue and
Dtdeque.SwitchingtoandfromDtset/Dtbag and Dtoset/Dtobag maycauseobjectstoberehashed,reordered,orremovedasthecaserequires.dtmethod() returns the previous method or NULL onerror.Dtdisc_t*dtdisc(Dt_t*dt,constDtdisc_t*disc,inttype)
If disc isNULL, dtdisc() returnsthecurrentdiscipline.Otherwise,itchangesthedisciplineofdt to
disc.Objectsmayberehashed,reordered,orremovedasappropriate.type can be any bit combination of
DT_SAMECMP andDT_SAMEHASH. DT_SAMECMP meansthatobjectswillcompareexactlythesameasbeforethusobviatingtheneedforreorderingorremovingnewduplicates.DT_SAMEHASH means that hash values of
objects remain the same thus obviating the need to rehash. dtdisc() returnsthepreviousdisciplineonsuccessandNULL on error.
Dt_t*dtview(Dt_t*dt,Dt_t*view)
A viewpath allows a search or walk starting from a dictionary to continue to another. dtview() firstterminatesanycurrentviewfromdt to another dictionary. Then, if view isNULL, dtview returnstheterminatedviewdictionary.Ifview is not NULL,aviewpathfromdt to view isestablished.dtview()
returns dt onsuccessandNULL on error.
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.
STORAGEMETHODS
Storage methods are of type Dtmethod_t*. Cdt supports the following methods:
DtosetDtobag
Objects are ordered by comparisons. Dtoset keepsuniqueobjects.Dtobag allows repeatable objects.
DtsetDtbag
Objects are unordered. Dtset keepsuniqueobjects.Dtbag allows repeatable objects and always keeps
them together (note the effect on dictionary walking.) These methods use a hash table with chaining to
manage the objects. See also the event DT_HASHSIZE belowonhowtomanagehashtableresizingwhenobjectsareinserted.Dtlist
Objects are kept in a list. The call dtinsert() insertsanewobjectinfrontofthecurrentobject(seedtfinger())ifitisdefinedoratlistfrontifnocurrentobjectisdefined.Similarly,thecalldtappend()appendsanewobjectafterthecurrentobject(seedtfinger())ifitisdefinedoratlistendifnocurrentobjectisdefined.Dtdeque
Objects are kept in a deque. This is similar to Dtlist exceptthatobjectsarealwaysinsertedatthefrontandappendedatthetailofthelist.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.
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.
DISCIPLINE
Object format and associated management functions are defined in the type Dtdisc_t:
typedef struct
{ int key, size;
int link;
Dtmake_f makef;
Dtfree_f freef;
Dtcompar_f comparf;
Dthash_f hashf;
Dtmemory_f memoryf;
Dtevent_f eventf;
} Dtdisc_t;
intkey,size
Each object obj isidentifiedbyakeyusedforobjectcomparisonorhashing.key should be non-negative
and defines an offset into obj.Ifsize is negative, the key is a null-terminated string with starting
address *(void**)((char*)obj+key).Ifsize is zero, the key is a null-terminated string with starting
address (void*)((char*)obj+key).Finally,ifsize is positive, the key is a byte array of length size
startingat(void*)((char*)obj+key).
intlink
Let obj beanobjecttobeinsertedintodt as discussed below. If link isnegative,aninternallyallocatedobjectholderisusedtoholdobj. Otherwise, obj shouldhaveaDtlink_t structure embedded
link bytesintoit,i.e.,ataddress(Dtlink_t*)((char*)obj+link).
void*(*makef)(Dt_t*dt,void*obj,Dtdisc_t*disc)
If makef isnotNULL, dtinsert(dt,obj) ordtappend() will call it to make a copy of obj suitableforinsertionintodt. If makef isNULL, obj itselfwillbeinsertedintodt.
void(*freef)(Dt_t*dt,void*obj,Dtdisc_t*disc)
If not NULL,freef is used to destroy data associated with obj.int(*comparf)(Dt_t*dt,void*key1,void*key2,Dtdisc_t*disc)
If not NULL,comparf is used to compare two keys. Its return value should be <0,=0, or >0 toindicatewhetherkey1 is smaller, equal to, or larger than key2.AllthreevaluesaresignificantformethodDtoset and Dtobag.Forothermethods,azerovalueindicatesequalityandanon-zerovalueindicatesinequality.If(*comparf)() is NULL,aninternalfunctionisusedtocomparethekeysasdefinedbytheDtdisc_t.size field.
unsignedint(*hashf)(Dt_t*dt,void*key,Dtdisc_t*disc)
If not NULL,hashf is used to compute the hash value of key.Itisrequiredthatkeyscomparedequalwillalsohavesamehashvalues.Ifhashf is NULL,aninternalfunctionisusedtohashthekeyasdefinedbytheDtdisc_t.size field.
void*(*memoryf)(Dt_t*dt,void*addr,size_tsize,Dtdisc_t*disc)
If not NULL,memoryf is used to allocate and free memory. When addr isNULL, a memory segment of size
size isrequested.Ifaddr is not NULL andsize is zero, addr istobefreed.Ifaddr is not NULL andsize is positive, addr istoberesizedtothegivensize.Ifmemoryf is NULL,malloc(3)isused.int(*eventf)(Dt_t*dt,inttype,void*data,Dtdisc_t*disc)
If not NULL,eventf announces various events. Each event may have particular handling of the return
values from eventf.Butanegativereturnvaluetypicallymeansfailure.Followingaretheevents:
DT_OPEN:
dt isbeingopened.Ifeventf returns negative, the opening process terminates with failure. If
eventf returnszero,theopeningprocessproceedsinadefaultmanner.Apositivereturnvalueindicatesspecialtreatmentofmemoryasfollows.If*(void**)data is set to point to some memory
segment as discussed in memoryf,thatsegmentofmemoryisusedtostartthedictionary.If*(void**)data is NULL,allmemoryincludingthatofthedictionaryhandleitselfwillbeallocatedviamemoryf.
DT_ENDOPEN:
This event announces that dtopen() has successfully opened a dictionary and is about to return.
The data argument of eventf should be the new dictionary handle itself.
DT_CLOSE:
dt is about to be closed. If eventf returns negative, the closing process stops immediately and
dtclose() returns -1. Objects in the dictionary are deleted only if eventf returns zero. The
dictionary handle itself is processed as follows. If it was allocated via malloc(), it will be
freed. If it was allocated via memoryf (see dtopen()) and eventf returns 0, a call to memoryf
will be issued to attempt freeing the handle. Otherwise, nothing will be done to its memory.
As should be clear from their description, the events DT_OPEN and DT_CLOSE are designed to be used
along with memoryf to manage the allocation and deallocation of dictionary and object memory
across dictionaries. In fact, they can be used to manage dictionaries based on shared and/or
persistent memory.
DT_ENDCLOSE:
This event announces that dtclose() has successfully closed a dictionary and is about to return.
DT_DISC:
The discipline of dt is being changed to a new one given in (Dtdisc_t*)data.
DT_METH:
The method of dt is being changed to a new one given in (Dtmethod_t*)data.
DT_HASHSIZE:
The hash table (for Dtset and Dtbag) is being resized. In this case, *(int*)data has the current
size of the table. The application can set the new table size by first changing *(int*)data to
the desired size, then return a positive value. The application can also fix the table size at
the current value forever by setting *(int*)data to a negative value, then again return a positive
value. A non-positive return value from the event handling function means that Cdt will be
responsible for choosing the hash table size.
#defineDTOFFSET(struct_s,member)
This macro function computes the offset of member fromthestartofstructurestruct_s. It is useful for
getting the offset of a Dtlink_t embeddedinsideanobject.#defineDTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)
This macro function initializes the discipline pointed to by disc withthegivenvalues.OBJECTOPERATIONSvoid*dtinsert(Dt_t*dt,void*obj)void*dtappend(Dt_t*dt,void*obj)
These functions add an object prototyped by obj intodt. dtinsert() anddtappend() perform the same
function for all methods except for Dtlist.SeeDtlist for details. If there is an existing object in dt
matchingobj and the storage method is Dtset orDtoset, dtinsert() anddtappend() will simply return the
matching object. Otherwise, a new object is inserted according to the method in use. See Dtdisc_t.makef
forobjectconstruction.ThenewobjectoramatchingobjectasnotedwillbereturnedonsuccesswhileNULL is returned on error.
void*dtdelete(Dt_t*dt,void*obj)
If obj isNULL, methods Dtstack andDtqueue delete respectively stack top or queue head while other
methods do nothing. If obj isnotNULL, there are two cases. If the method in use is not Dtbag orDtobag, the first object matching obj isdeleted.Ontheotherhand,ifthemethodinuseisDtbag or
Dtobag,thelibrarychecktoseeifobj is in the dictionary and delete it. If obj isnotinthedictionary,someobjectmatchingitwillbedeleted.SeeDtdisc_t.freef for object destruction.
dtdelete() returnsthedeletedobject(evenifitwasdeallocated)orNULL on error.
void*dtattach(Dt_t*dt,void*obj)
This function is similar to dtinsert() butobj itself will be inserted into dt evenifadisciplinefunctionmakef is defined.
void*dtdetach(Dt_t*dt,void*obj)
This function is similar to dtdelete() buttheobjecttobedeletedfromdt will not be freed (via the
discipline freef function).void*dtsearch(Dt_t*dt,void*obj)void*dtmatch(Dt_t*dt,void*key)
These functions find an object matching obj orkey either from dt orfromsomedictionaryaccessiblefromdt via a viewpath (see dtview().)dtsearch() and dtmatch() returnthematchingobjectorNULL on
failure.
void*dtfirst(Dt_t*dt)void*dtnext(Dt_t*dt,void*obj)
dtfirst() returnsthefirstobjectindt. dtnext() returnstheobjectfollowingobj. Objects are
ordered based on the storage method in use. For Dtoset andDtobag, objects are ordered by object
comparisons. For Dtstack,objectsareorderedinreverseorderofinsertion.ForDtqueue, objects are
ordered in order of insertion. For Dtlist,objectsareorderedbylistposition.ForDtset and Dtbag,objectsareorderedbysomeinternalorder(morebelow).Thus,objectsinadictionaryoraviewpathcanbewalkedusingafor(;;) loop as below.
for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))
When a dictionary uses Dtset or Dtbag, the object order is determined upon a call to dtfirst()/dtlast().
This order is frozen until a call dtnext()/dtprev() returns NULL or when these same functions are called
with a NULL object argument. It is important that a dtfirst()/dtlast() call be balanced by a
dtnext()/dtprev() call as described. Nested loops will require multiple balancing, once per loop. If
loop balancing is not done carefully, either performance is degraded or unexpected behaviors may result.
void*dtlast(Dt_t*dt)void*dtprev(Dt_t*dt,void*obj)
dtlast() anddtprev() are like dtfirst() anddtnext() but work in reverse order. Note that dictionaries
on a viewpath are still walked in order but objects in each dictionary are walked in reverse order.
void*dtfinger(Dt_t*dt)
This function returns the currentobject of dt,ifany.Thecurrentobjectisdefinedafterasuccessfulcalltooneofdtsearch(), dtmatch(),dtinsert(), dtfirst(),dtnext(), dtlast(),ordtprev(). As a side
effect of this implementation of Cdt, when a dictionary is based on Dtoset andDtobag, the current object
is always defined and is the root of the tree.
void*dtrenew(Dt_t*dt,void*obj)
This function repositions and perhaps rehashes an object obj afteritskeyhasbeenchanged.dtrenew()
only works if obj isthecurrentobject(seedtfinger()).
dtwalk(Dt_t*dt,int(*userf)(Dt_t*,void*,void*),void*data)
This function calls (*userf)(walk,obj,data) oneachobjectindt and other dictionaries viewable from it.
walk isthedictionarycontainingobj. If userf() returnsa<0 value, dtwalk() terminatesandreturnsthesamevalue.dtwalk() returns 0 oncompletion.Dtlink_t*dtflatten(Dt_t*dt)Dtlink_t*dtlink(Dt_t*dt,Dtlink_t*link)void*dtobj(Dt_t*dt,Dtlink_t*link)
Using dtfirst()/dtnext() ordtlast()/dtprev() to walk a single dictionary can incur significant cost due
to function calls. For efficient walking of a single directory (i.e., no viewpathing), dtflatten() anddtlink() can be used. Objects in dt aremadeintoalinkedlistandwalkedasfollows:for(link=dtflatten(dt);link;link=dtlink(dt,link))
Note that dtflatten() returns a list of type Dtlink_t*, not void*. That is, it returns a dictionary
holder pointer, not a user object pointer (although both are the same if the discipline field link is
zero.) The macro function dtlink() returns the dictionary holder object following link. The macro
function dtobj(dt,link) returns the user object associated with link, Beware that the flattened object
list is unflattened on any dictionary operations other than dtlink().
Dtlink_t*dtextract(Dt_t*dt)intdtrestore(Dt_t*dt,Dtlink_t*link)
dtextract() extractsallobjectsfromdt and makes it appear empty. dtrestore() repopulatesdt with
objects previously obtained via dtextract().dtrestore() will fail if dt isnotempty.Thesefunctionscanbeusedtoshareasamedt handle among many sets of objects. They are useful to reduce dictionary
overhead in an application that creates many concurrent dictionaries. It is important that the same
discipline and method are in use at both extraction and restoration. Otherwise, undefined behaviors may
result.
#defineDTTREESEARCH(Dt_t*dt,void*obj,action)#defineDTTREEMATCH(Dt_t*dt,void*key,action)
These macro functions are analogues of dtsearch() anddtmatch() but they can only be used on a dictionary
based on a binary search tree, i.e., Dtoset orDtobag.
obj or key:
These are used to find a matching object. If there is no match, the result is NULL.
action:
The matching object o (which may be NULL) will be processed as follow:
action (o);
Since action is used verbatim, it can be any C code fragment combinable with (o) to form a
syntactically correct C statement. For example, suppose that the matching object is an integer,
the below code accumulates the integer value in a variable total:
DTTREEMATCH(dt, key, total += (int));
DICTIONARYINFORMATIONDt_t*dtvnext(Dt_t*dt)
This returns the dictionary that dt isviewing,ifany.intdtvcount(Dt_t*dt)
This returns the number of dictionaries that view dt.Dt_t*dtvhere(Dt_t*dt)
This returns the dictionary v viewablefromdt where an object was found from the most recent search or
walk operation.
intdtsize(Dt_t*dt)
This function returns the number of objects stored in dt.intdtstat(Dt_t*dt,Dtstat_t*st,intall)
This function reports dictionary statistics. If all isnon-zero,allfieldsofst are filled.
Otherwise, only the dt_type anddt_size fields are filled. It returns 0 onsuccessand-1 on error.
Dtstat_t contains the below fields:
int dt_type:
This is one of DT_SET, DT_BAG, DT_OSET, DT_OBAG, DT_LIST, DT_STACK, and DT_QUEUE.
int dt_size:
This contains the number of objects in the dictionary.
int dt_n:
For Dtset and Dtbag, this is the number of non-empty chains in the hash table. For Dtoset and
Dtobag, this is the deepest level in the tree (counting from zero.) Each level in the tree
contains all nodes of equal distance from the root node. dt_n and the below two fields are
undefined for other methods.
int dt_max:
For Dtbag and Dtset, this is the size of a largest chain. For Dtoset and Dtobag, this is the size
of a largest level.
int* dt_count:
For Dtset and Dtbag, this is the list of counts for chains of particular sizes. For example,
dt_count[1] is the number of chains of size 1. For Dtoset and Dtobag, this is the list of sizes
of the levels. For example, dt_count[1] is the size of level 1.
HASHFUNCTIONSunsignedintdtcharhash(unsignedinth,charc)unsignedintdtstrhash(unsignedinth,char*str,intn)
These functions compute hash values from bytes or strings. dtcharhash() computesanewhashvaluefrombytec and seed value h.dtstrhash() computes a new hash value from string str andseedvalueh. If n
ispositive,str is a byte array of length n;otherwise,str is a null-terminated string.
Install Now
PNG Icons
