NAME
Cdt - container data types
SYNOPSIS
DICTIONARY TYPES
DICTIONARY CONTROL
STORAGE METHODS
DISCIPLINE
OBJECT OPERATIONS
DICTIONARY STATUS
HASH FUNCTIONS
DESCRIPTION
Cdt manages run-time dictionaries using standard container data types:
unordered set/multiset, ordered set/multiset, list, stack, and queue.
DICTIONARY TYPES
Void_t*
This type is used to pass objects between Cdt and application code.
is defined as for ANSI-C and C++ and for other compilation
environments.
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 .)
Dtstat_t
This is the type of a structure to return dictionary statistics (see .)
DICTIONARY CONTROL
Dt_t* dtopen(Dtdisc_t* disc, Dtmethod_t* meth)
This creates a new dictionary. is a discipline structure to describe
object format. specifies a manipulation method. returns the new
dictionary or on error.
int dtclose(Dt_t* dt)
This deletes and its objects. Note that fails if is being viewed by
some other dictionaries (see ). returns on success and on error.
void dtclear(Dt_t* dt)
This deletes all objects in without closing .
Dtmethod_t dtmethod(Dt_t* dt, Dtmethod_t* meth)
If is , returns the current method. Otherwise, it changes the
storage method of to . Object order remains the same during a method
switch among , and . Switching to and from and may cause objects to
be rehashed, reordered, or removed as the case requires. returns the
previous method or on error.
Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type)
If is , returns the current discipline. Otherwise, it changes the
discipline of to . Objects may be rehashed, reordered, or removed as
appropriate. can be any bit combination of and . means that
objects will compare exactly the same as before thus obviating the need
for reordering or removing new duplicates. means that hash values of
objects remain the same thus obviating the need to rehash. returns
the previous discipline on success and 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. first terminates any current view from to
another dictionary. Then, if is , returns the terminated view
dictionary. If is not , a viewpath from to is established.
returns on success and on error.
If two dictionaries on the same viewpath have the same values for the
discipline fields , , , and , it is expected that key hashing will be
the same. If not, undefined behaviors may result during a search or a
walk.
STORAGE METHODS
Storage methods are of type . Cdt supports the following methods:
Dtoset
Dtobag
Objects are ordered by comparisons. keeps unique objects. allows
repeatable objects.
Dtset
Dtbag
Objects are unordered. keeps unique objects. allows repeatable
objects and always keeps them together (note the effect on dictionary
walking.)
Dtlist
Objects are kept in a list. New objects are inserted either in front
of current object (see ) if this is defined or at list front if there
is no current object.
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 :
int key, size
Each object is identified by a key used for object comparison or
hashing. should be non-negative and defines an offset into . If is
negative, the key is a null-terminated string with starting address .
If is zero, the key is a null-terminated string with starting address
. Finally, if is positive, the key is a byte array of length starting
at .
int link
Let be an object to be inserted into as discussed below. If is
negative, an internally allocated object holder is used to hold .
Otherwise, should have a structure embedded bytes into it, i.e., at
address .
Void_t* (*makef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)
If is not , will call it to make a copy of suitable for insertion
into . If is , itself will be inserted into .
void (*freef)(Dt_t* dt, Void_t* obj, Dtdisc_t* disc)
If not , is used to destroy data associated with .
int (*comparf)(Dt_t* dt, Void_t* key1, Void_t* key2, Dtdisc_t* disc)
If not , is used to compare two keys. Its return value should be , ,
or to indicate whether is smaller, equal to, or larger than . All
three values are significant for method and . For other methods, a
zero value indicates equality and a non-zero value indicates
inequality. If is , an internal function is used to compare the keys
as defined by the field.
unsigned int (*hashf)(Dt_t* dt, Void_t* key, Dtdisc_t* disc)
If not , is used to compute the hash value of . It is required that
keys compared equal will also have same hash values. If is , an
internal function is used to hash the key as defined by the field.
Void_t* (*memoryf)(Dt_t* dt, Void_t* addr, size_t size, Dtdisc_t* disc)
If not , is used to allocate and free memory. When is , a memory
segment of size is requested. If is not and is zero, is to be
freed. If is not and is positive, is to be resized to the given
size. If is , malloc(3) is used. When dictionaries share memory, a
record of the first allocated memory segment should be kept so that it
can be used to initialize new dictionaries (see below.)
int (*eventf)(Dt_t* dt, int type, Void_t* data, Dtdisc_t* disc)
If not , announces various events. If it returns a negative value,
the calling operation will terminate with failure. Unless noted
otherwise, a non-negative return value let the calling function proceed
normally. Following are the events:
: is being opened. If returns zero, the opening process
proceeds normally. A positive return value indicates that uses
memory already initialized by a different dictionary. In that
case, should be set to the first allocated memory segment as
discussed in . may fail if this segment is not returned or if
it has not been properly initialized.
: is being closed.
: The discipline of is being changed to a new one given in .
: The method of is being changed to a new one given in .
OBJECT OPERATIONS
Void_t* dtinsert(Dt_t* dt, Void_t* obj)
This inserts an object prototyped by into . If there is an existing
object in matching and the storage method is or , will simply return
the matching object. Otherwise, a new object is inserted according to
the method in use. See for object construction. returns the new
object, a matching object as noted, or on error.
Void_t* dtdelete(Dt_t* dt, Void_t* obj)
If is not , the first object matching it is deleted. If is , methods
and delete respectively stack top or queue head while other methods do
nothing. See for object destruction. returns the deleted object
(even if it was deallocated) or on error.
Void_t* dtsearch(Dt_t* dt, Void_t* obj)
Void_t* dtmatch(Dt_t* dt, Void_t* key)
These functions find an object matching or either from or from some
dictionary accessible from via a viewpath (see .) and return the
matching object or on failure.
Void_t* dtfirst(Dt_t* dt)
Void_t* dtnext(Dt_t* dt, Void_t* obj)
returns the first object in . returns the object following .
Objects are ordered based on the storage method in use. For and ,
objects are ordered by object comparisons. For , objects are ordered
in reverse order of insertion. For , objects are ordered in order of
insertion. For , objects are ordered by list position. For and ,
objects use some internal ordering which may change on any search,
insert, or delete operations. Therefore, these operations should not
be used during a walk on a dictionary using either or .
Objects in a dictionary or a viewpath can be walked using a loop as
below. Note that only one loop can be used at a time per dictionary.
Concurrent or nested loops may result in unexpected behaviors.
Void_t* dtlast(Dt_t* dt)
Void_t* dtprev(Dt_t* dt, Void_t* obj)
and are like and 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_t* dtfinger(Dt_t* dt)
This function returns the current object of , if any. The current
object is defined after a successful call to one of , , , , , , or .
As a side effect of this implementation of Cdt, when a dictionary is
based on and , the current object is always defined and is the root of
the tree.
Void_t* dtrenew(Dt_t* dt, Void_t* obj)
This function repositions and perhaps rehashes an object after its key
has been changed. only works if is the current object (see ).
dtwalk(Dt_t* dt, int (*userf)(Dt_t*, Void_t*, Void_t*), Void_t* data)
This function calls on each object in and other dictionaries viewable
from it. is the dictionary containing . If returns a value,
terminates and returns the same value. returns on completion.
Dtlink_t* dtflatten(Dt_t* dt)
Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link)
Void_t* dtobj(Dt_t* dt, Dtlink_t* link)
Using or to walk a single dictionary can incur significant cost due to
function calls. For efficient walking of a single directory (i.e., no
viewpathing), and can be used. Objects in are made into a linked
list and walked as follows:
Note that returns a list of type , not . That is, it returns a
dictionary holder pointer, not a user object pointer (although both are
the same if the discipline field is non-negative.) The macro function
returns the dictionary holder object following . The macro function
returns the user object associated with , Beware that the flattened
object list is unflattened on any dictionary operations other than .
Dtlink_t* dtextract(Dt_t* dt)
int dtrestore(Dt_t* dt, Dtlink_t* link)
extracts all objects from and makes it appear empty. repopulates
with objects previously obtained via . will fail if is not empty.
These functions can be used to share a same handle among many sets of
objects. They are useful to reduce dictionary overhead in an
application that creates concurrently many dictionaries. It is
important that the same discipline and method are in use at both
extraction and restoration. Otherwise, undefined behaviors may result.
DICTIONARY INFORMATION
Dt_t* dtvnext(Dt_t* dt)
This returns the dictionary that is viewing, if any.
int dtvcount(Dt_t* dt)
This returns the number of dictionaries that view .
Dt_t* dtvhere(Dt_t* dt)
This returns the dictionary viewable from 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 .
int dtstat(Dt_t *dt, Dtstat_t* st, int all)
This function reports dictionary statistics. If is non-zero, all
fields of are filled. Otherwise, only the and fields are filled.
It returns on success and on error.
contains the below fields:
: This is one of , , , , , , and .
: This contains the number of objects in the dictionary.
: For and , this is the number of non-empty chains in the hash
table. For and , 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. and the below two fields
are undefined for other methods.
: For and , this is the size of a largest chain. For and , this
is the size of a largest level.
: For and , this is the list of counts for chains of particular
sizes. For example, is the number of chains of size . For
and , this is the list of sizes of the levels. For example, is
the size of level .
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. computes a
new hash value from byte and seed value . computes a new hash value
from string and seed value . If is positive, is a byte array of
length ; otherwise, is a null-terminated string.
IMPLEMENTATION NOTES
and are based on hash tables with move-to-front collision chains.
and are based on top-down splay trees. , and are based on doubly
linked list.
AUTHOR
Kiem-Phong Vo, kpv@research.att.com
LIBCDT(3)