### Initialize, Set, and Get Values in Table API

Source: https://context7.com/fanf2/qp/llms.txt

Demonstrates how to initialize an empty table, insert key-value pairs, and retrieve values by their keys using the Tset, Tget, and Tgetkv functions. Handles basic value insertion and retrieval.

```c
#include "Tbl.h"

// Initialize empty table
Tbl *tbl = NULL;

// Insert key-value pairs
void *value = malloc(sizeof(int));
*(int*)value = 42;
tbl = Tset(tbl, "example_key", value);

// Retrieve value by key
void *result = Tget(tbl, "example_key");
if (result != NULL) {
    printf("Found: %d\n", *(int*)result);
}

// Check if key exists and get both key and value
const char *rkey;
void *rval;
if (Tgetkv(tbl, "example_key", strlen("example_key"), &rkey, &rval)) {
    printf("Key: %s, Value: %d\n", rkey, *(int*)rval);
}
```

--------------------------------

### Benchmark Example for QP Tries

Source: https://context7.com/fanf2/qp/llms.txt

Provides instructions for compiling and running the benchmark tool for QP tries. It outlines the parameters for the benchmark command and explains the different operations measured: load, search, mutate, and free. It also mentions a script for comparative benchmarks.

```c
// Compile: make bench-fn
// Run: ./bench-fn "random_seed_12345" 1000000 /usr/share/dict/words

// Output timing for:
// - load: bulk insertion of all keys
// - search: random successful lookups
// - mutate: random insert/delete mix
// - free: delete all entries

// Example output:
// - got 102305 lines
// load... 0.045123 s
// search... 0.234567 s
// mutate... 0.456789 s
// free... 0.023456 s

// Use bench-cross.pl for comparative benchmarks:
// ./bench-cross.pl 1000000 bench-* -- in-*
// Generates HTML table comparing all implementations

```

--------------------------------

### DNS-trie Bitmap Lookup Example (Pseudocode)

Source: https://github.com/fanf2/qp/blob/master/blog-2020-07-05.md

This pseudocode demonstrates how to check a bitmap for a domain name label within a DNS-trie. It uses a 2D offset to access the label and character, then translates this into a bit index for the bitmap lookup. This method involves multiple array lookups, which can be a performance bottleneck.

```pseudocode
node->bmp & 1 << bmpbit[labels[node->label][node->chr]]
```

--------------------------------

### Stringified DNS-trie Bitmap Lookup Example (Pseudocode)

Source: https://github.com/fanf2/qp/blob/master/blog-2020-07-05.md

This pseudocode illustrates a simplified bitmap lookup for a stringified domain name in a DNS-trie. Instead of a 2D offset, it uses a single offset into the key and directly accesses the `bmpbit` table. This approach reduces complexity in the tree walk but requires more upfront processing of the domain name.

```pseudocode
node->bmp & 1 << bmpbit[key[node->offset]]
```

--------------------------------

### Access Internal Structure of 4-bit QP Trie

Source: https://context7.com/fanf2/qp/llms.txt

Provides an example of accessing the internal structure of a 4-bit QP trie, useful for debugging and analysis. It shows how to check if a node is a branch node and how to traverse to a specific child node using internal helper functions like twigbit, hastwig, twigoff, and twig.

```c
#include "qp.h"

// Access internal structure (for debugging/analysis)
static inline bool
is_branch_node(Trie *t) {
    return isbranch(t);
}

// Branch nodes contain:
// - flags (2 bits): 0=leaf, 1=upper nibble, 2=lower nibble
// - index (46 bits): byte position in key
// - bitmap (16 bits): which children exist
// - twigs pointer: array of child nodes

// Example: traverse to specific child
Trie *node = &trie->root;
if (isbranch(node)) {
    const char *search_key = "test";
    Tbitmap bit = twigbit(node, search_key, strlen(search_key));

    if (hastwig(node, bit)) {
        uint offset = twigoff(node, bit);
        Trie *child = twig(node, offset);
        // Process child node...
    }
}

```

--------------------------------

### Test Harness Usage for QP Tries

Source: https://context7.com/fanf2/qp/llms.txt

Demonstrates how to compile and run the test harness for QP tries. It explains the input format for adding and deleting keys, checking for existence, and the expected output format including lexicographical order and statistics. The test harness takes input from a file.

