LIBCDT(3) | Library Functions Manual | LIBCDT(3) |

#include <cdt.h>

Void_t*; Dt_t; Dtdisc_t; Dtmethod_t; Dtlink_t; Dtstat_t;

Dt_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);

Dtmethod_t* Dtset; Dtmethod_t* Dtbag; Dtmethod_t* Dtoset; Dtmethod_t* Dtobag; Dtmethod_t* Dtlist; Dtmethod_t* Dtstack; Dtmethod_t* Dtqueue; Dtmethod_t* Dtdeque;

#define DTOFFSET(struct_s,member) #define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf) typedef Void_t* (*Dtmake_f)(Dt_t*, Void_t*, Dtdisc_t*); typedef void (*Dtfree_f)(Dt_t*, Void_t*, Dtdisc_t*); typedef int (*Dtcompar_f)(Dt_t*, Void_t*, Void_t*, Dtdisc_t*); typedef unsigned int (*Dthash_f)(Dt_t*, Void_t*, Dtdisc_t*); typedef Void_t* (*Dtmemory_f)(Dt_t*, Void_t*, size_t, Dtdisc_t*); typedef int (*Dtevent_f)(Dt_t*, int, Void_t*, Dtdisc_t*);

Void_t* dtinsert(Dt_t* dt, Void_t* obj); Void_t* dtappend(Dt_t* dt, Void_t* obj); Void_t* dtdelete(Dt_t* dt, Void_t* obj); Void_t* dtattach(Dt_t* dt, Void_t* obj); Void_t* dtdetach(Dt_t* dt, Void_t* obj); Void_t* dtsearch(Dt_t* dt, Void_t* obj); Void_t* dtmatch(Dt_t* dt, Void_t* key); Void_t* dtfirst(Dt_t* dt); Void_t* dtnext(Dt_t* dt, Void_t* obj); Void_t* dtlast(Dt_t* dt); Void_t* dtprev(Dt_t* dt, Void_t* obj); Void_t* 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); #define DTTREESEARCH(Dt_t* dt, Void_t* obj, action) #define DTTREEMATCH(Dt_t* dt, Void_t* key, action)

Dt_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);

unsigned int dtstrhash(unsigned int h, char* str, int n); unsigned int dtcharhash(unsigned int h, unsigned char c);

- 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.

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;

- 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_t**)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_t**)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.

- 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.

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.

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 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().

- 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);

DTTREEMATCH(dt, key, total += (int));

- 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.

Debian Sid |