Mercurial > hg > camir-aes2014

annotate toolboxes/graph_visualisation/share/man/man3/cdt.3 @ 0:e9a9cd732c1e tip

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