3
\fBCdt\fR \- container data types
23
.ta 1.0i 2.0i 3.0i 4.0i 5.0i
27
.Ss "DICTIONARY TYPES"
36
.Ss "DICTIONARY CONTROL"
38
Dt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth);
39
int dtclose(Dt_t* dt);
41
Dtmethod_t* dtmethod(Dt_t* dt, Dtmethod_t* meth);
42
Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type);
43
Dt_t* dtview(Dt_t* dt, Dt_t* view);
57
typedef Void_t* (*Dtmake_f)(Dt_t*, Void_t*, Dtdisc_t*);
58
typedef void (*Dtfree_f)(Dt_t*, Void_t*, Dtdisc_t*);
59
typedef int (*Dtcompar_f)(Dt_t*, Void_t*, Void_t*, Dtdisc_t*);
60
typedef unsigned int (*Dthash_f)(Dt_t*, Void_t*, Dtdisc_t*);
61
typedef Void_t* (*Dtmemory_f)(Dt_t*, Void_t*, size_t, Dtdisc_t*);
62
typedef int (*Dtevent_f)(Dt_t*, int, Void_t*, Dtdisc_t*);
64
.Ss "OBJECT OPERATIONS"
66
Void_t* dtinsert(Dt_t* dt, Void_t* obj);
67
Void_t* dtdelete(Dt_t* dt, Void_t* obj);
68
Void_t* dtsearch(Dt_t* dt, Void_t* obj);
69
Void_t* dtmatch(Dt_t* dt, Void_t* key);
70
Void_t* dtfirst(Dt_t* dt);
71
Void_t* dtnext(Dt_t* dt, Void_t* obj);
72
Void_t* dtlast(Dt_t* dt);
73
Void_t* dtprev(Dt_t* dt, Void_t* obj);
74
Void_t* dtfinger(Dt_t* dt);
75
Void_t* dtrenew(Dt_t* dt, Void_t* obj);
76
int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t*);
77
Dtlink_t* dtflatten(Dt_t* dt);
78
Dtlink_t* dtlink(Dt_t*, Dtlink_t* link);
79
Void_t* dtobj(Dt_t* dt, Dtlink_t* link);
80
Dtlink_t* dtextract(Dt_t* dt);
81
int dtrestore(Dt_t* dt, Dtlink_t* link);
83
.Ss "DICTIONARY STATUS"
85
Dt_t* dtvnext(Dt_t* dt);
86
int dtvcount(Dt_t* dt);
87
Dt_t* dtvhere(Dt_t* dt);
89
int dtstat(Dt_t* dt, Dtstat_t*, int all);
93
unsigned int dtstrhash(unsigned int h, char* str, int n);
94
unsigned int dtcharhash(unsigned int h, unsigned char c);
98
\fICdt\fP manages run-time dictionaries using standard container data types:
99
unordered set/multiset, ordered set/multiset, list, stack, and queue.
101
.Ss "DICTIONARY TYPES"
104
This type is used to pass objects between \fICdt\fP and application code.
105
\f5Void_t\fP is defined as \f5void\fP for ANSI-C and C++
106
and \f5char\fP for other compilation environments.
109
This is the type of a dictionary handle.
112
This defines the type of a discipline structure which describes
113
object lay-out and manipulation functions.
116
This defines the type of a container method.
119
This is the type of a dictionary object holder (see \f5dtdisc()\fP.)
122
This is the type of a structure to return dictionary statistics (see \f5dtstat()\fP.)
124
.Ss "DICTIONARY CONTROL"
126
.Ss " Dt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth)"
127
This creates a new dictionary.
128
\f5disc\fP is a discipline structure to describe object format.
129
\f5meth\fP specifies a manipulation method.
130
\f5dtopen()\fP returns the new dictionary or \f5NULL\fP on error.
132
.Ss " int dtclose(Dt_t* dt)"
133
This deletes \f5dt\fP and its objects.
134
Note that \f5dtclose()\fP fails if \f5dt\fP is being viewed by
135
some other dictionaries (see \f5dtview()\fP).
136
\f5dtclose()\fP returns \f50\fP on success and \f5-1\fP on error.
138
.Ss " void dtclear(Dt_t* dt)"
139
This deletes all objects in \f5dt\fP without closing \f5dt\fP.
141
.Ss " Dtmethod_t dtmethod(Dt_t* dt, Dtmethod_t* meth)"
142
If \f5meth\fP is \f5NULL\fP, \f5dtmethod()\fP returns the current method.
143
Otherwise, it changes the storage method of \f5dt\fP to \f5meth\fP.
144
Object order remains the same during a
145
method switch among \f5Dtlist\fP, \f5Dtstack\fP and \f5Dtqueue\fP.
146
Switching to and from \f5Dtset/Dtbag\fP and \f5Dtoset/Dtobag\fP may cause
147
objects to be rehashed, reordered, or removed as the case requires.
148
\f5dtmethod()\fP returns the previous method or \f5NULL\fP on error.
150
.Ss " Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type)"
151
If \f5disc\fP is \f5NULL\fP, \f5dtdisc()\fP returns the current discipline.
152
Otherwise, it changes the discipline of \f5dt\fP to \f5disc\fP.
153
Objects may be rehashed, reordered, or removed as appropriate.
154
\f5type\fP can be any bit combination of \f5DT_SAMECMP\fP and \f5DT_SAMEHASH\fP.
155
\f5DT_SAMECMP\fP means that objects will compare exactly the same as before
156
thus obviating the need for reordering or removing new duplicates.
157
\f5DT_SAMEHASH\fP means that hash values of objects remain the same
158
thus obviating the need to rehash.
159
\f5dtdisc()\fP returns the previous discipline on success
160
and \f5NULL\fP on error.
162
.Ss " Dt_t* dtview(Dt_t* dt, Dt_t* view)"
163
A viewpath allows a search or walk starting from a dictionary to continue to another.
164
\f5dtview()\fP first terminates any current view from \f5dt\fP to another dictionary.
165
Then, if \f5view\fP is \f5NULL\fP, \f5dtview\fP returns the terminated view dictionary.
166
If \f5view\fP is not \f5NULL\fP, a viewpath from \f5dt\fP to \f5view\fP is established.
167
\f5dtview()\fP returns \f5dt\fP on success and \f5NULL\fP on error.
169
If two dictionaries on the same viewpath have the same values for the discipline fields
170
\f5Dtdisc_t.link\fP, \f5Dtdisc_t.key\fP, \f5Dtdisc_t.size\fP, and \f5Dtdisc_t.hashf\fP,
171
it is expected that key hashing will be the same.
172
If not, undefined behaviors may result during a search or a walk.
174
.Ss "STORAGE METHODS"
176
Storage methods are of type \f5Dtmethod_t*\fP.
177
\fICdt\fP supports the following methods:
181
Objects are ordered by comparisons.
182
\f5Dtoset\fP keeps unique objects.
183
\f5Dtobag\fP allows repeatable objects.
187
Objects are unordered.
188
\f5Dtset\fP keeps unique objects.
189
\f5Dtbag\fP allows repeatable objects and always keeps them together
190
(note the effect on dictionary walking.)
193
Objects are kept in a list.
194
New objects are inserted either
195
in front of \fIcurrent object\fP (see \f5dtfinger()\fP) if this is defined
196
or at list front if there is no current object.
199
Objects are kept in a stack, i.e., in reverse order of insertion.
200
Thus, the last object inserted is at stack top
201
and will be the first to be deleted.
204
Objects are kept in a queue, i.e., in order of insertion.
205
Thus, the first object inserted is at queue head
206
and will be the first to be deleted.
210
Object format and associated management functions are
211
defined in the type \f5Dtdisc_t\fP:
225
Each object \f5obj\fP is identified by a key used for object comparison or hashing.
226
\f5key\fP should be non-negative and defines an offset into \f5obj\fP.
227
If \f5size\fP is negative, the key is a null-terminated
228
string with starting address \f5*(Void_t**)((char*)obj+key)\fP.
229
If \f5size\fP is zero, the key is a null-terminated string with starting address
230
\f5(Void_t*)((char*)obj+key)\fP.
231
Finally, if \f5size\fP is positive, the key is a byte array of length \f5size\fP
232
starting at \f5(Void_t*)((char*)obj+key)\fP.
235
Let \f5obj\fP be an object to be inserted into \f5dt\fP as discussed below.
236
If \f5link\fP is negative, an internally allocated object holder is used
237
to hold \f5obj\fP. Otherwise, \f5obj\fP should have
238
a \f5Dtlink_t\fP structure embedded \f5link\fP bytes into it,
239
i.e., at address \f5(Dtlink_t*)((char*)obj+link)\fP.
241
.Ss " Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)"
242
If \f5makef\fP is not \f5NULL\fP,
243
\f5dtinsert(dt,obj)\fP will call it
244
to make a copy of \f5obj\fP suitable for insertion into \f5dt\fP.
245
If \f5makef\fP is \f5NULL\fP, \f5obj\fP itself will be inserted into \f5dt\fP.
247
.Ss " void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)"
249
\f5freef\fP is used to destroy data associated with \f5obj\fP.
251
.Ss "int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)"
252
If not \f5NULL\fP, \f5comparf\fP is used to compare two keys.
253
Its return value should be \f5<0\fP, \f5=0\fP, or \f5>0\fP to indicate
254
whether \f5key1\fP is smaller, equal to, or larger than \f5key2\fP.
255
All three values are significant for method \f5Dtoset\fP and \f5Dtobag\fP.
256
For other methods, a zero value
257
indicates equality and a non-zero value indicates inequality.
258
If \f5(*comparf)()\fP is \f5NULL\fP, an internal function is used
259
to compare the keys as defined by the \f5Dtdisc_t.size\fP field.
261
.Ss " unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)"
263
\f5hashf\fP is used to compute the hash value of \f5key\fP.
264
It is required that keys compared equal will also have same hash values.
265
If \f5hashf\fP is \f5NULL\fP, an internal function is used to hash
266
the key as defined by the \f5Dtdisc_t.size\fP field.
268
.Ss " Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)"
269
If not \f5NULL\fP, \f5memoryf\fP is used to allocate and free memory.
270
When \f5addr\fP is \f5NULL\fP, a memory segment of size \f5size\fP is requested.
271
If \f5addr\fP is not \f5NULL\fP and \f5size\fP is zero, \f5addr\fP is to be freed.
272
If \f5addr\fP is not \f5NULL\fP and \f5size\fP is positive,
273
\f5addr\fP is to be resized to the given size.
274
If \f5memoryf\fP is \f5NULL\fP, \fImalloc(3)\fP is used.
275
When dictionaries share memory,
276
a record of the first allocated memory segment should be kept
277
so that it can be used to initialize new dictionaries (see below.)
279
.Ss " int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)"
280
If not \f5NULL\fP, \f5eventf\fP announces various events.
281
If it returns a negative value, the calling operation will terminate with failure.
282
Unless noted otherwise, a non-negative return value let the
283
calling function proceed normally. Following are the events:
286
\f5dt\fP is being opened.
287
If \f5eventf\fP returns zero, the opening process proceeds normally.
288
A positive return value indicates that \f5dt\fP
289
uses memory already initialized by a different dictionary.
290
In that case, \f5*(Void_t**)data\fP should be set to
291
the first allocated memory segment as discussed in \f5memoryf\fP.
292
\f5dtopen()\fP may fail if this segment is not returned or
293
if it has not been properly initialized.
296
\f5dt\fP is being closed.
299
The discipline of \f5dt\fP is being changed to a new one given in
300
\f5(Dtdisc_t*)data\fP.
303
The method of \f5dt\fP is being changed to a new one given in
304
\f5(Dtmethod_t*)data\fP.
306
.Ss "OBJECT OPERATIONS"
308
.Ss " Void_t* dtinsert(Dt_t* dt, Void_t* obj)"
309
This inserts an object prototyped by \f5obj\fP into \f5dt\fP.
310
If there is an existing object in \f5dt\fP matching \f5obj\fP
311
and the storage method is \f5Dtset\fP or \f5Dtoset\fP,
312
\f5dtinsert()\fP will simply return the matching object.
313
Otherwise, a new object is inserted according to the method in use.
314
See \f5Dtdisc_t.makef\fP for object construction.
315
\f5dtinsert()\fP returns the new object, a matching object as noted,
316
or \f5NULL\fP on error.
318
.Ss " Void_t* dtdelete(Dt_t* dt, Void_t* obj)"
319
If \f5obj\fP is not \f5NULL\fP, the first object matching it is deleted.
320
If \f5obj\fP is \f5NULL\fP, methods \f5Dtstack\fP and \f5Dtqueue\fP
321
delete respectively stack top or queue head while other methods do nothing.
322
See \f5Dtdisc_t.freef\fP for object destruction.
323
\f5dtdelete()\fP returns the deleted object (even if it was deallocated)
324
or \f5NULL\fP on error.
326
.Ss " Void_t* dtsearch(Dt_t* dt, Void_t* obj)"
327
.Ss " Void_t* dtmatch(Dt_t* dt, Void_t* key)"
328
These functions find an object matching \f5obj\fP or \f5key\fP either from \f5dt\fP or
329
from some dictionary accessible from \f5dt\fP via a viewpath (see \f5dtview()\fP.)
330
\f5dtsearch()\fP and \f5dtmatch()\fP return the matching object or
331
\f5NULL\fP on failure.
333
.Ss " Void_t* dtfirst(Dt_t* dt)"
334
.Ss " Void_t* dtnext(Dt_t* dt, Void_t* obj)"
335
\f5dtfirst()\fP returns the first object in \f5dt\fP.
336
\f5dtnext()\fP returns the object following \f5obj\fP.
337
Objects are ordered based on the storage method in use.
338
For \f5Dtoset\fP and \f5Dtobag\fP, objects are ordered by object comparisons.
339
For \f5Dtstack\fP, objects are ordered in reverse order of insertion.
340
For \f5Dtqueue\fP, objects are ordered in order of insertion.
341
For \f5Dtlist\fP, objects are ordered by list position.
342
For \f5Dtset\fP and \f5Dtbag\fP,
343
objects use some internal ordering which
344
may change on any search, insert, or delete operations.
345
Therefore, these operations should not be used
346
during a walk on a dictionary using either \f5Dtset\fP or \f5Dtbag\fP.
348
Objects in a dictionary or a viewpath can be walked using
349
a \f5for(;;)\fP loop as below.
350
Note that only one loop can be used at a time per dictionary.
351
Concurrent or nested loops may result in unexpected behaviors.
353
for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))
355
.Ss " Void_t* dtlast(Dt_t* dt)"
356
.Ss " Void_t* dtprev(Dt_t* dt, Void_t* obj)"
357
\f5dtlast()\fP and \f5dtprev()\fP are like \f5dtfirst()\fP and \f5dtnext()\fP
358
but work in reverse order.
359
Note that dictionaries on a viewpath are still walked in order
360
but objects in each dictionary are walked in reverse order.
362
.Ss " Void_t* dtfinger(Dt_t* dt)"
363
This function returns the \fIcurrent object\fP of \f5dt\fP, if any.
364
The current object is defined after a successful call to one of
365
\f5dtsearch()\fP, \f5dtmatch()\fP, \f5dtinsert()\fP,
366
\f5dtfirst()\fP, \f5dtnext()\fP, \f5dtlast()\fP, or \f5dtprev()\fP.
367
As a side effect of this implementation of \fICdt\fP,
368
when a dictionary is based on \f5Dtoset\fP and \f5Dtobag\fP,
369
the current object is always defined and is the root of the tree.
371
.Ss " Void_t* dtrenew(Dt_t* dt, Void_t* obj)"
372
This function repositions and perhaps rehashes
373
an object \f5obj\fP after its key has been changed.
374
\f5dtrenew()\fP only works if \f5obj\fP is the current object (see \f5dtfinger()\fP).
376
.Ss " dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)"
377
This function calls \f5(*userf)(walk,obj,data)\fP on each object in \f5dt\fP and
378
other dictionaries viewable from it.
379
\f5walk\fP is the dictionary containing \f5obj\fP.
380
If \f5userf()\fP returns a \f5<0\fP value,
381
\f5dtwalk()\fP terminates and returns the same value.
382
\f5dtwalk()\fP returns \f50\fP on completion.
384
.Ss " Dtlink_t* dtflatten(Dt_t* dt)"
385
.Ss " Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)"
386
.Ss " Void_t* dtobj(Dt_t* dt, Dtlink_t* link)"
387
Using \f5dtfirst()/dtnext()\fP or \f5dtlast()/dtprev()\fP
388
to walk a single dictionary can incur significant cost due to function calls.
389
For efficient walking of a single directory (i.e., no viewpathing),
390
\f5dtflatten()\fP and \f5dtlink()\fP can be used.
391
Objects in \f5dt\fP are made into a linked list and walked as follows:
393
for(link = dtflatten(dt); link; link = dtlink(dt,link) )
396
Note that \f5dtflatten()\fP returns a list of type \f5Dtlink_t*\fP,
397
not \f5Void_t*\fP. That is, it returns a dictionary holder pointer,
398
not a user object pointer
399
(although both are the same if the discipline field \f5link\fP is non-negative.)
400
The macro function \f5dtlink()\fP
401
returns the dictionary holder object following \f5link\fP.
402
The macro function \f5dtobj(dt,link)\fP
403
returns the user object associated with \f5link\fP,
404
Beware that the flattened object list is unflattened on any
405
dictionary operations other than \f5dtlink()\fP.
407
.Ss " Dtlink_t* dtextract(Dt_t* dt)"
408
.Ss " int dtrestore(Dt_t* dt, Dtlink_t* link)"
409
\f5dtextract()\fP extracts all objects from \f5dt\fP and makes it appear empty.
410
\f5dtrestore()\fP repopulates \f5dt\fP with
411
objects previously obtained via \f5dtextract()\fP.
412
\f5dtrestore()\fP will fail if \f5dt\fP is not empty.
413
These functions can be used
414
to share a same \f5dt\fP handle among many sets of objects.
415
They are useful to reduce dictionary overhead
416
in an application that creates concurrently many dictionaries.
417
It is important that the same discipline and method are in use at both
418
extraction and restoration. Otherwise, undefined behaviors may result.
420
.Ss "DICTIONARY INFORMATION"
422
.Ss " Dt_t* dtvnext(Dt_t* dt)"
423
This returns the dictionary that \f5dt\fP is viewing, if any.
424
.Ss " int dtvcount(Dt_t* dt)"
425
This returns the number of dictionaries that view \f5dt\fP.
426
.Ss " Dt_t* dtvhere(Dt_t* dt)"
427
This returns the dictionary \f5v\fP viewable from \f5dt\fP
428
where an object was found from the most recent search or walk operation.
429
.Ss " int dtsize(Dt_t* dt)"
430
This function returns the number of objects stored in \f5dt\fP.
432
.Ss " int dtstat(Dt_t *dt, Dtstat_t* st, int all)"
433
This function reports dictionary statistics.
434
If \f5all\fP is non-zero, all fields of \f5st\fP are filled.
435
Otherwise, only the \f5dt_type\fP and \f5dt_size\fP fields are filled.
436
It returns \f50\fP on success and \f5-1\fP on error.
438
\f5Dtstat_t\fP contains the below fields:
441
This is one of \f5DT_SET\fP, \f5DT_BAG\fP, \f5DT_OSET\fP, \f5DT_OBAG\fP,
442
\f5DT_LIST\fP, \f5DT_STACK\fP, and \f5DT_QUEUE\fP.
445
This contains the number of objects in the dictionary.
448
For \f5Dtset\fP and \f5Dtbag\fP,
449
this is the number of non-empty chains in the hash table.
450
For \f5Dtoset\fP and \f5Dtobag\fP,
451
this is the deepest level in the tree (counting from zero.)
452
Each level in the tree contains all nodes of equal distance from the root node.
453
\f5dt_n\fP and the below two fields are undefined for other methods.
456
For \f5Dtbag\fP and \f5Dtset\fP, this is the size of a largest chain.
457
For \f5Dtoset\fP and \f5Dtobag\fP, this is the size of a largest level.
460
For \f5Dtset\fP and \f5Dtbag\fP,
461
this is the list of counts for chains of particular sizes.
462
For example, \f5dt_count[1]\fP is the number of chains of size \f51\fP.
463
For \f5Dtoset\fP and \f5Dtobag\fP, this is the list of sizes of the levels.
464
For example, \f5dt_count[1]\fP is the size of level \f51\fP.
468
.Ss " unsigned int dtcharhash(unsigned int h, char c)"
469
.Ss " unsigned int dtstrhash(unsigned int h, char* str, int n)"
470
These functions compute hash values from bytes or strings.
471
\f5dtcharhash()\fP computes a new hash value from byte \f5c\fP and seed value \f5h\fP.
472
\f5dtstrhash()\fP computes a new hash value from string \f5str\fP and seed value \f5h\fP.
473
If \f5n\fP is positive, \f5str\fP is a byte array of length \f5n\fP;
474
otherwise, \f5str\fP is a null-terminated string.
476
.SH IMPLEMENTATION NOTES
477
\f5Dtset\fP and \f5Dtbag\fP are based on hash tables with
478
move-to-front collision chains.
479
\f5Dtoset\fP and \f5Dtobag\fP are based on top-down splay trees.
480
\f5Dtlist\fP, \f5Dtstack\fP and \f5Dtqueue\fP are based on doubly linked list.
483
Kiem-Phong Vo, kpv@research.att.com
added
removed
cdt/cdt.3
