Provided by: libgraphviz-dev_2.40.1-7_amd64

**NAME**

Cdt- container data types

**SYNOPSIS**

#include <cdt.h>DICTIONARYTYPESDt_t; Dtdisc_t; Dtmethod_t; Dtlink_t; Dtstat_t;DICTIONARYCONTROLDt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth); int dtclose(Dt_t* dt); void dtclear(dt); Dtmethod_t* dtmethod(Dt_t* dt, const Dtmethod_t* meth); Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type); Dt_t* dtview(Dt_t* dt, Dt_t* view); int dttreeset(Dt_t* dt, int minp, int balance);STORAGEMETHODSDtmethod_t* Dtset; Dtmethod_t* Dtbag; Dtmethod_t* Dtoset; Dtmethod_t* Dtobag; Dtmethod_t* Dtlist; Dtmethod_t* Dtstack; Dtmethod_t* Dtqueue; Dtmethod_t* Dtdeque;DISCIPLINE#define DTOFFSET(struct_s,member) #define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf) typedef void* (*Dtmake_f)(Dt_t*, void*, Dtdisc_t*); typedef void (*Dtfree_f)(Dt_t*, void*, Dtdisc_t*); typedef int (*Dtcompar_f)(Dt_t*, void*, void*, Dtdisc_t*); typedef unsigned int (*Dthash_f)(Dt_t*, void*, Dtdisc_t*); typedef void* (*Dtmemory_f)(Dt_t*, void*, size_t, Dtdisc_t*); typedef int (*Dtevent_f)(Dt_t*, int, void*, Dtdisc_t*);OBJECTOPERATIONSvoid* dtinsert(Dt_t* dt, void* obj); void* dtappend(Dt_t* dt, void* obj); void* dtdelete(Dt_t* dt, void* obj); void* dtattach(Dt_t* dt, void* obj); void* dtdetach(Dt_t* dt, void* obj); void* dtsearch(Dt_t* dt, void* obj); void* dtmatch(Dt_t* dt, void* key); void* dtfirst(Dt_t* dt); void* dtnext(Dt_t* dt, void* obj); void* dtlast(Dt_t* dt); void* dtprev(Dt_t* dt, void* obj); void* dtfinger(Dt_t* dt); void* dtrenew(Dt_t* dt, void* obj); int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, void*, void*), void*); Dtlink_t* dtflatten(Dt_t* dt); Dtlink_t* dtlink(Dt_t*, Dtlink_t* link); void* dtobj(Dt_t* dt, Dtlink_t* link); Dtlink_t* dtextract(Dt_t* dt); int dtrestore(Dt_t* dt, Dtlink_t* link); #define DTTREESEARCH(Dt_t* dt, void* obj, action) #define DTTREEMATCH(Dt_t* dt, void* key, action)DICTIONARYSTATUSDt_t* dtvnext(Dt_t* dt); int dtvcount(Dt_t* dt); Dt_t* dtvhere(Dt_t* dt); int dtsize(Dt_t* dt); int dtstat(Dt_t* dt, Dtstat_t*, int all);HASHFUNCTIONSunsigned int dtstrhash(unsigned int h, char* str, int n); unsigned int dtcharhash(unsigned int h, unsigned char c);

**DESCRIPTION**

