cdt - Man Page
container data types
Synopsis
#include <cdt.h>
Dictionary Types
Dt_t; Dtdisc_t; Dtmethod_t; Dtlink_t; Dtstat_t;
Dictionary Control
Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth); int dtclose(Dt_t* dt); void dtclear(dt); Dtmethod_t* dtmethod(Dt_t* dt, const Dtmethod_t* meth); Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type); Dt_t* dtview(Dt_t* dt, Dt_t* view);
Storage Methods
Dtmethod_t* Dtset; Dtmethod_t* Dtbag; Dtmethod_t* Dtoset; Dtmethod_t* Dtobag; Dtmethod_t* Dtlist; Dtmethod_t* Dtstack; Dtmethod_t* Dtqueue; Dtmethod_t* Dtdeque;
Discipline
#define DTOFFSET(struct_s,member) #define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf) typedef void* (*Dtmake_f)(Dt_t*, void*, Dtdisc_t*); typedef void (*Dtfree_f)(Dt_t*, void*, Dtdisc_t*); typedef int (*Dtcompar_f)(Dt_t*, void*, void*, Dtdisc_t*); typedef unsigned int (*Dthash_f)(Dt_t*, void*, Dtdisc_t*); typedef void* (*Dtmemory_f)(Dt_t*, void*, size_t, Dtdisc_t*); typedef int (*Dtevent_f)(Dt_t*, int, void*, Dtdisc_t*);
Object Operations
void* dtinsert(Dt_t* dt, void* obj); void* dtappend(Dt_t* dt, void* obj); void* dtdelete(Dt_t* dt, void* obj); void* dtattach(Dt_t* dt, void* obj); void* dtdetach(Dt_t* dt, void* obj); void* dtsearch(Dt_t* dt, void* obj); void* dtmatch(Dt_t* dt, void* key); void* dtfirst(Dt_t* dt); void* dtnext(Dt_t* dt, void* obj); void* dtlast(Dt_t* dt); void* dtprev(Dt_t* dt, void* obj); void* dtfinger(Dt_t* dt); void* dtrenew(Dt_t* dt, void* obj); int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, void*, void*), void*); Dtlink_t* dtflatten(Dt_t* dt); Dtlink_t* dtlink(Dt_t*, Dtlink_t* link); void* dtobj(Dt_t* dt, Dtlink_t* link); Dtlink_t* dtextract(Dt_t* dt); int dtrestore(Dt_t* dt, Dtlink_t* link); #define DTTREESEARCH(Dt_t* dt, void* obj, action) #define DTTREEMATCH(Dt_t* dt, void* key, action)
Dictionary Status
Dt_t* dtvnext(Dt_t* dt); int dtvcount(Dt_t* dt); Dt_t* dtvhere(Dt_t* dt); int dtsize(Dt_t* dt); int dtstat(Dt_t* dt, Dtstat_t*, int all);
Hash Functions
unsigned int dtstrhash(unsigned int h, char* str, int n); unsigned int dtcharhash(unsigned int h, unsigned char c);
Description
Cdt manages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, stack, and queue.
Dictionary Types
Dt_t
This is the type of a dictionary handle.
Dtdisc_t
This defines the type of a discipline structure which describes object lay-out and manipulation functions.
Dtmethod_t
This defines the type of a container method.
Dtlink_t
This is the type of a dictionary object holder (see dtdisc()
.)
Dtstat_t
This is the type of a structure to return dictionary statistics (see dtstat()
.)
Dictionary Control
Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth)
This creates a new dictionary. disc
is a discipline structure to describe object format. meth
specifies a manipulation method. dtopen()
returns the new dictionary or NULL
on error. See also the events DT_OPEN
and DT_ENDOPEN
below.
int dtclose(Dt_t* dt)
This deletes dt
and its objects. Note that dtclose()
fails if dt
is being viewed by some other dictionaries (see dtview()
). dtclose()
returns 0
on success and -1
on error. See also the events DT_CLOSE
and DT_ENDCLOSE
below.
void dtclear(Dt_t* dt)
This deletes all objects in dt
without closing dt
.
Dtmethod_t dtmethod(Dt_t* dt, const Dtmethod_t* meth)
If meth
is NULL
, dtmethod()
returns the current method. Otherwise, it changes the storage method of dt
to meth
. Object order remains the same during a method switch among Dtlist
, Dtstack
, Dtqueue
and Dtdeque
. Switching to and from Dtset/Dtbag
and Dtoset/Dtobag
may cause objects to be rehashed, reordered, or removed as the case requires. dtmethod()
returns the previous method or NULL
on error.
Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type)
If disc
is NULL
, dtdisc()
returns the current discipline. Otherwise, it changes the discipline of dt
to disc
. Objects may be rehashed, reordered, or removed as appropriate. type
can be any bit combination of DT_SAMECMP
and DT_SAMEHASH
. DT_SAMECMP
means that objects will compare exactly the same as before thus obviating the need for reordering or removing new duplicates. DT_SAMEHASH
means that hash values of objects remain the same thus obviating the need to rehash. dtdisc()
returns the previous discipline on success and NULL
on error.
Dt_t* dtview(Dt_t* dt, Dt_t* view)
A viewpath allows a search or walk starting from a dictionary to continue to another. dtview()
first terminates any current view from dt
to another dictionary. Then, if view
is NULL
, dtview
returns the terminated view dictionary. If view
is not NULL
, a viewpath from dt
to view
is established. dtview()
returns dt
on success and NULL
on error.
It is an error to have dictionaries on a viewpath with different storage methods. In addition, dictionaries on the same view path should treat objects in a consistent manner with respect to comparison or hashing. If not, undefined behaviors may result.
Storage Methods
Storage methods are of type Dtmethod_t*
. Cdt supports the following methods:
Dtoset
Dtobag
Objects are ordered by comparisons. Dtoset
keeps unique objects. Dtobag
allows repeatable objects.
Dtset
Dtbag
Objects are unordered. Dtset
keeps unique objects. Dtbag
allows repeatable objects and always keeps them together (note the effect on dictionary walking.) These methods use a hash table with chaining to manage the objects. See also the event DT_HASHSIZE
below on how to manage hash table resizing when objects are inserted.
Dtlist
Objects are kept in a list. The call dtinsert()
inserts a new object in front of the current object (see dtfinger()
) if it is defined or at list front if no current object is defined. Similarly, the call dtappend()
appends a new object after the current object (see dtfinger()
) if it is defined or at list end if no current object is defined.
Dtdeque
Objects are kept in a deque. This is similar to Dtlist
except that objects are always inserted at the front and appended at the tail of the list.
Dtstack
Objects are kept in a stack, i.e., in reverse order of insertion. Thus, the last object inserted is at stack top and will be the first to be deleted.
Dtqueue
Objects are kept in a queue, i.e., in order of insertion. Thus, the first object inserted is at queue head and will be the first to be deleted.
Discipline
Object format and associated management functions are defined in the type Dtdisc_t
:
typedef struct { int key, size; int link; Dtmake_f makef; Dtfree_f freef; Dtcompar_f comparf; Dthash_f hashf; Dtmemory_f memoryf; Dtevent_f eventf; } Dtdisc_t;
int key, size
Each object obj
is identified by a key used for object comparison or hashing. key
should be non-negative and defines an offset into obj
. If size
is negative, the key is a null-terminated string with starting address *(void**)((char*)obj+key)
. If size
is zero, the key is a null-terminated string with starting address (void*)((char*)obj+key)
. Finally, if size
is positive, the key is a byte array of length size
starting at (void*)((char*)obj+key)
.
int link
Let obj
be an object to be inserted into dt
as discussed below. If link
is negative, an internally allocated object holder is used to hold obj
. Otherwise, obj
should have a Dtlink_t
structure embedded link
bytes into it, i.e., at address (Dtlink_t*)((char*)obj+link)
.
void* (*makef)(Dt_t* dt, void* obj, Dtdisc_t* disc)
If makef
is not NULL
, dtinsert(dt,obj)
or dtappend()
will call it to make a copy of obj
suitable for insertion into dt
. If makef
is NULL
, obj
itself will be inserted into dt
.
void (*freef)(Dt_t* dt, void* obj, Dtdisc_t* disc)
If not NULL
, freef
is used to destroy data associated with obj
.
int (*comparf)(Dt_t* dt, void* key1, void* key2, Dtdisc_t* disc)
If not NULL
, comparf
is used to compare two keys. Its return value should be <0
, =0
, or >0
to indicate whether key1
is smaller, equal to, or larger than key2
. All three values are significant for method Dtoset
and Dtobag
. For other methods, a zero value indicates equality and a non-zero value indicates inequality. If (*comparf)()
is NULL
, an internal function is used to compare the keys as defined by the Dtdisc_t.size
field.
unsigned int (*hashf)(Dt_t* dt, void* key, Dtdisc_t* disc)
If not NULL
, hashf
is used to compute the hash value of key
. It is required that keys compared equal will also have same hash values. If hashf
is NULL
, an internal function is used to hash the key as defined by the Dtdisc_t.size
field.
void* (*memoryf)(Dt_t* dt, void* addr, size_t size, Dtdisc_t* disc)
If not NULL
, memoryf
is used to allocate and free memory. When addr
is NULL
, a memory segment of size size
is requested. If addr
is not NULL
and size
is zero, addr
is to be freed. If addr
is not NULL
and size
is positive, addr
is to be resized to the given size. If memoryf
is NULL
, malloc(3) is used.
int (*eventf)(Dt_t* dt, int type, void* data, Dtdisc_t* disc)
If not NULL
, eventf
announces various events. Each event may have particular handling of the return values from eventf
. But a negative return value typically means failure. Following are the events:
- DT_OPEN:
dt
is being opened. Ifeventf
returns negative, the opening process terminates with failure. Ifeventf
returns zero, the opening process proceeds in a default manner. A positive return value indicates special treatment of memory as follows. If*(void**)data
is set to point to some memory segment as discussed inmemoryf
, that segment of memory is used to start the dictionary. If*(void**)data
isNULL
, all memory including that of the dictionary handle itself will be allocated viamemoryf
.- DT_ENDOPEN:
This event announces that
dtopen()
has successfully opened a dictionary and is about to return. Thedata
argument ofeventf
should be the new dictionary handle itself.- DT_CLOSE:
dt
is about to be closed. Ifeventf
returns negative, the closing process stops immediately anddtclose()
returns -1. Objects in the dictionary are deleted only ifeventf
returns zero. The dictionary handle itself is processed as follows. If it was allocated viamalloc()
, it will be freed. If it was allocated viamemoryf
(seedtopen()
) andeventf
returns 0, a call tomemoryf
will be issued to attempt freeing the handle. Otherwise, nothing will be done to its memory.As should be clear from their description, the events
DT_OPEN
andDT_CLOSE
are designed to be used along withmemoryf
to manage the allocation and deallocation of dictionary and object memory across dictionaries. In fact, they can be used to manage dictionaries based on shared and/or persistent memory.- DT_ENDCLOSE:
This event announces that
dtclose()
has successfully closed a dictionary and is about to return.- DT_DISC:
The discipline of
dt
is being changed to a new one given in(Dtdisc_t*)data
.- DT_METH:
The method of
dt
is being changed to a new one given in(Dtmethod_t*)data
.- DT_HASHSIZE:
The hash table (for
Dtset
andDtbag
) is being resized. In this case,*(int*)data
has the current size of the table. The application can set the new table size by first changing*(int*)data
to the desired size, then return a positive value. The application can also fix the table size at the current value forever by setting*(int*)data
to a negative value, then again return a positive value. A non-positive return value from the event handling function means that Cdt will be responsible for choosing the hash table size.
#define DTOFFSET(struct_s,member)
This macro function computes the offset of member
from the start of structure struct_s
. It is useful for getting the offset of a Dtlink_t
embedded inside an object.
#define DTDISC(disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf)
This macro function initializes the discipline pointed to by disc
with the given values.
Object Operations
void* dtinsert(Dt_t* dt, void* obj)
void* dtappend(Dt_t* dt, void* obj)
These functions add an object prototyped by obj
into dt
. dtinsert()
and dtappend()
perform the same function for all methods except for Dtlist
. See Dtlist
for details. If there is an existing object in dt
matching obj
and the storage method is Dtset
or Dtoset
, dtinsert()
and dtappend()
will simply return the matching object. Otherwise, a new object is inserted according to the method in use. See Dtdisc_t.makef
for object construction. The new object or a matching object as noted will be returned on success while NULL
is returned on error.
void* dtdelete(Dt_t* dt, void* obj)
If obj
is NULL
, methods Dtstack
and Dtqueue
delete respectively stack top or queue head while other methods do nothing. If obj
is not NULL
, there are two cases. If the method in use is not Dtbag
or Dtobag
, the first object matching obj
is deleted. On the other hand, if the method in use is Dtbag
or Dtobag
, the library check to see if obj
is in the dictionary and delete it. If obj
is not in the dictionary, some object matching it will be deleted. See Dtdisc_t.freef
for object destruction. dtdelete()
returns the deleted object (even if it was deallocated) or NULL
on error.
void* dtattach(Dt_t* dt, void* obj)
This function is similar to dtinsert()
but obj
itself will be inserted into dt
even if a discipline function makef
is defined.
void* dtdetach(Dt_t* dt, void* obj)
This function is similar to dtdelete()
but the object to be deleted from dt
will not be freed (via the discipline freef
function).
void* dtsearch(Dt_t* dt, void* obj)
void* dtmatch(Dt_t* dt, void* key)
These functions find an object matching obj
or key
either from dt
or from some dictionary accessible from dt
via a viewpath (see dtview()
.) dtsearch()
and dtmatch()
return the matching object or NULL
on failure.
void* dtfirst(Dt_t* dt)
void* dtnext(Dt_t* dt, void* obj)
dtfirst()
returns the first object in dt
. dtnext()
returns the object following obj
. Objects are ordered based on the storage method in use. For Dtoset
and Dtobag
, objects are ordered by object comparisons. For Dtstack
, objects are ordered in reverse order of insertion. For Dtqueue
, objects are ordered in order of insertion. For Dtlist
, objects are ordered by list position. For Dtset
and Dtbag
, objects are ordered by some internal order (more below). Thus, objects in a dictionary or a viewpath can be walked using a for(;;)
loop as below.
for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj))
When a dictionary uses Dtset
or Dtbag
, the object order is determined upon a call to dtfirst()
/dtlast()
. This order is frozen until a call dtnext()
/dtprev()
returns NULL
or when these same functions are called with a NULL
object argument. It is important that a dtfirst()/dtlast()
call be balanced by a dtnext()/dtprev()
call as described. Nested loops will require multiple balancing, once per loop. If loop balancing is not done carefully, either performance is degraded or unexpected behaviors may result.
void* dtlast(Dt_t* dt)
void* dtprev(Dt_t* dt, void* obj)
dtlast()
and dtprev()
are like dtfirst()
and dtnext()
but work in reverse order. Note that dictionaries on a viewpath are still walked in order but objects in each dictionary are walked in reverse order.
void* dtfinger(Dt_t* dt)
This function returns the current object of dt
, if any. The current object is defined after a successful call to one of dtsearch()
, dtmatch()
, dtinsert()
, dtfirst()
, dtnext()
, dtlast()
, or dtprev()
. As a side effect of this implementation of Cdt, when a dictionary is based on Dtoset
and Dtobag
, the current object is always defined and is the root of the tree.
void* dtrenew(Dt_t* dt, void* obj)
This function repositions and perhaps rehashes an object obj
after its key has been changed. dtrenew()
only works if obj
is the current object (see dtfinger()
).
dtwalk(Dt_t* dt, int (*userf)(Dt_t*, void*, void*), void* data)
This function calls (*userf)(walk,obj,data)
on each object in dt
and other dictionaries viewable from it. walk
is the dictionary containing obj
. If userf()
returns a <0
value, dtwalk()
terminates and returns the same value. dtwalk()
returns 0
on completion.
Dtlink_t* dtflatten(Dt_t* dt)
Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)
void* dtobj(Dt_t* dt, Dtlink_t* link)
Using dtfirst()/dtnext()
or dtlast()/dtprev()
to walk a single dictionary can incur significant cost due to function calls. For efficient walking of a single directory (i.e., no viewpathing), dtflatten()
and dtlink()
can be used. Objects in dt
are made into a linked list and walked as follows:
for(link = dtflatten(dt); link; link = dtlink(dt,link) )
Note that dtflatten()
returns a list of type Dtlink_t*
, not void*
. That is, it returns a dictionary holder pointer, not a user object pointer (although both are the same if the discipline field link
is zero.) The macro function dtlink()
returns the dictionary holder object following link
. The macro function dtobj(dt,link)
returns the user object associated with link
, Beware that the flattened object list is unflattened on any dictionary operations other than dtlink()
.
Dtlink_t* dtextract(Dt_t* dt)
int dtrestore(Dt_t* dt, Dtlink_t* link)
dtextract()
extracts all objects from dt
and makes it appear empty. dtrestore()
repopulates dt
with objects previously obtained via dtextract()
. dtrestore()
will fail if dt
is not empty. These functions can be used to share a same dt
handle among many sets of objects. They are useful to reduce dictionary overhead in an application that creates many concurrent dictionaries. It is important that the same discipline and method are in use at both extraction and restoration. Otherwise, undefined behaviors may result.
#define DTTREESEARCH(Dt_t* dt, void* obj, action)
#define DTTREEMATCH(Dt_t* dt, void* key, action)
These macro functions are analogues of dtsearch()
and dtmatch()
but they can only be used on a dictionary based on a binary search tree, i.e., Dtoset
or Dtobag
.
- obj or key:
These are used to find a matching object. If there is no match, the result is
NULL
.- action:
The matching object
o
(which may beNULL
) will be processed as follow:action (o);
Since
action
is used verbatim, it can be any C code fragment combinable with(o)
to form a syntactically correct C statement. For example, suppose that the matching object is an integer, the below code accumulates the integer value in a variabletotal
:DTTREEMATCH(dt, key, total += (int));
Dictionary Information
Dt_t* dtvnext(Dt_t* dt)
This returns the dictionary that dt
is viewing, if any.
int dtvcount(Dt_t* dt)
This returns the number of dictionaries that view dt
.
Dt_t* dtvhere(Dt_t* dt)
This returns the dictionary v
viewable from dt
where an object was found from the most recent search or walk operation.
int dtsize(Dt_t* dt)
This function returns the number of objects stored in dt
.
int dtstat(Dt_t *dt, Dtstat_t* st, int all)
This function reports dictionary statistics. If all
is non-zero, all fields of st
are filled. Otherwise, only the dt_type
and dt_size
fields are filled. It returns 0
on success and -1
on error.
Dtstat_t
contains the below fields:
- int dt_type:
This is one of
DT_SET
,DT_BAG
,DT_OSET
,DT_OBAG
,DT_LIST
,DT_STACK
, andDT_QUEUE
.- int dt_size:
This contains the number of objects in the dictionary.
- int dt_n:
For
Dtset
andDtbag
, this is the number of non-empty chains in the hash table. ForDtoset
andDtobag
, this is the deepest level in the tree (counting from zero.) Each level in the tree contains all nodes of equal distance from the root node.dt_n
and the below two fields are undefined for other methods.- int dt_max:
For
Dtbag
andDtset
, this is the size of a largest chain. ForDtoset
andDtobag
, this is the size of a largest level.- int* dt_count:
For
Dtset
andDtbag
, this is the list of counts for chains of particular sizes. For example,dt_count[1]
is the number of chains of size1
. ForDtoset
andDtobag
, this is the list of sizes of the levels. For example,dt_count[1]
is the size of level1
.
Hash Functions
unsigned int dtcharhash(unsigned int h, char c)
unsigned int dtstrhash(unsigned int h, char* str, int n)
These functions compute hash values from bytes or strings. dtcharhash()
computes a new hash value from byte c
and seed value h
. dtstrhash()
computes a new hash value from string str
and seed value h
. If n
is positive, str
is a byte array of length n
; otherwise, str
is a null-terminated string.
Implementation Notes
Dtset
and Dtbag
are based on hash tables with move-to-front collision chains. Dtoset
and Dtobag
are based on top-down splay trees. Dtlist
, Dtstack
and Dtqueue
are based on doubly linked list.
Author
Kiem-Phong Vo, kpv@research.att.com