LIBCDT(3) Library Functions Manual LIBCDT(3) NAMECdt- container data types SYNOPSIS #include <graphviz/cdt.h>DICTIONARY TYPESVoid_t*; Dt_t; Dtdisc_t; Dtmethod_t; Dtlink_t; Dtstat_t;DICTIONARY CONTROLDt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth); int dtclose(Dt_t* dt); void dtclear(dt); Dtmethod_t* dtmethod(Dt_t* dt, Dtmethod_t* meth); Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type); Dt_t* dtview(Dt_t* dt, Dt_t* view);STORAGE METHODSDtmethod_t* Dtset; Dtmethod_t* Dtbag; Dtmethod_t* Dtoset; Dtmethod_t* Dtobag; Dtmethod_t* Dtlist; Dtmethod_t* Dtstack; Dtmethod_t* Dtqueue;DISCIPLINEtypedef 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*);OBJECT OPERATIONSVoid_t* dtinsert(Dt_t* dt, Void_t* obj); Void_t* dtdelete(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* dtfinger(Dt_t* dt); Void_t* dtrenew(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*, Dtlink_t* link); Void_t* dtobj(Dt_t* dt, Dtlink_t* link); Dtlink_t* dtextract(Dt_t* dt); int dtrestore(Dt_t* dt, Dtlink_t* link);DICTIONARY STATUSDt_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);HASH FUNCTIONSunsigned int dtstrhash(unsigned int h, char* str, int n); unsigned int dtcharhash(unsigned int h, unsigned char c); DESCRIPTIONCdtmanages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, stack, and queue.DICTIONARY TYPESVoid_t*This type is used to pass objects betweenCdtand application code. Void_tis defined as voidfor ANSI-C and C++ and charfor othercompilation environments.Dt_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().)DICTIONARY CONTROLDt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth)This creates a new dictionary. discis a discipline structure todescribe object format. methspecifies a manipulation method. dtopen()returns the new dictionary or NULLon error.int dtclose(Dt_t* dt)This deletes dtand its objects. Note that dtclose()fails if dtisbeing viewed by some other dictionaries (see dtview()). dtclose()returns 0on success and -1on error.void dtclear(Dt_t* dt)This deletes all objects in dtwithout closing dt.Dtmethod_t dtmethod(Dt_t* dt, Dtmethod_t* meth)If methis NULL, dtmethod()returns the current method. Otherwise, itchanges the storage method of dtto meth. Object order remains thesame during a method switch among Dtlist, Dtstackand Dtqueue. Switching to and from Dtset/Dtbagand Dtoset/Dtobagmay cause objects to be rehashed, reordered, or removed as the case requires. dtmethod()returns the previous method or NULLon error.Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type)If discis NULL, dtdisc()returns the current discipline. Otherwise,it changes the discipline of dtto disc. Objects may be rehashed,reordered, or removed as appropriate. typecan be any bit combination of DT_SAMECMPand DT_SAMEHASH. DT_SAMECMPmeans that objects willcompare exactly the same as before thus obviating the need forreordering or removing new duplicates. DT_SAMEHASHmeans that hash values of objects remain the same thus obviating the need to rehash. dtdisc()returns the previous discipline on success and NULLon 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()first terminates any current view fromdtto another dictionary. Then, if viewis NULL, dtviewreturns theterminated view dictionary. If viewis not NULL, a viewpath from dtto viewis established. dtview()returns dton success and NULLon error. If two dictionaries on the same viewpath have the same values for the discipline fields Dtdisc_t.link, Dtdisc_t.key, Dtdisc_t.size, and Dtdisc_t.hashf, it is expected that key hashing will be the same. If not, undefined behaviors may result during a search or a walk.STORAGE METHODSStorage methods are of type Dtmethod_t*.Cdtsupports the following methods:DtosetDtobagObjects are ordered by comparisons. Dtosetkeeps unique objects.Dtobagallows repeatable objects.DtsetDtbagObjects are unordered. Dtsetkeeps unique objects. Dtbagallows repeatable objects and always keeps them together (note the effect on dictionary walking.)DtlistObjects are kept in a list. New objects are inserted either in front ofcurrent object(see dtfinger()) if this is defined or at list frontif there is no current object.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;int key, sizeEach object objis identified by a key used for object comparison orhashing. keyshould be non-negative and defines an offset into obj.If sizeis negative, the key is a null-terminated string with starting address *(Void_t**)((char*)obj+key). If sizeis zero, the key is a null-terminated string with starting address (Void_t*)((char*)obj+key).Finally, if sizeis positive, the key is a byte array of length sizestarting at (Void_t*)((char*)obj+key).int linkLet objbe an object to be inserted into dtas discussed below. If linkis negative, an internally allocated object holder is used to holdobj. Otherwise, objshould have a Dtlink_tstructure embedded linkbytes into it, i.e., at address (Dtlink_t*)((char*)obj+link).Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)If makefis not NULL, dtinsert(dt,obj)will call it to make a copy ofobjsuitable for insertion into dt. If makefis NULL, objitself will be inserted into dt.void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)If not NULL, freefis used to destroy data associated with obj.int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)If not NULL, comparfis used to compare two keys. Its return value should be <0, =0, or >0to indicate whether key1is smaller, equal to, or larger than key2. All three values are significant for methodDtosetand Dtobag. For other methods, a zero value indicates equalityand a non-zero value indicates inequality. If (*comparf)()is NULL, aninternal function is used to compare the keys as defined by theDtdisc_t.sizefield.unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)If not NULL, hashfis used to compute the hash value of key. It isrequired that keys compared equal will also have same hash values. Ifhashfis NULL, an internal function is used to hash the key as definedby the Dtdisc_t.sizefield.Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)If not NULL, memoryfis used to allocate and free memory. When addrisNULL, a memory segment of size sizeis requested. If addris not NULLand sizeis zero, addris to be freed. If addris not NULLand sizeis positive, addris to be resized to the given size. If memoryfis NULL,malloc(3)is used. When dictionaries share memory, a record of thefirst allocated memory segment should be kept so that it can be used toinitialize new dictionaries (see below.)int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)If not NULL, eventfannounces various events. If it returns a negative value, the calling operation will terminate with failure. Unless noted otherwise, a non-negative return value let the calling function proceed normally. Following are the events: DT_OPEN:dtis being opened. If eventfreturns zero, the opening process proceeds normally. A positive return value indicates that dtuses memory already initialized by a different dictionary. Inthat case, *(Void_t**)datashould be set to the first allocated memory segment as discussed in memoryf. dtopen()may fail if this segment is not returned or if it has not been properly initialized. DT_CLOSE:dtis being closed.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.OBJECT OPERATIONSVoid_t* dtinsert(Dt_t* dt, Void_t* obj)This inserts an object prototyped by objinto dt. If there is an existing object in dtmatching objand the storage method is DtsetorDtoset, dtinsert()will simply return the matching object. Otherwise,a new object is inserted according to the method in use. SeeDtdisc_t.makeffor object construction. dtinsert()returns the newobject, a matching object as noted, or NULLon error.Void_t* dtdelete(Dt_t* dt, Void_t* obj)If objis not NULL, the first object matching it is deleted. If objisNULL, methods Dtstackand Dtqueuedelete respectively stack top or queue head while other methods do nothing. See Dtdisc_t.freefforobject destruction. dtdelete()returns the deleted object (even if it was deallocated) or NULLon error.Void_t* dtsearch(Dt_t* dt, Void_t* obj)Void_t* dtmatch(Dt_t* dt, Void_t* key)These functions find an object matching objor keyeither from dtorfrom some dictionary accessible from dtvia a viewpath (see dtview().)dtsearch()and dtmatch()return the matching object or NULLon failure.Void_t* dtfirst(Dt_t* dt)Void_t* dtnext(Dt_t* dt, Void_t* obj)dtfirst()returns the first object in dt. dtnext()returns the objectfollowing obj. Objects are ordered based on the storage method in use. For Dtosetand Dtobag, objects are ordered by object comparisons. For Dtstack, objects are ordered in reverse order of insertion. ForDtqueue, objects are ordered in order of insertion. For Dtlist,objects are ordered by list position. For Dtsetand Dtbag, objects usesome internal ordering which may change on any search, insert, ordelete operations. Therefore, these operations should not be usedduring a walk on a dictionary using either Dtsetor Dtbag.Objects in a dictionary or a viewpath can be walked using a for(;;)loop as below. Note that only one loop can be used at a time perdictionary. Concurrent or nested loops may result in unexpectedbehaviors.for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))Void_t* dtlast(Dt_t* dt)Void_t* dtprev(Dt_t* dt, Void_t* obj)dtlast()and dtprev()are like dtfirst()and dtnext()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_t* dtfinger(Dt_t* dt)This function returns thecurrent objectof dt, if any. The currentobject is defined after a successful call to one of dtsearch(), dtmatch(), dtinsert(), dtfirst(), dtnext(), dtlast(), or dtprev(). As a side effect of this implementation ofCdt, when a dictionary is based on Dtosetand Dtobag, the current object is always defined and is the root of the tree.Void_t* dtrenew(Dt_t* dt, Void_t* obj)This function repositions and perhaps rehashes an object objafter itskey has been changed. dtrenew()only works if objis the currentobject (see dtfinger()).dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)This function calls (*userf)(walk,obj,data)on each object in dtand other dictionaries viewable from it. walkis the dictionary containingobj. If userf()returns a <0value, dtwalk()terminates and returnsthe same value. dtwalk()returns 0on completion.Dtlink_t* dtflatten(Dt_t* dt)Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)Void_t* dtobj(Dt_t* dt, Dtlink_t* link)Using dtfirst()/dtnext()or dtlast()/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()and dtlink()can be used. Objects in dtare made into alinked list and walked as follows:for(link = dtflatten(dt); link; link = dtlink(dt,link) )Note that dtflatten() returns a list of type Dtlink_t*, not Void_t*. That is, it returns a dictionary holder pointer, not a user object pointer (although both are the same if the discipline field link is non-negative.) 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)int dtrestore(Dt_t* dt, Dtlink_t* link)dtextract()extracts all objects from dtand makes it appear empty. dtrestore()repopulates dtwith objects previously obtained via dtextract(). dtrestore()will fail if dtis not empty. Thesefunctions can be used to share a same dthandle among many sets of objects. They are useful to reduce dictionary overhead in an application that creates concurrently many dictionaries. It is important that the same discipline and method are in use at both extraction and restoration. Otherwise, undefined behaviors may result.DICTIONARY INFORMATIONDt_t* dtvnext(Dt_t* dt)This returns the dictionary that dtis viewing, if any.int dtvcount(Dt_t* dt)This returns the number of dictionaries that view dt.Dt_t* dtvhere(Dt_t* dt)This returns the dictionary vviewable from dtwhere an object was found from the most recent search or walk operation.int dtsize(Dt_t* dt)This function returns the number of objects stored in dt.int dtstat(Dt_t *dt, Dtstat_t* st, int all)This function reports dictionary statistics. If allis non-zero, allfields of stare filled. Otherwise, only the dt_typeand dt_sizefields are filled. It returns 0on success and -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.HASH FUNCTIONSunsigned int dtcharhash(unsigned int h, char c)unsigned int dtstrhash(unsigned int h, char* str, int n)These functions compute hash values from bytes or strings. dtcharhash()computes a new hash value from byte cand seed value h.dtstrhash()computes a new hash value from string strand seed value h. If nis positive, stris a byte array of length n; otherwise, stris a null-terminated string. IMPLEMENTATION NOTES Dtsetand Dtbagare based on hash tables with move-to-front collision chains. Dtosetand Dtobagare based on top-down splay trees. Dtlist,Dtstackand Dtqueueare based on doubly linked list.AUTHOR Kiem-Phong Vo, kpv@research.att.com LIBCDT(3)