Cdtmanages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, stack, and queue.DICTIONARYTYPESDt_tThis is the type of a dictionary handle.Dtdisc_tThis defines the type of a discipline structure which describes object lay-out and manipulation functions.Dtmethod_tThis defines the type of a container method.Dtlink_tThis is the type of a dictionary object holder (see dtdisc().)Dtstat_tThis 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. discisadisciplinestructuretodescribeobjectformat.methspecifies a manipulation method. dtopen()returnsthenewdictionaryorNULLon error. See also the events DT_OPENandDT_ENDOPENbelow.intdtclose(Dt_t*dt)This deletes dtanditsobjects.Notethatdtclose()fails if dtisbeingviewedbysomeotherdictionaries(seedtview()). dtclose()returns0on success and -1onerror.SeealsotheeventsDT_CLOSEand DT_ENDCLOSEbelow.voiddtclear(Dt_t*dt)This deletes all objects in dtwithoutclosingdt.Dtmethod_tdtmethod(Dt_t*dt,constDtmethod_t*meth)If methisNULL, dtmethod()returnsthecurrentmethod.Otherwise,itchangesthestoragemethodofdtto meth.ObjectorderremainsthesameduringamethodswitchamongDtlist, Dtstack,Dtqueueand Dtdeque.SwitchingtoandfromDtset/Dtbagand Dtoset/Dtobagmaycauseobjectstoberehashed,reordered,orremovedasthecaserequires.dtmethod()returns the previous method or NULLonerror.Dtdisc_t*dtdisc(Dt_t*dt,constDtdisc_t*disc,inttype)If discisNULL, dtdisc()returnsthecurrentdiscipline.Otherwise,itchangesthedisciplineofdtto disc.Objectsmayberehashed,reordered,orremovedasappropriate.typecan be any bit combination of DT_SAMECMPandDT_SAMEHASH. DT_SAMECMPmeansthatobjectswillcompareexactlythesameasbeforethusobviatingtheneedforreorderingorremovingnewduplicates.DT_SAMEHASHmeans that hash values of objects remain the same thus obviating the need to rehash. dtdisc()returnsthepreviousdisciplineonsuccessandNULLon 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()firstterminatesanycurrentviewfromdtto another dictionary. Then, if viewisNULL, dtviewreturnstheterminatedviewdictionary.Ifviewis not NULL,aviewpathfromdtto viewisestablished.dtview()returns dtonsuccessandNULLon 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.intdttreeset(Dt_t*dt,intminp,intbalance)This function only applies to dictionaries operated under the method Dtosetwhichusestop-downsplaytrees(seebelow).Itreturns0onsuccessand-1onerror.minp: This parameter defines the minimum path length before a search path is adjusted. For example, minp equal 0 would mean that search paths are always adjusted. If minp is negative, the minimum search path is internally computed based on a function of the current dictionary size. This computed value is such that if the tree is balanced, it will never require adjusting. balance: If this is non-zero, the tree will be made balanced.STORAGEMETHODSStorage methods are of type Dtmethod_t*.Cdtsupports the following methods:DtosetDtobagObjects are ordered by comparisons. Dtosetkeepsuniqueobjects.Dtobagallows repeatable objects.DtsetDtbagObjects are unordered. Dtsetkeepsuniqueobjects.Dtbagallows 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_HASHSIZEbelowonhowtomanagehashtableresizingwhenobjectsareinserted.DtlistObjects are kept in a list. The call dtinsert()insertsanewobjectinfrontofthecurrentobject(seedtfinger())ifitisdefinedoratlistfrontifnocurrentobjectisdefined.Similarly,thecalldtappend()appendsanewobjectafterthecurrentobject(seedtfinger())ifitisdefinedoratlistendifnocurrentobjectisdefined.DtdequeObjects are kept in a deque. This is similar to Dtlistexceptthatobjectsarealwaysinsertedatthefrontandappendedatthetailofthelist.DtstackObjects 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.DtqueueObjects 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.DISCIPLINEObject 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,sizeEach object objisidentifiedbyakeyusedforobjectcomparisonorhashing.keyshould be non-negative and defines an offset into obj.Ifsizeis negative, the key is a null- terminated string with starting address *(void**)((char*)obj+key).Ifsizeis zero, the key is a null-terminated string with starting address (void*)((char*)obj+key).Finally,ifsizeis positive, the key is a byte array of length sizestartingat(void*)((char*)obj+key).intlinkLet objbeanobjecttobeinsertedintodtas discussed below. If linkisnegative,aninternallyallocatedobjectholderisusedtoholdobj. Otherwise, objshouldhaveaDtlink_tstructure embedded linkbytesintoit,i.e.,ataddress(Dtlink_t*)((char*)obj+link).void*(*makef)(Dt_t*dt,void*obj,Dtdisc_t*disc)If makefisnotNULL, dtinsert(dt,obj)ordtappend()will call it to make a copy of objsuitableforinsertionintodt. If makefisNULL, objitselfwillbeinsertedintodt.void(*freef)(Dt_t*dt,void*obj,Dtdisc_t*disc)If not NULL,freefis used to destroy data associated with obj.int(*comparf)(Dt_t*dt,void*key1,void*key2,Dtdisc_t*disc)If not NULL,comparfis used to compare two keys. Its return value should be <0,=0, or >0toindicatewhetherkey1is smaller, equal to, or larger than key2.AllthreevaluesaresignificantformethodDtosetand Dtobag.Forothermethods,azerovalueindicatesequalityandanon-zerovalueindicatesinequality.If(*comparf)()is NULL,aninternalfunctionisusedtocomparethekeysasdefinedbytheDtdisc_t.sizefield.unsignedint(*hashf)(Dt_t*dt,void*key,Dtdisc_t*disc)If not NULL,hashfis used to compute the hash value of key.Itisrequiredthatkeyscomparedequalwillalsohavesamehashvalues.Ifhashfis NULL,aninternalfunctionisusedtohashthekeyasdefinedbytheDtdisc_t.sizefield.void*(*memoryf)(Dt_t*dt,void*addr,size_tsize,Dtdisc_t*disc)If not NULL,memoryfis used to allocate and free memory. When addrisNULL, a memory segment of size sizeisrequested.Ifaddris not NULLandsizeis zero, addristobefreed.Ifaddris not NULLandsizeis positive, addristoberesizedtothegivensize.Ifmemoryfis NULL,malloc(3)isused.int(*eventf)(Dt_t*dt,inttype,void*data,Dtdisc_t*disc)If not NULL,eventfannounces various events. Each event may have particular handling of the return values from eventf.Butanegativereturnvaluetypicallymeansfailure.Followingaretheevents:DT_OPEN: dt is being opened. If eventf returns negative, the opening process terminates with failure. If eventf returns zero, the opening process proceeds in a default manner. A positive return value indicates special treatment of memory as follows. If *(void**)data is set to point to some memory segment as discussed in memoryf, that segment of memory is used to start the dictionary. If *(void**)data is NULL, all memory including that of the dictionary handle itself will be allocated via memoryf. 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 memberfromthestartofstructurestruct_s. It is useful for getting the offset of a Dtlink_tembeddedinsideanobject.#defineDTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)This macro function initializes the discipline pointed to by discwiththegivenvalues.OBJECTOPERATIONSvoid*dtinsert(Dt_t*dt,void*obj)void*dtappend(Dt_t*dt,void*obj)These functions add an object prototyped by objintodt. dtinsert()anddtappend()perform the same function for all methods except for Dtlist.SeeDtlistfor details. If there is an existing object in dtmatchingobjand the storage method is DtsetorDtoset, dtinsert()anddtappend()will simply return the matching object. Otherwise, a new object is inserted according to the method in use. See Dtdisc_t.makefforobjectconstruction.ThenewobjectoramatchingobjectasnotedwillbereturnedonsuccesswhileNULLis returned on error.void*dtdelete(Dt_t*dt,void*obj)If objisNULL, methods DtstackandDtqueuedelete respectively stack top or queue head while other methods do nothing. If objisnotNULL, there are two cases. If the method in use is not DtbagorDtobag, the first object matching objisdeleted.Ontheotherhand,ifthemethodinuseisDtbagor Dtobag,thelibrarychecktoseeifobjis in the dictionary and delete it. If objisnotinthedictionary,someobjectmatchingitwillbedeleted.SeeDtdisc_t.freeffor object destruction. dtdelete()returnsthedeletedobject(evenifitwasdeallocated)orNULLon error.void*dtattach(Dt_t*dt,void*obj)This function is similar to dtinsert()butobjitself will be inserted into dtevenifadisciplinefunctionmakefis defined.void*dtdetach(Dt_t*dt,void*obj)This function is similar to dtdelete()buttheobjecttobedeletedfromdtwill not be freed (via the discipline freeffunction).void*dtsearch(Dt_t*dt,void*obj)void*dtmatch(Dt_t*dt,void*key)These functions find an object matching objorkeyeither from dtorfromsomedictionaryaccessiblefromdtvia a viewpath (see dtview().)dtsearch()and dtmatch()returnthematchingobjectorNULLon 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 DtosetandDtobag, objects are ordered by object comparisons. For Dtstack,objectsareorderedinreverseorderofinsertion.ForDtqueue, objects are ordered in order of insertion. For Dtlist,objectsareorderedbylistposition.ForDtsetand 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 thecurrentobjectof dt,ifany.Thecurrentobjectisdefinedafterasuccessfulcalltooneofdtsearch(), dtmatch(),dtinsert(), dtfirst(),dtnext(), dtlast(),ordtprev(). As a side effect of this implementation ofCdt, when a dictionary is based on DtosetandDtobag, 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 objafteritskeyhasbeenchanged.dtrenew()only works if objisthecurrentobject(seedtfinger()).dtwalk(Dt_t*dt,int(*userf)(Dt_t*,void*,void*),void*data)This function calls (*userf)(walk,obj,data)oneachobjectindtand other dictionaries viewable from it. walkisthedictionarycontainingobj. If userf()returnsa<0value, dtwalk()terminatesandreturnsthesamevalue.dtwalk()returns 0oncompletion.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 dtaremadeintoalinkedlistandwalkedasfollows: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()extractsallobjectsfromdtand makes it appear empty. dtrestore()repopulatesdtwith objects previously obtained via dtextract().dtrestore()will fail if dtisnotempty.Thesefunctionscanbeusedtoshareasamedthandle 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., DtosetorDtobag. objorkey: 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 dtisviewing,ifany.intdtvcount(Dt_t*dt)This returns the number of dictionaries that view dt.Dt_t*dtvhere(Dt_t*dt)This returns the dictionary vviewablefromdtwhere 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 allisnon-zero,allfieldsofstare filled. Otherwise, only the dt_typeanddt_sizefields are filled. It returns 0onsuccessand-1on 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()computesanewhashvaluefrombytecand seed value h.dtstrhash()computes a new hash value from string strandseedvalueh. If nispositive,stris a byte array of length n;otherwise,stris a null-terminated string.

**IMPLEMENTATION** **NOTES**

DtsetandDtbagare based on hash tables with move-to-front collision chains. DtosetandDtobagare based on top-down splay trees. Dtlist,Dtstackand Dtqueuearebasedondoublylinkedlist.

**AUTHOR**

Kiem-Phong Vo, kpv@research.att.com LIBCDT(3)