```c
// Compile: make test-qp
// Run: ./test-qp < test_input.txt

// Input format: each line starts with + (add) or - (delete)
// followed by the key string

// Example test_input.txt:
// +apple
// +banana
// +application
// *app         # Check if exists (* -> found, = -> not found)
// -banana
// +cherry

// Output: keys in lexicographic order, then statistics:
// SIZE qp leaves=3 branches=2 overhead=1.33 depth=5.67

```

--------------------------------

### Insert and Lookup Domain Names in DNS Trie

Source: https://context7.com/fanf2/qp/llms.txt

Demonstrates inserting domain names into a DNS-optimized trie and performing efficient lookups. The trie is optimized for hostname characters and uses byte-at-a-time indexing. Requires 'dns.h'.

```c
#include "dns.h"

// Optimized for hostname characters: [a-z0-9-_.]
// Uses byte-at-a-time indexing for common characters
// Falls back to 3+5 bit split for unusual characters

Tbl *dns_trie = NULL;

// Insert domain names
const char *domains[] = {
    "example.com",
    "www.example.com",
    "mail.example.com",
    "example.org",
    "test.example.com"
};

for (int i = 0; i < 5; i++) {
    dns_trie = Tset(dns_trie, domains[i], (void*)(long)i);
}

// Efficient lookup for domain names
void *result = Tget(dns_trie, "www.example.com");
if (result) {
    printf("Domain ID: %ld\n", (long)result);
}

// Iterate over all domains in lexicographic order
const char *domain = NULL;
void *id;
while (Tnext(dns_trie, &domain, &id)) {
    printf("%s -> ID %ld\n", domain, (long)id);
}
```

--------------------------------

### Iterate Over Keys in Table API

Source: https://context7.com/fanf2/qp/llms.txt

Illustrates how to iterate through all key-value pairs in a table in lexicographical order using Tnext and Tnextl. Also shows how to find the next key after a given key using Tnxt. Supports iterating with and without explicit key length tracking.

```c
#include "Tbl.h"

// Iterate in lexicographic order
const char *key = NULL;
void *val = NULL;

while (Tnext(tbl, &key, &val)) {
    printf("%s -> %p\n", key, val);
}

// Alternative: iterate with explicit length tracking
const char *key2 = NULL;
size_t klen = 0;
void *val2 = NULL;

while (Tnextl(tbl, &key2, &klen, &val2)) {
    printf("%.*s (%zu bytes) -> %p\n", (int)klen, key2, klen, val2);
}

// Simple next key lookup
const char *current = "start_key";
const char *next = Tnxt(tbl, current);
if (next != NULL) {
    printf("After '%s' comes '%s'\n", current, next);
}
```

--------------------------------

### Memory and Performance Analysis using Tbl API

Source: https://context7.com/fanf2/qp/llms.txt

Shows how to use the Tbl API to retrieve detailed statistics about a trie, including size, depth, branches, and leaves. It demonstrates calculating overhead metrics and average depth, and provides expected results for different QP variants.

```c
#include "Tbl.h"

// Get detailed statistics
size_t size, depth, branches, leaves;
const char *type;
Tsize(trie, &type, &size, &depth, &branches, &leaves);

// Calculate metrics
size_t overhead_words = size / sizeof(void*) - 2 * leaves;
double overhead_per_leaf = (double)overhead_words / leaves;
double avg_depth = (double)depth / leaves;

printf("Implementation: %s\n", type);
printf("Leaves: %zu\n", leaves);
printf("Branches: %zu\n", branches);
printf("Overhead: %.2f words per entry\n", overhead_per_leaf);
printf("Average depth: %.2f levels\n", avg_depth);

// Expected results for QP variants on typical data:
// - qp (4-bit): ~1.3 words overhead, ~10 depth
// - fn (5-bit): ~1.2 words overhead, ~8 depth
// - dns: ~1.1 words overhead, ~3 depth (for domains)
// - cb (crit-bit): ~2.0 words overhead, ~20 depth

```

--------------------------------

### Build and Search FN Trie with Word List

Source: https://context7.com/fanf2/qp/llms.txt

Builds a trie using the FN variant from a word list and performs prefix searches. The FN variant uses 5 bits (quintets) at a time for efficiency and portability. It requires the 'fn.h' header.

