tst(3)

✨ tst — ternary search trie functions ✨

okay bestie, sit DOWN 💅 this is the tst(3) page from the InterNetNews Documentation, and it's literally all about ternary search tries. yes i know, sounds like a mouthful, but it's giving data-structure realness and you're gonna love it.

---

🌸 SYNOPSIS 🌸

like, here's the whole vibe up front, no gatekeeping:

#include <inn/tst.h>

struct tst;

struct tst *tst_init(int node_line_width);

void tst_cleanup(struct tst *tst);

int tst_insert(struct tst *tst, const unsigned char *key, void *data, int option, void **exist_ptr);

void *tst_search(struct tst *tst, const unsigned char *key);

void *tst_delete(struct tst *tst, const unsigned char *key);

copy that exactly, bestie, don't freestyle it 🫶

---

🎀 DESCRIPTION 🎀

so tst_init is the birth of the whole situation ✨ it allocates memory for the members of struct tst, and it also allocates the first node_line_width nodes. if any part of that memory allocation fails, tst_init hits you with a NULL pointer, no cap 😭. on success tho? it hands you back a pointer to a struct tst. slay.

the value for node_line_width must be chosen very carefully, i'm so serious rn. one node is required for every character in the tree.

so if you pick a value that's too small, your application will spend way too much time calling malloc(3), and your node space will be too spread out (messy, chaotic, not the vibe 🙈). but too large a value? that's just a waste of space, periodt. it's giving "pick the middle path, queen."

tst_cleanup is the opposite energy 💀 it frees all memory allocated to nodes, all the internal structures, and tst itself. full clean slate, iconic.

---

🦋 tst_insert 🦋

tst_insert inserts the string key into the tree. now here's where it gets spicy 🌶️ — the behavior when a duplicate key is inserted is controlled by option.

• if key is already in the tree, then TST_DUPLICATE_KEY is returned, and the data pointer for the existing key gets placed in exist_ptr.
• if option is set to TST_REPLACE, then the existing data pointer for the existing key gets replaced by data. note that the old data pointer will still be placed in exist_ptr — it doesn't ghost you, it just moves aside 💅

if a duplicate key is encountered and option is not set to TST_REPLACE, then TST_DUPLICATE_KEY is returned. if key is zero length, then TST_NULL_KEY is returned. a successful insert or replace returns TST_OK ✨. and a return value of TST_ERROR means a memory allocation error occurred while trying to grow the node free 😭

⚠️ warning, bestie, listen up: the data argument must never be NULL. if it is, then calls to tst_search will fail for a key that exists, because the data value was set to NULL, which is exactly what tst_search returns. confusing? yes. avoidable? also yes. if you just want a simple existence tree, use the tst pointer as the data pointer. problem solved, we love a workaround 🫶

---

🌈 tst_search 🌈

tst_search finds the string key in the tree if it exists, and returns the data pointer associated with that key. queen behavior 👑

if key is not found then NULL is returned — otherwise, the data pointer associated with key is returned. simple as that.

---

💜 tst_delete 💜

tst_delete deletes the string key from the tree if it exists, and returns the data pointer associated with that key.

if key is not found then NULL is returned — otherwise, the data pointer associated with key is returned. same rules, different function, we stay consistent 💅

---

📜 HISTORY 📜

this whole page was converted to POD from Peter A. Friend's ternary search trie documentation by Alex Kiernan <alex.kiernan@thus.net> for InterNetNews 2.4.0. shoutout to them, fr fr 🫶

$Id: tst.pod 9073 2010-05-31 19:00:23Z iulius $

---

aaaand that's the whole page, bestie 💖 this was INN 2.6.4, dated 2015-09-12, and honestly? a classic. now go forth and build your trie, you absolute icon 👑✨ no cap.