1LIBCDT(3) Library Functions Manual LIBCDT(3)
2
6 Cdt - container data types
7
9 #include <graphviz/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(Dtdisc_t* disc, Dtmethod_t* meth);
21 int dtclose(Dt_t* dt);
22 void dtclear(dt);
23 Dtmethod_t* dtmethod(Dt_t* dt, Dtmethod_t* meth);
24 Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type);
25 Dt_t* dtview(Dt_t* dt, Dt_t* view);
26 STORAGE METHODS
28 Dtmethod_t* Dtset;
29 Dtmethod_t* Dtbag;
30 Dtmethod_t* Dtoset;
31 Dtmethod_t* Dtobag;
32 Dtmethod_t* Dtlist;
33 Dtmethod_t* Dtstack;
34 Dtmethod_t* Dtqueue;
35 DISCIPLINE
37 typedef Void_t* (*Dtmake_f)(Dt_t*, Void_t*, Dtdisc_t*);
38 typedef void (*Dtfree_f)(Dt_t*, Void_t*, Dtdisc_t*);
39 typedef int (*Dtcompar_f)(Dt_t*, Void_t*, Void_t*, Dtdisc_t*);
40 typedef unsigned int (*Dthash_f)(Dt_t*, Void_t*, Dtdisc_t*);
41 typedef Void_t* (*Dtmemory_f)(Dt_t*, Void_t*, size_t, Dtdisc_t*);
42 typedef int (*Dtevent_f)(Dt_t*, int, Void_t*, Dtdisc_t*);
43 OBJECT OPERATIONS
45 Void_t* dtinsert(Dt_t* dt, Void_t* obj);
46 Void_t* dtdelete(Dt_t* dt, Void_t* obj);
47 Void_t* dtsearch(Dt_t* dt, Void_t* obj);
48 Void_t* dtmatch(Dt_t* dt, Void_t* key);
49 Void_t* dtfirst(Dt_t* dt);
50 Void_t* dtnext(Dt_t* dt, Void_t* obj);
51 Void_t* dtlast(Dt_t* dt);
52 Void_t* dtprev(Dt_t* dt, Void_t* obj);
53 Void_t* dtfinger(Dt_t* dt);
54 Void_t* dtrenew(Dt_t* dt, Void_t* obj);
55 int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t*);
56 Dtlink_t* dtflatten(Dt_t* dt);
57 Dtlink_t* dtlink(Dt_t*, Dtlink_t* link);
58 Void_t* dtobj(Dt_t* dt, Dtlink_t* link);
59 Dtlink_t* dtextract(Dt_t* dt);
60 int dtrestore(Dt_t* dt, Dtlink_t* link);
61 DICTIONARY STATUS
63 Dt_t* dtvnext(Dt_t* dt);
64 int dtvcount(Dt_t* dt);
65 Dt_t* dtvhere(Dt_t* dt);
66 int dtsize(Dt_t* dt);
67 int dtstat(Dt_t* dt, Dtstat_t*, int all);
68 HASH FUNCTIONS
70 unsigned int dtstrhash(unsigned int h, char* str, int n);
71 unsigned int dtcharhash(unsigned int h, unsigned char c);
72
74 Cdt manages run-time dictionaries using standard container data types:
75 unordered set/multiset, ordered set/multiset, list, stack, and queue.
76 DICTIONARY TYPES
78 Void_t*
79 This type is used to pass objects between Cdt and application code.
80 Void_t is defined as void for ANSI-C and C++ and char for other compi‐
81 lation environments.
82 Dt_t
84 This is the type of a dictionary handle.
85 Dtdisc_t
87 This defines the type of a discipline structure which describes object
88 lay-out and manipulation functions.
89 Dtmethod_t
91 This defines the type of a container method.
92 Dtlink_t
94 This is the type of a dictionary object holder (see dtdisc().)
95 Dtstat_t
97 This is the type of a structure to return dictionary statistics (see
98 dtstat().)
99 DICTIONARY CONTROL
101 Dt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth)
102 This creates a new dictionary. disc is a discipline structure to
103 describe object format. meth specifies a manipulation method.
104 dtopen() returns the new dictionary or NULL on error.
105 int dtclose(Dt_t* dt)
107 This deletes dt and its objects. Note that dtclose() fails if dt is
108 being viewed by some other dictionaries (see dtview()). dtclose()
109 returns 0 on success and -1 on error.
110 void dtclear(Dt_t* dt)
112 This deletes all objects in dt without closing dt.
113 Dtmethod_t dtmethod(Dt_t* dt, Dtmethod_t* meth)
115 If meth is NULL, dtmethod() returns the current method. Otherwise, it
116 changes the storage method of dt to meth. Object order remains the
117 same during a method switch among Dtlist, Dtstack and Dtqueue. Switch‐
118 ing to and from Dtset/Dtbag and Dtoset/Dtobag may cause objects to be
119 rehashed, reordered, or removed as the case requires. dtmethod()
120 returns the previous method or NULL on error.
121 Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type)
123 If disc is NULL, dtdisc() returns the current discipline. Otherwise,
124 it changes the discipline of dt to disc. Objects may be rehashed,
125 reordered, or removed as appropriate. type can be any bit combination
126 of DT_SAMECMP and DT_SAMEHASH. DT_SAMECMP means that objects will com‐
127 pare exactly the same as before thus obviating the need for reordering
128 or removing new duplicates. DT_SAMEHASH means that hash values of
129 objects remain the same thus obviating the need to rehash. dtdisc()
130 returns the previous discipline on success and NULL on error.
131 Dt_t* dtview(Dt_t* dt, Dt_t* view)
133 A viewpath allows a search or walk starting from a dictionary to con‐
134 tinue to another. dtview() first terminates any current view from dt
135 to another dictionary. Then, if view is NULL, dtview returns the ter‐
136 minated view dictionary. If view is not NULL, a viewpath from dt to
137 view is established. dtview() returns dt on success and NULL on error.
138 If two dictionaries on the same viewpath have the same values for the
140 discipline fields Dtdisc_t.link, Dtdisc_t.key, Dtdisc_t.size, and
141 Dtdisc_t.hashf, it is expected that key hashing will be the same. If
142 not, undefined behaviors may result during a search or a walk.
143 STORAGE METHODS
145 Storage methods are of type Dtmethod_t*. Cdt supports the following
146 methods:
147 Dtoset
149 Dtobag
150 Objects are ordered by comparisons. Dtoset keeps unique objects. Dto‐
151 bag allows repeatable objects.
152 Dtset
154 Dtbag
155 Objects are unordered. Dtset keeps unique objects. Dtbag allows
156 repeatable objects and always keeps them together (note the effect on
157 dictionary walking.)
158 Dtlist
160 Objects are kept in a list. New objects are inserted either in front
161 of current object (see dtfinger()) if this is defined or at list front
162 if there is no current object.
163 Dtstack
165 Objects are kept in a stack, i.e., in reverse order of insertion.
166 Thus, the last object inserted is at stack top and will be the first to
167 be deleted.
168 Dtqueue
170 Objects are kept in a queue, i.e., in order of insertion. Thus, the
171 first object inserted is at queue head and will be the first to be
172 deleted.
173 DISCIPLINE
175 Object format and associated management functions are defined in the
176 type Dtdisc_t:
177 typedef struct
178 { int key, size;
179 int link;
180 Dtmake_f makef;
181 Dtfree_f freef;
182 Dtcompar_f comparf;
183 Dthash_f hashf;
184 Dtmemory_f memoryf;
185 Dtevent_f eventf;
186 } Dtdisc_t;
187 int key, size
189 Each object obj is identified by a key used for object comparison or
190 hashing. key should be non-negative and defines an offset into obj.
191 If size is negative, the key is a null-terminated string with starting
192 address *(Void_t**)((char*)obj+key). If size is zero, the key is a
193 null-terminated string with starting address (Void_t*)((char*)obj+key).
194 Finally, if size is positive, the key is a byte array of length size
195 starting at (Void_t*)((char*)obj+key).
196 int link
198 Let obj be an object to be inserted into dt as discussed below. If
199 link is negative, an internally allocated object holder is used to hold
200 obj. Otherwise, obj should have a Dtlink_t structure embedded link
201 bytes into it, i.e., at address (Dtlink_t*)((char*)obj+link).
202 Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)
204 If makef is not NULL, dtinsert(dt,obj) will call it to make a copy of
205 obj suitable for insertion into dt. If makef is NULL, obj itself will
206 be inserted into dt.
207 void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)
209 If not NULL, freef is used to destroy data associated with obj.
210 int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)
212 If not NULL, comparf is used to compare two keys. Its return value
213 should be <0, =0, or >0 to indicate whether key1 is smaller, equal to,
214 or larger than key2. All three values are significant for method
215 Dtoset and Dtobag. For other methods, a zero value indicates equality
216 and a non-zero value indicates inequality. If (*comparf)() is NULL, an
217 internal function is used to compare the keys as defined by the
218 Dtdisc_t.size field.
219 unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)
221 If not NULL, hashf is used to compute the hash value of key. It is
222 required that keys compared equal will also have same hash values. If
223 hashf is NULL, an internal function is used to hash the key as defined
224 by the Dtdisc_t.size field.
225 Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)
227 If not NULL, memoryf is used to allocate and free memory. When addr is
228 NULL, a memory segment of size size is requested. If addr is not NULL
229 and size is zero, addr is to be freed. If addr is not NULL and size is
230 positive, addr is to be resized to the given size. If memoryf is NULL,
231 malloc(3) is used. When dictionaries share memory, a record of the
232 first allocated memory segment should be kept so that it can be used to
233 initialize new dictionaries (see below.)
234 int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)
236 If not NULL, eventf announces various events. If it returns a negative
237 value, the calling operation will terminate with failure. Unless noted
238 otherwise, a non-negative return value let the calling function proceed
239 normally. Following are the events:
240 DT_OPEN:
242 dt is being opened. If eventf returns zero, the opening process
243 proceeds normally. A positive return value indicates that dt
244 uses memory already initialized by a different dictionary. In
245 that case, *(Void_t**)data should be set to the first allocated
246 memory segment as discussed in memoryf. dtopen() may fail if
247 this segment is not returned or if it has not been properly ini‐
248 tialized.
249 DT_CLOSE:
251 dt is being closed.
252 DT_DISC:
254 The discipline of dt is being changed to a new one given in
255 (Dtdisc_t*)data.
256 DT_METH:
258 The method of dt is being changed to a new one given in
259 (Dtmethod_t*)data.
260 OBJECT OPERATIONS
262 Void_t* dtinsert(Dt_t* dt, Void_t* obj)
263 This inserts an object prototyped by obj into dt. If there is an
264 existing object in dt matching obj and the storage method is Dtset or
265 Dtoset, dtinsert() will simply return the matching object. Otherwise,
266 a new object is inserted according to the method in use. See
267 Dtdisc_t.makef for object construction. dtinsert() returns the new
268 object, a matching object as noted, or NULL on error.
269 Void_t* dtdelete(Dt_t* dt, Void_t* obj)
271 If obj is not NULL, the first object matching it is deleted. If obj is
272 NULL, methods Dtstack and Dtqueue delete respectively stack top or
273 queue head while other methods do nothing. See Dtdisc_t.freef for
274 object destruction. dtdelete() returns the deleted object (even if it
275 was deallocated) or NULL on error.
276 Void_t* dtsearch(Dt_t* dt, Void_t* obj)
278 Void_t* dtmatch(Dt_t* dt, Void_t* key)
279 These functions find an object matching obj or key either from dt or
280 from some dictionary accessible from dt via a viewpath (see dtview().)
281 dtsearch() and dtmatch() return the matching object or NULL on failure.
282 Void_t* dtfirst(Dt_t* dt)
284 Void_t* dtnext(Dt_t* dt, Void_t* obj)
285 dtfirst() returns the first object in dt. dtnext() returns the object
286 following obj. Objects are ordered based on the storage method in use.
287 For Dtoset and Dtobag, objects are ordered by object comparisons. For
288 Dtstack, objects are ordered in reverse order of insertion. For
289 Dtqueue, objects are ordered in order of insertion. For Dtlist,
290 objects are ordered by list position. For Dtset and Dtbag, objects use
291 some internal ordering which may change on any search, insert, or
292 delete operations. Therefore, these operations should not be used dur‐
293 ing a walk on a dictionary using either Dtset or Dtbag.
294 Objects in a dictionary or a viewpath can be walked using a for(;;)
296 loop as below. Note that only one loop can be used at a time per dic‐
297 tionary. Concurrent or nested loops may result in unexpected behav‐
298 iors.
299 for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))
300 Void_t* dtlast(Dt_t* dt)
302 Void_t* dtprev(Dt_t* dt, Void_t* obj)
303 dtlast() and dtprev() are like dtfirst() and dtnext() but work in
304 reverse order. Note that dictionaries on a viewpath are still walked
305 in order but objects in each dictionary are walked in reverse order.
306 Void_t* dtfinger(Dt_t* dt)
308 This function returns the current object of dt, if any. The current
309 object is defined after a successful call to one of dtsearch(),
310 dtmatch(), dtinsert(), dtfirst(), dtnext(), dtlast(), or dtprev(). As
311 a side effect of this implementation of Cdt, when a dictionary is based
312 on Dtoset and Dtobag, the current object is always defined and is the
313 root of the tree.
314 Void_t* dtrenew(Dt_t* dt, Void_t* obj)
316 This function repositions and perhaps rehashes an object obj after its
317 key has been changed. dtrenew() only works if obj is the current
318 object (see dtfinger()).
319 dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)
321 This function calls (*userf)(walk,obj,data) on each object in dt and
322 other dictionaries viewable from it. walk is the dictionary containing
323 obj. If userf() returns a <0 value, dtwalk() terminates and returns
324 the same value. dtwalk() returns 0 on completion.
325 Dtlink_t* dtflatten(Dt_t* dt)
327 Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)
328 Void_t* dtobj(Dt_t* dt, Dtlink_t* link)
329 Using dtfirst()/dtnext() or dtlast()/dtprev() to walk a single dictio‐
330 nary can incur significant cost due to function calls. For efficient
331 walking of a single directory (i.e., no viewpathing), dtflatten() and
332 dtlink() can be used. Objects in dt are made into a linked list and
333 walked as follows:
334 for(link = dtflatten(dt); link; link = dtlink(dt,link) )
335 Note that dtflatten() returns a list of type Dtlink_t*, not Void_t*.
337 That is, it returns a dictionary holder pointer, not a user object
338 pointer (although both are the same if the discipline field link is
339 non-negative.) The macro function dtlink() returns the dictionary
340 holder object following link. The macro function dtobj(dt,link)
341 returns the user object associated with link, Beware that the flattened
342 object list is unflattened on any dictionary operations other than
343 dtlink().
344 Dtlink_t* dtextract(Dt_t* dt)
346 int dtrestore(Dt_t* dt, Dtlink_t* link)
347 dtextract() extracts all objects from dt and makes it appear empty.
348 dtrestore() repopulates dt with objects previously obtained via dtex‐
349 tract(). dtrestore() will fail if dt is not empty. These functions
350 can be used to share a same dt handle among many sets of objects. They
351 are useful to reduce dictionary overhead in an application that creates
352 concurrently many dictionaries. It is important that the same disci‐
353 pline and method are in use at both extraction and restoration. Other‐
354 wise, undefined behaviors may result.
355 DICTIONARY INFORMATION
357 Dt_t* dtvnext(Dt_t* dt)
358 This returns the dictionary that dt is viewing, if any.
359 int dtvcount(Dt_t* dt)
361 This returns the number of dictionaries that view dt.
362 Dt_t* dtvhere(Dt_t* dt)
364 This returns the dictionary v viewable from dt where an object was
365 found from the most recent search or walk operation.
366 int dtsize(Dt_t* dt)
368 This function returns the number of objects stored in dt.
369 int dtstat(Dt_t *dt, Dtstat_t* st, int all)
371 This function reports dictionary statistics. If all is non-zero, all
372 fields of st are filled. Otherwise, only the dt_type and dt_size
373 fields are filled. It returns 0 on success and -1 on error.
374 Dtstat_t contains the below fields:
376 int dt_type:
378 This is one of DT_SET, DT_BAG, DT_OSET, DT_OBAG, DT_LIST,
379 DT_STACK, and DT_QUEUE.
380 int dt_size:
382 This contains the number of objects in the dictionary.
383 int dt_n:
385 For Dtset and Dtbag, this is the number of non-empty chains in
386 the hash table. For Dtoset and Dtobag, this is the deepest
387 level in the tree (counting from zero.) Each level in the tree
388 contains all nodes of equal distance from the root node. dt_n
389 and the below two fields are undefined for other methods.
390 int dt_max:
392 For Dtbag and Dtset, this is the size of a largest chain. For
393 Dtoset and Dtobag, this is the size of a largest level.
394 int* dt_count:
396 For Dtset and Dtbag, this is the list of counts for chains of
397 particular sizes. For example, dt_count[1] is the number of
398 chains of size 1. For Dtoset and Dtobag, this is the list of
399 sizes of the levels. For example, dt_count[1] is the size of
400 level 1.
401 HASH FUNCTIONS
403 unsigned int dtcharhash(unsigned int h, char c)
404 unsigned int dtstrhash(unsigned int h, char* str, int n)
405 These functions compute hash values from bytes or strings.
406 dtcharhash() computes a new hash value from byte c and seed value h.
407 dtstrhash() computes a new hash value from string str and seed value h.
408 If n is positive, str is a byte array of length n; otherwise, str is a
409 null-terminated string.
410
412 Dtset and Dtbag are based on hash tables with move-to-front collision
413 chains. Dtoset and Dtobag are based on top-down splay trees. Dtlist,
414 Dtstack and Dtqueue are based on doubly linked list.
415
417 Kiem-Phong Vo, kpv@research.att.com
418 LIBCDT(3)