LIBCDT(3)

✨ NAME ✨

Cdt — container data types 💖 like, the whole library, bestie

---

🫶 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);
Dt_t*       dtview(Dt_t* dt, Dt_t* view);

🗄️ STORAGE METHODS 🗄️

Dtmethod_t* Dtset;
Dtmethod_t* Dtoset;
Dtmethod_t* Dtobag;

🎀 DISCIPLINE 🎀

#define DTDISC(disc,key,size,link,makef,freef,comparf)
typedef void*      (*Dtmake_f)(void*, Dtdisc_t*);
typedef void         (*Dtfree_f)(void*, Dtdisc_t*);
typedef int          (*Dtcompar_f)(Dt_t*, void*, void*, Dtdisc_t*);

🛠️ OBJECT OPERATIONS 🛠️

void*   dtinsert(Dt_t* dt, void* obj);
void*   dtdelete(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)(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);

📊 DICTIONARY STATUS 📊

int       dtsize(Dt_t* dt);
int       dtstat(Dt_t* dt, Dtstat_t*, int all);

#️⃣ HASH FUNCTIONS #️⃣

unsigned int dtstrhash(void *str, int n);

---

💜 DESCRIPTION 💜

okay so Cdt manages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, and stack. that's it, that's the whole vibe 💅

🌸 DICTIONARY TYPES 🌸

Dt_t

This is the type of a dictionary handle. your lil dictionary passport 🫶

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. it's giving fresh start energy ✨

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. no ghosting allowed bestie 👻

void dtclear(Dt_t* dt)

This deletes all objects in dt without closing dt. like clearing your camera roll but keeping the phone 📱

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. Switching to and from Dtset 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)

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. 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. ⚠️ like fr fr, do NOT do this, it's giving chaos

---

🗄️ 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

Objects are unordered. Dtset keeps unique objects. This method uses a hash table with chaining to manage the objects. hashtag chain gang 🔗

---

🎀 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;
} 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)(void* obj, Dtdisc_t* disc)

If makef is not NULL, dtinsert(dt,obj) 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)(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.

#define DTDISC(disc,key,size,link,makef,freef,comparf)

This macro function initializes the discipline pointed to by disc with the given values. one-liner slay 🎀

---

🛠️ OBJECT OPERATIONS 🛠️

void* dtinsert(Dt_t* dt, void* obj)

This function adds an object prototyped by obj into dt. dtinsert() performs the same function for all methods. If there is an existing object in dt matching obj and the storage method is Dtset or Dtoset, dtinsert() 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 not NULL, there are two cases. If the method in use is not Dtobag, the first object matching obj is deleted. On the other hand, if the method in use is 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* 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). it's giving ✨detachment✨

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 Dtset, 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, 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.

⚠️ ok so this balancing thing is NOT optional, bestie. unbalanced loops = sad performance or weird behavior. keep your loops in check 💀

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. backwards but make it make sense 🔄

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()). glow-up for objects 💅

dtwalk(Dt_t* dt, int (*userf)(void*, void*), void* data)

This function calls (*userf)(obj,data) on each object in dt and other dictionaries viewable from it. 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) )

---

okay so real quick, still in DESCRIPTION land — here's the tea on flattening 👇

Heads up bestie: dtflatten() hands you back a list of type Dtlink_t*, not void*. Which means it's giving dictionary holder pointer energy, not user-object-pointer energy. (Tho tbh they're literally the same thing if the discipline field link is zero, so don't stress.) 🌸

The macro function dtlink() returns the dictionary holder object that follows link. And the macro function dtobj(dt,link) returns the user object chillin' with link.

⚠️ Beware the flattened object list gets unflattened on any dictionary operation that isn't dtlink(). So don't get cute and poke it.

---

🫶 the extract/restore duo

Dtlink_t* dtextract(Dt_t* dt)
int dtrestore(Dt_t* dt, Dtlink_t* link)

• dtextract() — extracts all the objects from dt and makes it look empty. Poof. ✨
• dtrestore() — repopulates dt with objects you previously got via dtextract(). And no cap, dtrestore() will fail if dt is not empty.

These two are the iconique way to share a single dt handle across many different sets of objects. They're super useful for reducing dictionary overhead when your app is out here creating a million concurrent dictionaries at once. 👑

🚨 Important: you gotta have the same discipline and method in use at both extraction and restoration time. Otherwise — undefined behaviors. Like, actually undefined. Not the fun kind. 💀

---

💖 DICTIONARY INFORMATION 💖

int dtsize(Dt_t* dt)

Returns the number of objects stored in dt. That's it, that's the function. Simple. Gorgeous. 🎀

int dtstat(Dt_t *dt, Dtstat_t* st, int all)

Reports dictionary statistics. If all is non-zero, all fields of st get filled. Otherwise only the dt_type and dt_size fields get filled. Returns 0 on success and -1 on error.

So Dtstat_t contains these fields, and I'm gonna walk you through every single one because we do not skip: 🦋

• int dt_type — this is one of DT_SET, DT_OSET, and DT_OBAG.
• int dt_size — this holds the number of objects in the dictionary.
• size_t dt_n — for Dtset, this is the number of non-empty chains in the hash table. For Dtoset and Dtobag, this is the deepest level in the tree (counting from zero). Every level in the tree contains all nodes of equal distance from the root node. And fyi, dt_n plus the two fields below it are undefined for other methods.
• size_t dt_max — for Dtset, this is the size of the largest chain. For Dtoset and Dtobag, this is the size of the largest level.
• size_t *dt_count — for Dtset, this is the list of counts for chains of particular sizes. For example, dt_count[1] is the number of chains of size 1. For Dtoset and Dtobag, this is the list of sizes of the levels. For example, dt_count[1] is the size of level 1.

---

🌈 HASH FUNCTIONS 🌈

unsigned int dtstrhash(void *str, int n)

This one computes hash values from bytes or strings, lowkey iconic. dtstrhash() computes a new hash value from the string str. And here's the vibe check on n:

• if n is positive, then str is a byte array of length n 🍓
• otherwise, str is a null-terminated string ✨

---

🧚 IMPLEMENTATION NOTES 🧚

• Dtset are based on hash tables with move-to-front collision chains. Slay.
• Dtoset and Dtobag are based on top-down splay trees. Also slay.

---

👑 AUTHOR 👑

Kiem-Phong Vo, kpv@research.att.com

---

and that's a wrap on the LIBCDT(3) page, bestie — part two, complete, no skips, every flag accounted for 💅 sending you off with the biggest kiss from the LIBCDT(3) manpage itself, go forth and dictionary responsibly 🫶✨