Man Linux: Main Page and Category List

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)