```c
#include "fn.h"

// FN uses 5 bits (quintets) at a time - faster and more portable
// This is the RECOMMENDED implementation

Tbl *fn_trie = NULL;

// Build trie from word list
FILE *fp = fopen("/usr/share/dict/words", "r");
char *line = NULL;
size_t len = 0;

while (getline(&line, &len, fp) != -1) {
    // Remove newline
    size_t klen = strlen(line);
    if (line[klen-1] == '\n') {
        line[klen-1] = '\0';
        klen--;
    }

    // Insert with explicit length
    fn_trie = Tsetl(fn_trie, line, klen, line);
    line = NULL;  // getline will allocate new buffer
    len = 0;
}
fclose(fp);

// Perform prefix search by iteration
const char *prefix = "comp";
const char *key = prefix;
void *val;

printf("Words starting with '%s':\n", prefix);
while (Tnext(fn_trie, &key, &val)) {
    if (strncmp(key, prefix, strlen(prefix)) != 0) {
        break;  // Past our prefix
    }
    printf("  %s\n", key);
}
```

--------------------------------

### FN Trie Index Word Structure and Manipulation

Source: https://context7.com/fanf2/qp/llms.txt

Explains the structure of the FN trie's index word (64 bits) and demonstrates manual manipulation for creating and extracting components. It details the use of shift, offset, and bitmap for managing child nodes. Requires 'fn.h'.

```c
#include "fn.h"

// FN uses a cleaner index word layout than older variants
// Index word (64 bits) contains:
// - branch flag (1 bit)
// - shift (3 bits): position within byte (0-7)
// - offset (28 bits): byte position in key
// - bitmap (32 bits): which of 32 children exist

// Maximum key length
#define MAX_KEY_LENGTH Tmaxlen  // 2^28 - 1 bytes

// Example: manual index word manipulation
Tindex idx = Tindex_new(
    5,           // shift: bits 5-9 within two-byte window
    100,         // offset: byte 100 in the key
    0x12345678   // bitmap: which quintets have children
);

// Extract components
uint shift = Tindex_shift(idx);    // Returns 5
uint offset = Tindex_offset(idx);  // Returns 100
Tbitmap bmp = Tindex_bitmap(idx);  // Returns 0x12345678

// Check specific child exists
byte quintet = 15;  // 0-31
Tbitmap bit = 1U << quintet;
if (hastwig(idx, bit)) {
    uint child_pos = twigoff(idx, bit);
    printf("Child for quintet %d at position %u\n", quintet, child_pos);
}
```

--------------------------------

### Insert, Delete, and Retrieve Key-Value Pairs in Table API

Source: https://context7.com/fanf2/qp/llms.txt

Covers advanced insert and delete operations in the Table API, including inserting with explicit key length for binary keys, handling potential errors like non-word-aligned values or allocation failures, and deleting keys while retrieving the removed data. Supports deletion by setting value to NULL or using Tdelkv.

```c
#include "Tbl.h"
#include <errno.h>

// Insert with explicit length (supports binary keys)
const char *key = "my_key";
void *value = (void*)0x1234;  // Must be word-aligned
tbl = Tsetl(tbl, key, strlen(key), value);
if (tbl == NULL && errno != 0) {
    if (errno == EINVAL) {
        fprintf(stderr, "Value pointer not word-aligned\n");
    } else if (errno == ENOMEM) {
        fprintf(stderr, "Allocation failed\n");
    }
}

// Delete by setting value to NULL
tbl = Tset(tbl, "my_key", NULL);

// Delete and retrieve removed key/value
const char *removed_key;
void *removed_val;
tbl = Tdelkv(tbl, "my_key", strlen("my_key"), &removed_key, &removed_val);
if (removed_key != NULL) {
    printf("Removed: %s -> %p\n", removed_key, removed_val);
    free((void*)removed_key);
}

// When last key deleted, returns NULL without errno
if (tbl == NULL && errno == 0) {
    printf("Table is empty\n");
}
```

--------------------------------

### DNS Trie Bitmap Layout and Character Handling

Source: https://context7.com/fanf2/qp/llms.txt

Describes the 47-bit bitmap layout used in the DNS trie for hostname characters and its fallback mechanism for unusual characters. It also outlines the internal 'Node' structure and index word layout. Requires 'dns.h'.

