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