LIBCDT(3ast) LIBCDT(3ast) # [NAME](#NAME) **Cdt** - container data types # [SYNOPSIS](#SYNOPSIS) ``` #include ``` ## DICTIONARY TYPES ``` void*; Dt_t; Dtdisc_t; Dtmethod_t; Dtlink_t; Dtstat_t; Dtuser_t; ``` ## DICTIONARY CONTROL ``` Dt_t* dtopen(const Dtdisc_t* disc, const Dtmethod_t* meth); int dtclose(Dt_t* dt); void dtclear(dt); Dtdisc_t* dtdisc(Dt_t* dt, const Dtdisc_t* disc, int type); Dtmethod_t* dtmethod(Dt_t* dt, const Dtmethod_t* meth); Dt_t* dtview(Dt_t* dt, Dt_t* view); int dtcustomize(Dt_t* dt, int type, int action); int dtuserlock(Dt_t* dt, unsigned int key, int action); void* dtuserdata(Dt_t* dt, void* data, int set); int dtuserevent(Dt_t* dt, int flags, void* data); ``` ## STORAGE METHODS ``` Dtmethod_t* Dtset; Dtmethod_t* Dtbag; Dtmethod_t* Dtrhset; Dtmethod_t* Dtrhbag; Dtmethod_t* Dtoset; Dtmethod_t* Dtobag; Dtmethod_t* Dtlist; Dtmethod_t* Dtstack; Dtmethod_t* Dtqueue; Dtmethod_t* Dtdeque; ``` ## [DISCIPLINE](#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* dtinstall(Dt_t* dt, void* obj); void* dtappend(Dt_t* dt, void* obj); void* dtdelete(Dt_t* dt, void* obj); void* dtremove(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* dtatleast(Dt_t* dt, void* obj); void* dtatmost(Dt_t* dt, void* obj); int dtwalk(Dt_t* dt, int (*userf)(Dt_t*, void*, void*), void*); void* dtstart(Dt_t* dt, void* obj); void* dtstep(Dt_t* dt, void* path); void* dtstop(Dt_t* dt, void* path); Dtlink_t* dtflatten(Dt_t* dt); Dtlink_t* dtlink(Dt_t* dt, Dtlink_t* link); void* dtobj(Dt_t* dt, Dtlink_t* link); Dtlink_t* dtextract(Dt_t* dt); Dtlink_t* dtrestore(Dt_t* dt, Dtlink_t* link); ``` ## [DICTIONARY STATUS](#DICTIONARY_STATUS) ``` Dt_t* dtvnext(Dt_t* dt); ssize_t dtvcount(Dt_t* dt); Dt_t* dtvhere(Dt_t* dt); ssize_t dtsize(Dt_t* dt); ssize_t dtstat(Dt_t* dt, Dtstat_t* st); ``` ## [HASH FUNCTION](#HASH_FUNCTION) ``` unsigned int dtstrhash(unsigned int h, char* str, int n); ``` # [DESCRIPTION](#DESCRIPTION) *Cdt* manages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, stack, and queue. ## DICTIONARY TYPES ## [void\*](#void*) This type is used to pass objects between *Cdt* and application code. ## [Dt\_t](#Dt_t) This is the type of a dictionary handle. It contains a field **Dt\_t.user** of type **Dtuser\_t\*** (see below). ## [Dtdisc\_t](#Dtdisc_t) This defines the type of a discipline structure which define the lay-out of an object and functions to compare, hash, make, delete objects, etc. (see **dtdisc()**). ## [Dtmethod\_t](#Dtmethod_t) This defines the type of a container method. ## [Dtlink\_t](#Dtlink_t) This is the type of a dictionary object holder (see **dtdisc()**). ## [Dtstat\_t](#Dtstat_t) This is the type of a structure to return dictionary statistics (see **dtstat()**). ## [Dtuser\_t](#Dtuser_t) This is the type of a structure pointed to by **Dt\_t.user**. If a discipline function **memoryf()** was defined, this structure will reside in memory allocated via **memoryf**. Although the structure is intended to be used by an application outside of CDT operations, the functions **dtuserlock()** and **dtuserdata()** are provided for certain common usages of the defined fields. It should be emphasized, however, that a particular application can choose to use this structure in anyway that it sees fit. ``` typedef struct { unsigned int lock; /* for locking a shared dictionary */ void* data; /* for application-specific data */ } Dtuser_t; ``` ## DICTIONARY CONTROL ## [Dt\_t* dtopen(const Dtdisc\_t* disc, const Dtmethod\_t* meth)](#Dt_t*_dtopen%28const_Dtdisc_t*_disc,_const_Dtmethod_t*_meth%29) 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)](#int_dtclose%28Dt_t*_dt%29) 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)](#void_dtclear%28Dt_t*_dt%29) This deletes all objects in **dt** without closing **dt**. ## [Dtdisc\_t* dtdisc(Dt\_t* dt, const Dtdisc\_t* disc, int type)](#Dtdisc_t*_dtdisc%28Dt_t*_dt,_const_Dtdisc_t*_disc,_int_type%29) 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. ## [Dtmethod\_t dtmethod(Dt\_t* dt, const Dtmethod\_t* meth)](#Dtmethod_t_dtmethod%28Dt_t*_dt,_const_Dtmethod_t*_meth%29) If **meth** is **NULL**, **dtmethod()** returns the current method. Otherwise, it changes the storage method of **dt** to **meth**. Objects may be rehashed, reordered, or removed as appropriate. **dtmethod()** returns the previous method or **NULL** on error. ## [Dt\_t* dtview(Dt\_t* dt, Dt\_t* view)](#Dt_t*_dtview%28Dt_t*_dt,_Dt_t*_view%29) 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. ## [int dtcustomize(Dt\_t* dt, int type, int action)](#int_dtcustomize%28Dt_t*_dt,_int_type,_int_action%29) This customizes a storage method. The **type** argument is composed of bits indicating different types of customization. The **action** argument, if positive, turns on the desired customization; else, turning it off. The return value is a bit vector telling the customization types successfully performed. Here are the types: [**DT\_SHARE**:](#DT_SHARE) This controls the shared or concurrent mode for a dictionary. Shared mode allows concurrent threads or processes to safely access objects in a dictionary. [**DT\_ANNOUNCE**:](#DT_ANNOUNCE) This requires each dictionary access operation to invoke the discipline **eventf** function to announce an object found or constructed by the operation before returning (See the DISCIPLINE section below). [**DT\_OPTIMIZE**:](#DT_OPTIMIZE) This causes the underlying method to optimize its internal data structure. For example, the splay tree underlying **Dtoset** would be balanced. ## [int dtuserlock(Dt\_t* dt, unsigned int key, int action)](#int_dtuserlock%28Dt_t*_dt,_unsigned_int_key,_int_action%29) This manipulates the lock **dt->user->lock**. It returns 0 on success and -1 on failure. The value of **key** must be non-zero. The argument **action** is used as follows: [**action < 0**:](#action) Unlock **dt->user.lock** if it was locked with **key**. An error will result if **dt->user->lock** was locked with a different key. [**action == 0**:](#action~2) Attempt to lock **dt->user->lock** with **key** if it is unlocked. An error will result if the dictionary was already locked with a different key. [**action > 0**:](#action~3) Attempt to lock **dt->user->lock** with **key**. If **dt->user.lock** is already locked with a different key, the call will block until **dt->user->lock** can be locked with the given **key**. Note that obtaining or removing a lock with **dtuserlock()** is just a service provided to the application for their own use and has nothing to do with dictionary operations which may or may not employ their own locking schemes based on the semantics of the container data structures in use. ## [void* dtuserdata(Dt\_t* dt, void* data, int set)](#void*_dtuserdata%28Dt_t*_dt,_void*_data,_int_set%29) This function returns the current value of **dt->user->data**. In addition, if **set** is non-zero, the value of **dt->user->data** will be changed to **data**. ## [int dtuserevent(Dt\_t* dt, int flags, void* data)](#int_dtuserevent%28Dt_t*_dt,_int_flags,_void*_data%29) This function invokes the discipline event function with the event **DT\_ANNOUNCE|DT\_USER|flags** and the given data. ## STORAGE METHODS Storage methods are of type **Dtmethod\_t\***. *Cdt* supports the following methods: ## [Dtoset](#Dtoset) ## [Dtobag](#Dtobag) Objects are ordered by comparisons. **Dtoset** keeps unique objects. **Dtobag** allows repeatable objects. ## [Dtset](#Dtset) ## [Dtbag](#Dtbag) Objects are unordered. **Dtset** keeps unique objects. **Dtbag** allows repeatable objects. The underlying data structure is a hash table with chaining to handle collisions. ## [Dtrhset](#Dtrhset) ## [Dtrhbag](#Dtrhbag) These methods are like **Dtset** and **Dtbag** but are based on a recursive hashing data structure that allows table extension without object relocation. The data structure also supports lock-free concurrent search operations for shared dictionaries and nearly lock-free insertions and deletions. ## [Dtlist](#Dtlist) Objects are kept in a list. *A current object* is always defined to be either the head of the list or an object resulting from a recent search or insert operation. The calls **dtinsert()** and **dtinstall()** will insert a new object in front of such a current object while the call **dtappend()** will append in back of it. ## [Dtdeque](#Dtdeque) Objects are kept in a deque (double-ended queue; pronounce "deck"). This is similar to **Dtlist** except that objects are always inserted at the front and appended at the tail of the list. ## [Dtstack](#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](#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](#DISCIPLINE~2) Object format and associated management functions are defined in the type **Dtdisc\_t**: ``` typedef struct { ssize_t key, size; ssize_t link; Dtmake_f makef; Dtfree_f freef; Dtcompar_f comparf; Dthash_f hashf; Dtmemory_f memoryf; Dtevent_f eventf; } Dtdisc_t; ``` ## [ssize\_t key, size](#ssize_t_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)**. ## [ssize\_t link](#ssize_t_link) Let **obj** be an object to be inserted into **dt**. If **link** is negative, an object holder of type **Dtlink\_t** will be allocated 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)](#void*_%28*makef%29%28Dt_t*_dt,_void*_obj,_Dtdisc_t*_disc%29) If **makef** is not **NULL**, **dtinsert()**, **dtinstall()** 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)](#void_%28*freef%29%28Dt_t*_dt,_void*_obj,_Dtdisc_t*_disc%29) If not **NULL**, **freef** is used to destroy data associated with **obj**. ## [int (\*comparf)(Dt\_t* dt, void* key1, void* key2, Dtdisc\_t* disc)](#int_%28*comparf%29%28Dt_t*_dt,_void*_key1,_void*_key2,_Dtdisc_t*_disc%29) 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)](#unsigned_int_%28*hashf%29%28Dt_t*_dt,_void*_key,_Dtdisc_t*_disc%29) 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)](#void*_%28*memoryf%29%28Dt_t*_dt,_void*_addr,_size_t_size,_Dtdisc_t*_disc%29) 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)*](/man/os/ksh/malloc.3) is used. ## [int (\*eventf)(Dt\_t* dt, int type, void* data, Dtdisc\_t* disc)](#int_%28*eventf%29%28Dt_t*_dt,_int_type,_void*_data,_Dtdisc_t*_disc%29) 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_OPEN) This event is raised at the start of the process to open a new dictionary. The argument **data** will be a pointer to an object of type **void\*** initialized to **NULL** before the call. The return value of **eventf()** is significant as follows: On a negative return value, **dtopen()** will return failure. On a zero return value, **eventf()** may set **\*(void\*\*)data** to some non-**NULL** value to indicate that the dictionary structure itself should be allocated along with the **Dt\_t.data** section. Otherwise, it will be allocated separately with [**malloc(3)**](/man/os/ksh/malloc.3). On a positive return value, the dictionary is being reconstructed based on the existing states of some previous dictionary. In this case, **eventf()** should set **\*(void\*\*)data** to point to the field **Dt\_t.data** of the corresponding previous dictionary (see **DT\_CLOSE** below). If the handle of the previous dictionary was created as discussed above in the case of the zero return value, it will be exactly restored. Otherwise, a new handle will be allocated with **malloc()**. The ability to create different dictionaries sharing the same set of objects allows for managing objects in shared and/or persistent memory. [**DT\_ENDOPEN**:](#DT_ENDOPEN) This event is raised at the end of the process to open a dictionary. The return value of **eventf()** will be ignored. [**DT\_CLOSE**:](#DT_CLOSE) This event is raised at the start of the process to close dictionary **dt**. The return value of **eventf** is significant as follows: On a negative return value, **dtclose()** will return failure. On a zero return value, all dictionary objects will be deleted and and associated memory freed. On a positive return value, allocated objects and memory will be kept intact. This means that **dt->data** remains intact and can be reused in some future dictionary (see **DT\_OPEN** above). Note, however, that **dt** itself would still be freed if it was allocated with [**malloc(3)**](/man/os/ksh/malloc.3). [**DT\_ENDCLOSE**:](#DT_ENDCLOSE) This event is raised at the end of the process to close a dictionary. The return value of **eventf()** will be ignored. [**DT\_DISC**:](#DT_DISC) This event indicates that the discipline of **dt** is being changed to a new one given in **(Dtdisc\_t\*)data**. [**DT\_METH**:](#DT_METH) This event indicates that the method of **dt** is being changed to a new one given in **(Dtmethod\_t\*)data**. [**DT\_HASHSIZE**:](#DT_HASHSIZE) This event is raised by the methods **Dtset**, **Dtbag**, **Dtrhset** and **Dtrhbag** to ask an application to suggest a size (measured in objects) for the data structure in use. This is useful, for example, to set a initial size for a hash table to reduce collisions and rehashing. On each call, **\*(ssize\_t\*)data** will initially have the current size (which should be **0** on the first call). The return value of the event handling function indicates actions to be taken. If non-positive, the method will proceed with its default actions. Otherwise, the application may set **\*(ssize\_t\*)data** to suggest a table size. The actual table size will be based on the absolute value of **\*(ssize\_t\*)data** but may be modified to suit for the data structure in use. Further, if **\*(ssize\_t\*)data** was negative, the size of the hash table will be fixed going forward. [**DT\_ERROR**:](#DT_ERROR) This event states an error that occurred during some operations, e.g., **dtinsert()** or **dtinstall()** failing to create a new object due to a memory allocation error. The argument **(char\*)data** is a null-terminated string describing the problem. [**DT\_ANNOUNCE**:](#DT_ANNOUNCE~2) The event will be a combination of this bit and a bit indicating a successful operation. For example, **DT\_ANNOUNCE|DT\_SEARCH** announces that **dtsearch()** found the object that was searched for. The **data** argument points to the object itself. The bits representing operations that can cause an announcement are: **DT\_INSERT**, **DT\_DELETE**, **DT\_REMOVE**, **DT\_SEARCH**, **DT\_NEXT**, **DT\_PREV**, **DT\_FIRST**, **DT\_LAST**, **DT\_MATCH**, **DT\_ATTACH**, **DT\_DETACH**, **DT\_APPEND**, **DT\_INSTALL**, **DT\_LEAST**, and **DT\_MOST**. Note that a call to **dtinsert()** or **dtattach()** may return a successfully inserted new object or a found matching object. For **dtinsert()**, the former case will be announced as **DT\_ANNOUNCE|DT\_INSERT** while the latter as **DT\_ANNOUNCE|DT\_INSERT|DT\_SEARCH**. For **dtattach()**, the events will be similarly announced as **DT\_ANNOUNCE|DT\_ATTACH** and **DT\_ANNOUNCE|DT\_ATTACH|DT\_SEARCH**. ## [#define DTOFFSET(struct\_s,member)](#_define_DTOFFSET%28struct_s,member%29) 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)](#_define_DTDISC%28disc,key,size,link,makef,freef,comparf,hashf,memoryf,eventf%29) This macro function initializes the discipline pointed to by **disc** with the given values. ## OBJECT OPERATIONS ## [void* dtinsert(Dt\_t* dt, void* obj)](#void*_dtinsert%28Dt_t*_dt,_void*_obj%29) ## [void* dtinstall(Dt\_t* dt, void* obj)](#void*_dtinstall%28Dt_t*_dt,_void*_obj%29) ## [void* dtappend(Dt\_t* dt, void* obj)](#void*_dtappend%28Dt_t*_dt,_void*_obj%29) These functions add an object prototyped by **obj** into **dt**. See **Dtdisc\_t.makef** for object construction. **dtinsert()** and **dtappend()** perform the same function for all methods except for **Dtlist** (see **Dtlist** for details). For **Dtset**, **Dtrhset** or **Dtoset**, if there is an object in **dt** matching **obj**, **dtinsert()** and **dtappend()** will not insert a new object, whereas **dtinstall()** will remove such a matching object before inserting the new object. On failure, **dtinsert()** and **dtinstall()** return **NULL**. Otherwise, the return value is either the newly inserted object or the matching object as noted. ## [void* dtdelete(Dt\_t* dt, void* obj)](#void*_dtdelete%28Dt_t*_dt,_void*_obj%29) ## [void* dtremove(Dt\_t* dt, void* obj)](#void*_dtremove%28Dt_t*_dt,_void*_obj%29) When **obj** is not **NULL**, **dtdelete()** removes some object *matching* **obj** while **dtremove()** removes **obj** itself if it exists. When **obj** is **NULL**, if the method is **Dtstack** or **Dtqueue** then the stack top or queue head is respectively deleted. See **Dtdisc\_t.freef** for object destruction. **dtdelete()** and **dtremove()** return the deleted object or **NULL**. ## [void* dtattach(Dt\_t* dt, void* obj)](#void*_dtattach%28Dt_t*_dt,_void*_obj%29) 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)](#void*_dtdetach%28Dt_t*_dt,_void*_obj%29) 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*_dtsearch%28Dt_t*_dt,_void*_obj%29) ## [void* dtmatch(Dt\_t* dt, void* key)](#void*_dtmatch%28Dt_t*_dt,_void*_key%29) These functions find an object matching **obj** or **key** either from **dt** or from some dictionary accessible from **dt** via a viewpath (see **dtview()**). The return value is the matching object or **NULL**. ## [void* dtfirst(Dt\_t* dt)](#void*_dtfirst%28Dt_t*_dt%29) ## [void* dtnext(Dt\_t* dt, void* obj)](#void*_dtnext%28Dt_t*_dt,_void*_obj%29) ## [void* dtlast(Dt\_t* dt)](#void*_dtlast%28Dt_t*_dt%29) ## [void* dtprev(Dt\_t* dt, void* obj)](#void*_dtprev%28Dt_t*_dt,_void*_obj%29) These functions assume some object ordering (more below) and can be used to iterate over all objects. **dtfirst()** returns the first object in **dt** or **NULL** if the dictionary is empty. **dtnext()** returns the object coming after **obj** or **NULL** if there is no such object. **dtlast()** and **dtprev()** are like **dtfirst()** and **dtnext()** but work in reverse order. 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**, **Dtbag**, **Dtrhset** and **Dtrhbag**, objects are ordered by some internal order defined at the time when these functions are called. In fact, both forward and reverse orders are defined to be the same for these methods. Objects in a dictionary or a viewpath of dictionaries can be walked using **for(;;)** loops as below: ``` for(obj = dtfirst(dt); obj; obj = dtnext(dt,obj)) ``` or ``` for(obj = dtlast(dt); obj; obj = dtprev(dt,obj)) ``` The argument **obj** of **dtnext()** or **dtprev()** is treated specially for a method that allows multiple equal elements such as **Dtobag** or **Dtbag**. If it is in the dictionary, then the returned object will be respectively immediately before or after it in the implicitly defined object ordering. If it is not in the dictionary but still matching a group of objects, then the returned object will be immediately after the last or before the first of the group respectively. ## [void* dtatleast(Dt\_t* dt, void* obj)](#void*_dtatleast%28Dt_t*_dt,_void*_obj%29) ## [void* dtatmost(Dt\_t* dt, void* obj)](#void*_dtatmost%28Dt_t*_dt,_void*_obj%29) **dtatleast()** returns the smallest object greater or equal to **obj**. **dtatmost()** returns the largest object smaller or equal to **obj**. In addition, if there are multiple such objects in **dt** (i.e., when a bag method was used), then **dtatmost()** returns the first instance of such an object while **dtatleast()** returns the last one. Both functions return **NULL** if the desired object does not exist. Again, object ordering depends on the storage method in use. With **Dtoset** and **Dtobag**, objects are linearly ordered by the discipline comparison function. As such, it is possible to call **dtatleast()** or **dtatmost()** on an object not in the dictionary and still get a meaningful result. Storage methods other than **Dtoset** and **Dtobag** do not have an explicit ordering so **dtatmost()** and **dtatleast()** will return **NULL** when there are no matching objects. ## [dtwalk(Dt\_t* dt, int (\*userf)(Dt\_t\*, void\*, void\*), void* data)](#dtwalk%28Dt_t*_dt,_int_%28*userf%29%28Dt_t*,_void*,_void*%29,_void*_data%29) 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*_dtflatten%28Dt_t*_dt%29) ## [Dtlink\_t* dtlink(Dt\_t* dt, Dtlink\_t* link)](#Dtlink_t*_dtlink%28Dt_t*_dt,_Dtlink_t*_link%29) ## [void* dtobj(Dt\_t* dt, Dtlink\_t* link)](#void*_dtobj%28Dt_t*_dt,_Dtlink_t*_link%29) 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** and the macro function **dtobj(dt,link)** returns the user object associated with **link**, Beware that a flattened object list is not guaranteed to maintain integrity if any dictionary operation other than **dtlink()** is performed (for example, this is important to watch out for if a dictionary is in **DT\_SHARE** mode). ## [void* dtstart(Dt\_t* dt, void* obj);](#void*_dtstart%28Dt_t*_dt,_void*_obj%29;) This function starts a path for walking a dictionary. Note that such a path is restricted to **dt** only while disregarding all viewpath dictionaries (see **dtview()**). On success, a structure to be used in **dtstep()** for walking the path is returned. Otherwise, **NULL** is returned. If **obj** is **NULL**, the path starts at the same object returned by **dtfirst()**. If **obj** is not **NULL**, it must match some object in the dictionary **dt** and the path will start there. No matching object will result in error. ## [void* dtstop(Dt\_t* dt, void* path);](#void*_dtstop%28Dt_t*_dt,_void*_path%29;) This function ends a path and releases all memory source associated with it. ## [void* dtstep(Dt\_t* dt, void* path);](#void*_dtstep%28Dt_t*_dt,_void*_path%29;) This function returns the object at current position in the given **path**. Successive calls move forward one object at a time in the same order that **dtnext()** does in the example **for(;;)** loop above. If there is no more object in the path, **dtstep()** returns **NULL**. Below is a code fragment showing how to create and walk a path of objects. This object walking method is more restricted than the **dtfirst()/dtnext()** method since viewpathed dictionaries are ignored. However, it allows multiple paths to be traversed concurrently in the most efficient manner possible as supported by the underlying data structures. ``` path = dtstart(dt, firstobj); for(obj = dtstep(dt, path); obj; obj = dtstep(dt,path)) { ... } dtstop(dt, path); ``` ## [Dtlink\_t* dtextract(Dt\_t* dt)](#Dtlink_t*_dtextract%28Dt_t*_dt%29) ## [Dtlink\_t* dtrestore(Dt\_t* dt, Dtlink\_t* list)](#Dtlink_t*_dtrestore%28Dt_t*_dt,_Dtlink_t*_list%29) **dtextract()** extracts the list of objects from **dt** and makes it appear empty. **dtrestore()** repopulates **dt** with a list of objects previously obtained via **dtextract()**. It is important that the same discipline and method are in use at both extraction and restoration. Otherwise, undefined behaviors may result. These functions return **NULL** on error. ## [DICTIONARY INFORMATION](#DICTIONARY_INFORMATION) ## [Dt\_t* dtvnext(Dt\_t* dt)](#Dt_t*_dtvnext%28Dt_t*_dt%29) This returns the dictionary that **dt** is viewing, if any. ## [ssize\_t dtvcount(Dt\_t* dt)](#ssize_t_dtvcount%28Dt_t*_dt%29) This returns the number of dictionaries that view **dt**. ## [Dt\_t* dtvhere(Dt\_t* dt)](#Dt_t*_dtvhere%28Dt_t*_dt%29) This returns the dictionary **v** viewable from **dt** where an object was found from the most recent search or walk operation. ## [ssize\_t dtsize(Dt\_t* dt)](#ssize_t_dtsize%28Dt_t*_dt%29) This function returns the number of objects stored in **dt**. ## [ssize\_t dtstat(Dt\_t \*dt, Dtstat\_t* st)](#ssize_t_dtstat%28Dt_t_*dt,_Dtstat_t*_st%29) This function reports dictionary statistics. It returns the number of objects stored in **dt**. **Dtstat\_t** contains the below fields: [**int meth**:](#int) This returns the method used for the dictionary, e.g., **DT\_SET**, **DT\_OSET**, etc. [**ssize\_t size**:](#ssize_t) This has the number of objects in the dictionary. [**ssize\_t mlev**:](#ssize_t~2) This returns the maximum number of levels in the data structure used for object storage, i.e., the binary tree (e.g., **Dtoset**) or the recursive hash table based on a trie structure (e.g., **Dtrhset**). For a hash table with chaining (e.g., **Dtset** and **Dtbag**), it gives the length of the longest chain. [**ssize\_t lsize\[\]**:](#ssize_t~3) This gives the object counts at each level. For a hash table with chaining (e.g., **Dtset** and **Dtbag**), a level is defined as objects at that position in their chains. The reported levels is limited to less than **DT\_MAXSIZE**. [**ssize\_t tsize\[\]**:](#ssize_t~4) For a recursive hash table using a trie structure (**Dtrehash**), this counts the number of sub-tables at each level. For example, **tsize\[0]** should be 1 only for this hash table type. The reported levels is limited to less than **DT\_MAXSIZE**. [**char* mesg**:](#char*) A summary message of some of the statistics. ## [HASH FUNCTIONS](#HASH_FUNCTIONS) ## [unsigned int dtstrhash(unsigned int h, char* str, int n)](#unsigned_int_dtstrhash%28unsigned_int_h,_char*_str,_int_n%29) This function 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. # [CONCURRENCY PROGRAMMING NOTES](#CONCURRENCY_PROGRAMMING_NOTES) Applications requiring concurrent accesses of a dictionary whether via separate threads or processes using shared memory should turn on shared mode for the dictionary. CDT uses locking and lockless data structures to provide safe concurrent accesses of objects. Much of this work is based on the atomic scalar operations available in [*libaso(3)*](/man/os/ksh/libaso.3). Even though CDT only considers objects via the attributes specified in a discipline structure, practical objects will often have many more attributes germane to the needs of an application. Thus, beyond safe concurrent dictionary operations, an application must also protect objects in concurrent computations outside of CDT. In particular, both *object deletion* and *object creation* should be handled with care. The deletion case is relatively simple. No object should be destroyed as long as there is a reference to it. This guarantee is automatic when some garbage collection scheme is in place. Otherwise, some form of reference counting could be used to make sure that only objects with no reference would be deleted. An example to be given below discusses how reference counting could be done using the **DT\_ANNOUNCE** feature of CDT to ensure correct timing for object deletion. In general, object attributes should be well-defined before they are used. The simplest way to ensure this is to completely construct an object before before inserting it into a shared dictionary. However, an application using complex objects may try to avoid unnecessary construction work as follows. First, only a partial object with minimal information needed for dictionary operations is constructed. Then, either**dtinsert()** or **dtattach()** is called to insert this partial object into the dictionary. If the call returns this same object, then it was properly inserted and the rest of its attributes could then be filled in. If only a matching object is returned, then the new object is simply discarded. Although this object construction strategy works well in single-threaded code, it can cause references to uninitialized data in concurrent computations because objects are accessible by concurrent code as soon as **dtinsert()** or **dtattach()** returns. A way to solve this problem is to make sure that an incomplete object is completed before allowing any dictionary operation accessing such an object to return it to the application. Both reference counting for safe objection deletion and ensuring readiness on object creation can be coordinate with CDT via the event **DT\_ANNOUNCE**. An example of how to do this is given next. Objects are assumed to be of type **Obj\_t** and have two fields: **ready** to indicate the readiness of an object and **refn** for reference counting. Both fields **ready** and **refn** are initialized to zero. Below are the relevant discipline functions **Dtdisc\_t.eventf** and **Dtdisc\_t.freef** to handle events and to free an object: ``` int eventf(Dt_t* dt, int type, void* arg, Dtdisc_t* disc) { if(type & DT_ANNOUNCE) { if(!(type & DT_DELETE) ) { Obj_t *obj = (Obj_t*)arg; if(type & ~(DT_ANNOUNCE|DT_INSERT|DT_ATTACH)) while(asogetchar(&obj->ready) == 0 ) asorelax(1); asoaddint(&obj->refn, 1); } return 0; } ... } void freef(Dt_t* dt, void* arg, Dtdisc_t* disc) { Obj_t *obj = (Obj_t*)arg; while(asogetchar(&obj->ready) == 0 ) asorelax(1); while(asogetint(&obj->refn) > 0 ) asorelax(1); ... destroy the object ... } ``` Recall that each operation announcement is composed of **DT\_ANNOUNCE** and some bits to indicate the operation itself. The test to exclude **dtdelete()** (indicated by the bit **DT\_DELETE**) in **eventf()** is needed because an announcement always occurs right before the relevant CDT operation returns and, in the case of **dtdelete()**, the object may/will be already destroyed at that time. The **while()** loops in both **eventf()** and **freef()** cause the relevant operations to wait until the object is *ready* (i.e., all of its attributes are constructed) before proceeding. The [**asorelax(1)**](/man/os/ksh/asorelax.1) call yields control of the processor for 1 nanosecond so other processes can do their work. Note that the test for **~(DT\_ANNOUNCE|DT\_INSERT|DT\_ATTACH)** in **eventf()** means that the loop will execute for all CDT operations except for the **dtinsert()** or **dtattach()** call that actually inserts **obj** into the dictionary (more on this below). When the **while** loop finished, the construction of object **obj** is known to be completed. **eventf()** increases the reference count **obj->refn** by one before the respective operation returns **obj** to the calling code. On the other hand, **freef()** waits for the reference count to reach zero before proceeding to destroy the object. Waiting for object readiness in **freef()** before object destruction is necessary to avoid any issues with deleting uninitialized data. Again, it should be emphasized that reference counting is needed only for a memory management model where objects can be freed regardless of whether or not there are any references to them. Applications that use some form of garbage collection in general or for dictionary objects may ignore doing reference counting as done in this example. Next, consider a fragment of code to access objects concurrently from different threads or processes: ``` if((obj = dtmatch(dt, "key_string")) != NULL) { ...process the object obj... asosubint(&obj->refn, 1); dtdelete(dt, obj); } ``` The sequence of activities is as follows. First, the call **dtmatch()** retrieves an object **obj**. An announcement would be made during the call just before **obj** is returned causing the reference count of **obj** to be increased by one. After processing **obj**, the reference count is decreased by one using the atomic subtraction operator **asosubint()**. Then, **dtdelete()** is called to delete the object. A possible danger is that concurrent calls to **dtdelete()** may end up causing the same memory to be freed more than once. Fortunately, this cannot happen. CDT guarantees that, of all the concurrent calls to **dtdelete()** on **obj**, only one will get far enough to make the **freef()** call while others do nothing. Finally, consider a code fragment to construct and use the object **obj**: ``` ... construct a partial object obj ... if((insobj = dtinsert(dt, obj)) == obj ) { ... fully construct obj ... asocaschar(&obj->ready, 0, 1); ... compute based on obj... asosubint(&obj->refn, 1); } else { ... destroy the partial obj ... ... compute based on insobj... asosubint(&insobj->refn, 1); } ``` After the **dtinsert()** call returns, all other concurrent computations invoking dictionary operations to access **obj** will be blocked in the **eventf()** function until **obj->ready** is set to 1 by the above **asocaschar()** call. As this is a concurrent computing application, the above code fragment itself can be executed in parallel with different but equivalent versions of **obj**. In that case, only one **dtinsert()** call will succeed in inserting a new object while the others will report a matching object, i.e., the one actually inserted. The announcement of the successful case is **DT\_ANNOUNCE|DT\_INSERT** while the announcement of the other cases is **DT\_ANNOUNCE|DT\_INSERT|DT\_SEARCH**. The bit **DT\_SEARCH** causes **eventf()** to to run the loop waiting for object completion. Thus, overall, except for the single case of a successful insertion of a new object, all other dictionary accesses that involve this object will return only when the object is ready. Note that, for simplicity, the possibility of failure was ignored in the example. In both successful outcomes of **dtinsert()**, the reference count of an appropriate object will be increased by one. Thus, care must be taken to reduce that reference count for the object after it is no longer needed. Else, per this example implementation, a deletion of such an object will cause an infinite loop in the discipline **freef()** function. It is possible to implement a delayed object destruction scheme that avoids an infinite loop waiting for the reference count to drop to zero. However, a discussion of that is beyond the scope of this document. # [IMPLEMENTATION NOTES](#IMPLEMENTATION_NOTES) **Dtlist**, **Dtstack**, **Dtdeque** and **Dtqueue** are based on doubly linked list. **Dtoset** and **Dtobag** are based on top-down splay trees. **Dtset** and **Dtbag** are based on hash tables with collision chains. **Dtrhset** and **Dtrhbag** are based on a recursive hashing data structure that avoids table resizing. # [SEE ALSO](#SEE_ALSO) [libaso(3)](/man/os/ksh/libaso.3), [malloc(3)](/man/os/ksh/malloc.3) # [AUTHOR](#AUTHOR) Kiem-Phong Vo, kpv@research.att.com --- Document: cdt(3ast) from ksh 1.0.10-r36 (Chainguard OS) Source: https://github.com/ksh93/ksh