1LIBCDT(3) Library Functions Manual LIBCDT(3)
2
6 Cdt - container data types
7
9 #include <cdt.h>
10 DICTIONARY TYPES
12 Dt_t;
13 Dtdisc_t;
14 Dtmethod_t;
15 Dtlink_t;
16 Dtstat_t;
17 DICTIONARY CONTROL
19 Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth);
20 int dtclose(Dt_t* dt);
21 void dtclear(dt);
22 Dtmethod_t* dtmethod(Dt_t* dt, const Dtmethod_t* meth);
23 Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type);
24 Dt_t* dtview(Dt_t* dt, Dt_t* view);
25 STORAGE METHODS
27 Dtmethod_t* Dtset;
28 Dtmethod_t* Dtbag;
29 Dtmethod_t* Dtoset;
30 Dtmethod_t* Dtobag;
31 Dtmethod_t* Dtlist;
32 Dtmethod_t* Dtstack;
33 Dtmethod_t* Dtqueue;
34 Dtmethod_t* Dtdeque;
35 DISCIPLINE
37 #define DTOFFSET(struct_s,member)
38 #define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)
39 typedef void* (*Dtmake_f)(Dt_t*, void*, Dtdisc_t*);
40 typedef void (*Dtfree_f)(Dt_t*, void*, Dtdisc_t*);
41 typedef int (*Dtcompar_f)(Dt_t*, void*, void*, Dtdisc_t*);
42 typedef unsigned int (*Dthash_f)(Dt_t*, void*, Dtdisc_t*);
43 typedef void* (*Dtmemory_f)(Dt_t*, void*, size_t, Dtdisc_t*);
44 typedef int (*Dtevent_f)(Dt_t*, int, void*, Dtdisc_t*);
45 OBJECT OPERATIONS
47 void* dtinsert(Dt_t* dt, void* obj);
48 void* dtappend(Dt_t* dt, void* obj);
49 void* dtdelete(Dt_t* dt, void* obj);
50 void* dtattach(Dt_t* dt, void* obj);
51 void* dtdetach(Dt_t* dt, void* obj);
52 void* dtsearch(Dt_t* dt, void* obj);
53 void* dtmatch(Dt_t* dt, void* key);
54 void* dtfirst(Dt_t* dt);
55 void* dtnext(Dt_t* dt, void* obj);
56 void* dtlast(Dt_t* dt);
57 void* dtprev(Dt_t* dt, void* obj);
58 void* dtfinger(Dt_t* dt);
59 void* dtrenew(Dt_t* dt, void* obj);
60 int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, void*, void*), void*);
61 Dtlink_t* dtflatten(Dt_t* dt);
62 Dtlink_t* dtlink(Dt_t*, Dtlink_t* link);
63 void* dtobj(Dt_t* dt, Dtlink_t* link);
64 Dtlink_t* dtextract(Dt_t* dt);
65 int dtrestore(Dt_t* dt, Dtlink_t* link);
66 #define DTTREESEARCH(Dt_t* dt, void* obj, action)
68 #define DTTREEMATCH(Dt_t* dt, void* key, action)
69 DICTIONARY STATUS
71 Dt_t* dtvnext(Dt_t* dt);
72 int dtvcount(Dt_t* dt);
73 Dt_t* dtvhere(Dt_t* dt);
74 int dtsize(Dt_t* dt);
75 int dtstat(Dt_t* dt, Dtstat_t*, int all);
76 HASH FUNCTIONS
78 unsigned int dtstrhash(unsigned int h, char* str, int n);
79 unsigned int dtcharhash(unsigned int h, unsigned char c);
80
82 Cdt manages run-time dictionaries using standard container data types:
83 unordered set/multiset, ordered set/multiset, list, stack, and queue.
84 DICTIONARY TYPES
86 Dt_t
87 This is the type of a dictionary handle.
88 Dtdisc_t
90 This defines the type of a discipline structure which describes object
91 lay-out and manipulation functions.
92 Dtmethod_t
94 This defines the type of a container method.
95 Dtlink_t
97 This is the type of a dictionary object holder (see dtdisc().)
98 Dtstat_t
100 This is the type of a structure to return dictionary statistics (see
101 dtstat().)
102 DICTIONARY CONTROL
104 Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth)
105 This creates a new dictionary. disc is a discipline structure to
106 describe object format. meth specifies a manipulation method.
107 dtopen() returns the new dictionary or NULL on error. See also the
108 events DT_OPEN and DT_ENDOPEN below.
109 int dtclose(Dt_t* dt)
111 This deletes dt and its objects. Note that dtclose() fails if dt is
112 being viewed by some other dictionaries (see dtview()). dtclose()
113 returns 0 on success and -1 on error. See also the events DT_CLOSE and
114 DT_ENDCLOSE below.
115 void dtclear(Dt_t* dt)
117 This deletes all objects in dt without closing dt.
118 Dtmethod_t dtmethod(Dt_t* dt, const Dtmethod_t* meth)
120 If meth is NULL, dtmethod() returns the current method. Otherwise, it
121 changes the storage method of dt to meth. Object order remains the
122 same during a method switch among Dtlist, Dtstack, Dtqueue and Dtdeque.
123 Switching to and from Dtset/Dtbag and Dtoset/Dtobag may cause objects
124 to be rehashed, reordered, or removed as the case requires. dtmethod()
125 returns the previous method or NULL on error.
126 Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type)
128 If disc is NULL, dtdisc() returns the current discipline. Otherwise,
129 it changes the discipline of dt to disc. Objects may be rehashed,
130 reordered, or removed as appropriate. type can be any bit combination
131 of DT_SAMECMP and DT_SAMEHASH. DT_SAMECMP means that objects will com‐
132 pare exactly the same as before thus obviating the need for reordering
133 or removing new duplicates. DT_SAMEHASH means that hash values of
134 objects remain the same thus obviating the need to rehash. dtdisc()
135 returns the previous discipline on success and NULL on error.
136 Dt_t* dtview(Dt_t* dt, Dt_t* view)
138 A viewpath allows a search or walk starting from a dictionary to con‐
139 tinue to another. dtview() first terminates any current view from dt
140 to another dictionary. Then, if view is NULL, dtview returns the ter‐
141 minated view dictionary. If view is not NULL, a viewpath from dt to
142 view is established. dtview() returns dt on success and NULL on error.
143 It is an error to have dictionaries on a viewpath with different stor‐
145 age methods. In addition, dictionaries on the same view path should
146 treat objects in a consistent manner with respect to comparison or
147 hashing. If not, undefined behaviors may result.
148 STORAGE METHODS
150 Storage methods are of type Dtmethod_t*. Cdt supports the following
151 methods:
152 Dtoset
154 Dtobag
155 Objects are ordered by comparisons. Dtoset keeps unique objects. Dto‐
156 bag allows repeatable objects.
157 Dtset
159 Dtbag
160 Objects are unordered. Dtset keeps unique objects. Dtbag allows
161 repeatable objects and always keeps them together (note the effect on
162 dictionary walking.) These methods use a hash table with chaining to
163 manage the objects. See also the event DT_HASHSIZE below on how to
164 manage hash table resizing when objects are inserted.
165 Dtlist
167 Objects are kept in a list. The call dtinsert() inserts a new object
168 in front of the current object (see dtfinger()) if it is defined or at
169 list front if no current object is defined. Similarly, the call dtap‐
170 pend() appends a new object after the current object (see dtfinger())
171 if it is defined or at list end if no current object is defined.
172 Dtdeque
174 Objects are kept in a deque. This is similar to Dtlist except that
175 objects are always inserted at the front and appended at the tail of
176 the list.
177 Dtstack
179 Objects are kept in a stack, i.e., in reverse order of insertion.
180 Thus, the last object inserted is at stack top and will be the first to
181 be deleted.
182 Dtqueue
184 Objects are kept in a queue, i.e., in order of insertion. Thus, the
185 first object inserted is at queue head and will be the first to be
186 deleted.
187 DISCIPLINE
189 Object format and associated management functions are defined in the
190 type Dtdisc_t:
191 typedef struct
192 { int key, size;
193 int link;
194 Dtmake_f makef;
195 Dtfree_f freef;
196 Dtcompar_f comparf;
197 Dthash_f hashf;
198 Dtmemory_f memoryf;
199 Dtevent_f eventf;
200 } Dtdisc_t;
201 int key, size
203 Each object obj is identified by a key used for object comparison or
204 hashing. key should be non-negative and defines an offset into obj.
205 If size is negative, the key is a null-terminated string with starting
206 address *(void**)((char*)obj+key). If size is zero, the key is a null-
207 terminated string with starting address (void*)((char*)obj+key).
208 Finally, if size is positive, the key is a byte array of length size
209 starting at (void*)((char*)obj+key).
210 int link
212 Let obj be an object to be inserted into dt as discussed below. If
213 link is negative, an internally allocated object holder is used to hold
214 obj. Otherwise, obj should have a Dtlink_t structure embedded link
215 bytes into it, i.e., at address (Dtlink_t*)((char*)obj+link).
216 void* (*makef)(Dt_t* dt, void* obj, Dtdisc_t* disc)
218 If makef is not NULL, dtinsert(dt,obj) or dtappend() will call it to
219 make a copy of obj suitable for insertion into dt. If makef is NULL,
220 obj itself will be inserted into dt.
221 void (*freef)(Dt_t* dt, void* obj, Dtdisc_t* disc)
223 If not NULL, freef is used to destroy data associated with obj.
224 int (*comparf)(Dt_t* dt, void* key1, void* key2, Dtdisc_t* disc)
226 If not NULL, comparf is used to compare two keys. Its return value
227 should be <0, =0, or >0 to indicate whether key1 is smaller, equal to,
228 or larger than key2. All three values are significant for method
229 Dtoset and Dtobag. For other methods, a zero value indicates equality
230 and a non-zero value indicates inequality. If (*comparf)() is NULL, an
231 internal function is used to compare the keys as defined by the
232 Dtdisc_t.size field.
233 unsigned int (*hashf)(Dt_t* dt, void* key, Dtdisc_t* disc)
235 If not NULL, hashf is used to compute the hash value of key. It is
236 required that keys compared equal will also have same hash values. If
237 hashf is NULL, an internal function is used to hash the key as defined
238 by the Dtdisc_t.size field.
239 void* (*memoryf)(Dt_t* dt, void* addr, size_t size, Dtdisc_t* disc)
241 If not NULL, memoryf is used to allocate and free memory. When addr is
242 NULL, a memory segment of size size is requested. If addr is not NULL
243 and size is zero, addr is to be freed. If addr is not NULL and size is
244 positive, addr is to be resized to the given size. If memoryf is NULL,
245 malloc(3) is used.
246 int (*eventf)(Dt_t* dt, int type, void* data, Dtdisc_t* disc)
248 If not NULL, eventf announces various events. Each event may have par‐
249 ticular handling of the return values from eventf. But a negative
250 return value typically means failure. Following are the events:
251 DT_OPEN:
253 dt is being opened. If eventf returns negative, the opening
254 process terminates with failure. If eventf returns zero, the
255 opening process proceeds in a default manner. A positive return
256 value indicates special treatment of memory as follows. If
257 *(void**)data is set to point to some memory segment as dis‐
258 cussed in memoryf, that segment of memory is used to start the
259 dictionary. If *(void**)data is NULL, all memory including that
260 of the dictionary handle itself will be allocated via memoryf.
261 DT_ENDOPEN:
263 This event announces that dtopen() has successfully opened a
264 dictionary and is about to return. The data argument of eventf
265 should be the new dictionary handle itself.
266 DT_CLOSE:
268 dt is about to be closed. If eventf returns negative, the clos‐
269 ing process stops immediately and dtclose() returns -1. Objects
270 in the dictionary are deleted only if eventf returns zero. The
271 dictionary handle itself is processed as follows. If it was
272 allocated via malloc(), it will be freed. If it was allocated
273 via memoryf (see dtopen()) and eventf returns 0, a call to memo‐
274 ryf will be issued to attempt freeing the handle. Otherwise,
275 nothing will be done to its memory.
276 As should be clear from their description, the events DT_OPEN
278 and DT_CLOSE are designed to be used along with memoryf to man‐
279 age the allocation and deallocation of dictionary and object
280 memory across dictionaries. In fact, they can be used to manage
281 dictionaries based on shared and/or persistent memory.
282 DT_ENDCLOSE:
284 This event announces that dtclose() has successfully closed a
285 dictionary and is about to return.
286 DT_DISC:
288 The discipline of dt is being changed to a new one given in
289 (Dtdisc_t*)data.
290 DT_METH:
292 The method of dt is being changed to a new one given in
293 (Dtmethod_t*)data.
294 DT_HASHSIZE:
296 The hash table (for Dtset and Dtbag) is being resized. In this
297 case, *(int*)data has the current size of the table. The appli‐
298 cation can set the new table size by first changing *(int*)data
299 to the desired size, then return a positive value. The applica‐
300 tion can also fix the table size at the current value forever by
301 setting *(int*)data to a negative value, then again return a
302 positive value. A non-positive return value from the event han‐
303 dling function means that Cdt will be responsible for choosing
304 the hash table size.
305 #define DTOFFSET(struct_s,member)
307 This macro function computes the offset of member from the start of
308 structure struct_s. It is useful for getting the offset of a Dtlink_t
309 embedded inside an object.
310 #define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)
312 This macro function initializes the discipline pointed to by disc with
313 the given values.
314 OBJECT OPERATIONS
316 void* dtinsert(Dt_t* dt, void* obj)
317 void* dtappend(Dt_t* dt, void* obj)
318 These functions add an object prototyped by obj into dt. dtinsert()
319 and dtappend() perform the same function for all methods except for
320 Dtlist. See Dtlist for details. If there is an existing object in dt
321 matching obj and the storage method is Dtset or Dtoset, dtinsert() and
322 dtappend() will simply return the matching object. Otherwise, a new
323 object is inserted according to the method in use. See Dtdisc_t.makef
324 for object construction. The new object or a matching object as noted
325 will be returned on success while NULL is returned on error.
326 void* dtdelete(Dt_t* dt, void* obj)
328 If obj is NULL, methods Dtstack and Dtqueue delete respectively stack
329 top or queue head while other methods do nothing. If obj is not NULL,
330 there are two cases. If the method in use is not Dtbag or Dtobag, the
331 first object matching obj is deleted. On the other hand, if the method
332 in use is Dtbag or Dtobag, the library check to see if obj is in the
333 dictionary and delete it. If obj is not in the dictionary, some object
334 matching it will be deleted. See Dtdisc_t.freef for object destruc‐
335 tion. dtdelete() returns the deleted object (even if it was deallo‐
336 cated) or NULL on error.
337 void* dtattach(Dt_t* dt, void* obj)
339 This function is similar to dtinsert() but obj itself will be inserted
340 into dt even if a discipline function makef is defined.
341 void* dtdetach(Dt_t* dt, void* obj)
343 This function is similar to dtdelete() but the object to be deleted
344 from dt will not be freed (via the discipline freef function).
345 void* dtsearch(Dt_t* dt, void* obj)
347 void* dtmatch(Dt_t* dt, void* key)
348 These functions find an object matching obj or key either from dt or
349 from some dictionary accessible from dt via a viewpath (see dtview().)
350 dtsearch() and dtmatch() return the matching object or NULL on failure.
351 void* dtfirst(Dt_t* dt)
353 void* dtnext(Dt_t* dt, void* obj)
354 dtfirst() returns the first object in dt. dtnext() returns the object
355 following obj. Objects are ordered based on the storage method in use.
356 For Dtoset and Dtobag, objects are ordered by object comparisons. For
357 Dtstack, objects are ordered in reverse order of insertion. For
358 Dtqueue, objects are ordered in order of insertion. For Dtlist,
359 objects are ordered by list position. For Dtset and Dtbag, objects are
360 ordered by some internal order (more below). Thus, objects in a dic‐
361 tionary or a viewpath can be walked using a for(;;) loop as below.
362 for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))
363 When a dictionary uses Dtset or Dtbag, the object order is determined
364 upon a call to dtfirst()/dtlast(). This order is frozen until a call
365 dtnext()/dtprev() returns NULL or when these same functions are called
366 with a NULL object argument. It is important that a dtfirst()/dtlast()
367 call be balanced by a dtnext()/dtprev() call as described. Nested
368 loops will require multiple balancing, once per loop. If loop balanc‐
369 ing is not done carefully, either performance is degraded or unexpected
370 behaviors may result.
371 void* dtlast(Dt_t* dt)
373 void* dtprev(Dt_t* dt, void* obj)
374 dtlast() and dtprev() are like dtfirst() and dtnext() but work in
375 reverse order. Note that dictionaries on a viewpath are still walked
376 in order but objects in each dictionary are walked in reverse order.
377 void* dtfinger(Dt_t* dt)
379 This function returns the current object of dt, if any. The current
380 object is defined after a successful call to one of dtsearch(),
381 dtmatch(), dtinsert(), dtfirst(), dtnext(), dtlast(), or dtprev(). As
382 a side effect of this implementation of Cdt, when a dictionary is based
383 on Dtoset and Dtobag, the current object is always defined and is the
384 root of the tree.
385 void* dtrenew(Dt_t* dt, void* obj)
387 This function repositions and perhaps rehashes an object obj after its
388 key has been changed. dtrenew() only works if obj is the current
389 object (see dtfinger()).
390 dtwalk(Dt_t* dt, int (*userf)(Dt_t*, void*, void*), void* data)
392 This function calls (*userf)(walk,obj,data) on each object in dt and
393 other dictionaries viewable from it. walk is the dictionary containing
394 obj. If userf() returns a <0 value, dtwalk() terminates and returns
395 the same value. dtwalk() returns 0 on completion.
396 Dtlink_t* dtflatten(Dt_t* dt)
398 Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)
399 void* dtobj(Dt_t* dt, Dtlink_t* link)
400 Using dtfirst()/dtnext() or dtlast()/dtprev() to walk a single dictio‐
401 nary can incur significant cost due to function calls. For efficient
402 walking of a single directory (i.e., no viewpathing), dtflatten() and
403 dtlink() can be used. Objects in dt are made into a linked list and
404 walked as follows:
405 for(link = dtflatten(dt); link; link = dtlink(dt,link) )
406 Note that dtflatten() returns a list of type Dtlink_t*, not void*. That
408 is, it returns a dictionary holder pointer, not a user object pointer
409 (although both are the same if the discipline field link is zero.) The
410 macro function dtlink() returns the dictionary holder object following
411 link. The macro function dtobj(dt,link) returns the user object asso‐
412 ciated with link, Beware that the flattened object list is unflattened
413 on any dictionary operations other than dtlink().
414 Dtlink_t* dtextract(Dt_t* dt)
416 int dtrestore(Dt_t* dt, Dtlink_t* link)
417 dtextract() extracts all objects from dt and makes it appear empty.
418 dtrestore() repopulates dt with objects previously obtained via dtex‐
419 tract(). dtrestore() will fail if dt is not empty. These functions
420 can be used to share a same dt handle among many sets of objects. They
421 are useful to reduce dictionary overhead in an application that creates
422 many concurrent dictionaries. It is important that the same discipline
423 and method are in use at both extraction and restoration. Otherwise,
424 undefined behaviors may result.
425 #define DTTREESEARCH(Dt_t* dt, void* obj, action)
427 #define DTTREEMATCH(Dt_t* dt, void* key, action)
428 These macro functions are analogues of dtsearch() and dtmatch() but
429 they can only be used on a dictionary based on a binary search tree,
430 i.e., Dtoset or Dtobag.
431 obj or key:
433 These are used to find a matching object. If there is no match,
434 the result is NULL.
435 action:
437 The matching object o (which may be NULL) will be processed as
438 follow:
439 action (o);
441 Since action is used verbatim, it can be any C code fragment
443 combinable with (o) to form a syntactically correct C statement.
444 For example, suppose that the matching object is an integer, the
445 below code accumulates the integer value in a variable total:
446 DTTREEMATCH(dt, key, total += (int));
448 DICTIONARY INFORMATION
451 Dt_t* dtvnext(Dt_t* dt)
452 This returns the dictionary that dt is viewing, if any.
453 int dtvcount(Dt_t* dt)
455 This returns the number of dictionaries that view dt.
456 Dt_t* dtvhere(Dt_t* dt)
458 This returns the dictionary v viewable from dt where an object was
459 found from the most recent search or walk operation.
460 int dtsize(Dt_t* dt)
462 This function returns the number of objects stored in dt.
463 int dtstat(Dt_t *dt, Dtstat_t* st, int all)
465 This function reports dictionary statistics. If all is non-zero, all
466 fields of st are filled. Otherwise, only the dt_type and dt_size
467 fields are filled. It returns 0 on success and -1 on error.
468 Dtstat_t contains the below fields:
470 int dt_type:
472 This is one of DT_SET, DT_BAG, DT_OSET, DT_OBAG, DT_LIST,
473 DT_STACK, and DT_QUEUE.
474 int dt_size:
476 This contains the number of objects in the dictionary.
477 int dt_n:
479 For Dtset and Dtbag, this is the number of non-empty chains in
480 the hash table. For Dtoset and Dtobag, this is the deepest
481 level in the tree (counting from zero.) Each level in the tree
482 contains all nodes of equal distance from the root node. dt_n
483 and the below two fields are undefined for other methods.
484 int dt_max:
486 For Dtbag and Dtset, this is the size of a largest chain. For
487 Dtoset and Dtobag, this is the size of a largest level.
488 int* dt_count:
490 For Dtset and Dtbag, this is the list of counts for chains of
491 particular sizes. For example, dt_count[1] is the number of
492 chains of size 1. For Dtoset and Dtobag, this is the list of
493 sizes of the levels. For example, dt_count[1] is the size of
494 level 1.
495 HASH FUNCTIONS
497 unsigned int dtcharhash(unsigned int h, char c)
498 unsigned int dtstrhash(unsigned int h, char* str, int n)
499 These functions compute hash values from bytes or strings.
500 dtcharhash() computes a new hash value from byte c and seed value h.
501 dtstrhash() computes a new hash value from string str and seed value h.
502 If n is positive, str is a byte array of length n; otherwise, str is a
503 null-terminated string.
504
506 Dtset and Dtbag are based on hash tables with move-to-front collision
507 chains. Dtoset and Dtobag are based on top-down splay trees. Dtlist,
508 Dtstack and Dtqueue are based on doubly linked list.
509
511 Kiem-Phong Vo, kpv@research.att.com
512 LIBCDT(3)