```c
#include "dns.h"

// 47-bit bitmap for hostname characters:
// - Digits 0-9 (10 bits)
// - Letters a-z (26 bits, case-insensitive in real use)
// - Hyphen, underscore, dot (3 bits)
// - 8 block bits for non-hostname character ranges

// For unusual characters, uses two nodes:
// - Upper 3 bits select block (8 possibilities)
// - Lower 5 bits index within 32-entry block (32-bit bitmap)

// Internal structure (for reference)
typedef struct Node {
    void *ptr;     // Pointer to twigs array or leaf key
    word index;    // Flags, bitmap, and offset combined
} Node;

// Index word layout:
// - COW marker (1 bit)
// - Branch tag (1 bit)
// - Bitmap (47 bits): NOBYTE + character classes + blocks
// - Offset (9 bits): byte position (max 512 for split keys)

// Example: check if character is split across two nodes
byte ch = '@';  // Unusual character
Shift bit = /* ... calculate from character ... */;
if (byte_is_split(bit)) {
    // Will use two-node representation
}
```

--------------------------------

### Create and Search 4-bit QP Trie

Source: https://context7.com/fanf2/qp/llms.txt

Demonstrates the creation and searching of a 4-bit QP trie. This trie implementation uses 4 bits (nibbles) per branch node and 16-bit bitmaps with popcount compression for efficient storage and lookup. It shows inserting multiple string keys and retrieving them.

```c
#include "qp.h"

// The qp trie uses 4 bits (nibbles) at a time
// Branch nodes use 16-bit bitmaps with popcount compression

Tbl *trie = NULL;

// Insert multiple entries
char *keys[] = {"apple", "application", "apply", "banana", "band"};
for (int i = 0; i < 5; i++) {
    void *val = keys[i];  // Using key as value for simplicity
    trie = Tset(trie, keys[i], val);
}

// Search for keys
void *found = Tget(trie, "apple");
if (found) {
    printf("Found: %s\n", (char*)found);
}

// The trie automatically handles prefix compression
// Keys sharing prefixes are stored efficiently in the tree structure

```

--------------------------------

### QP Trie Traversal Loop (C)

Source: https://github.com/fanf2/qp/blob/master/notes-dns.md

A simplified C traversal loop for a qp-trie. It uses bit manipulation and prefetching to navigate the trie. The 'marked line' indicates where eager byte-to-bit conversion would simplify the logic by directly providing the bit index.

```C
while(t->isbranch) {
            __builtin_prefetch(t->twigs);
            b = 1 << key[t->offset]; // <-- marked line
            if((t->bitmap & b) == 0) return(NULL);
            t = t->twigs + popcount(t->bitmap & b-1);
        }
```

--------------------------------

### DNS-trie Node Bitmap Check

Source: https://github.com/fanf2/qp/blob/master/blog-2020-07-05.md

Demonstrates how to check a node's bitmap against a key. This operation is fundamental to traversing the trie and locating specific entries based on bitwise comparisons.

```c
node->bmp & 1 << key[node->offset]
```

--------------------------------

### Standard Crit-Bit Trie Implementation and API Usage

Source: https://context7.com/fanf2/qp/llms.txt

Showcases the standard Crit-Bit trie implementation as a baseline for comparison. It follows the same API as other trie variants for insertion and retrieval, with a note on its performance characteristics and memory overhead. Requires 'cb.h'.

```c
#include "cb.h"

// Traditional binary trie for comparison
// Tests one bit at a time, 2 words overhead per entry

Tbl *cb_trie = NULL;

// Same API as other implementations
cb_trie = Tset(cb_trie, "key1", (void*)1);
cb_trie = Tset(cb_trie, "key2", (void*)2);
cb_trie = Tset(cb_trie, "key3", (void*)3);

void *val = Tget(cb_trie, "key2");

// Crit-bit structure:
// - Branch nodes: bit index + pointer to pair of children
// - Leaf nodes: key pointer + value pointer
// - Children allocated as pairs ("twigs")

// Performance characteristics:
// - Depth: ~8x bytes in key (tests 1 bit per level)
// - Memory: 2 words overhead per entry
// - Speed: Baseline for comparison
```