Skip to content

Instantly share code, notes, and snippets.

@mistymntncop

mistymntncop/zipper.c

Last active July 8, 2025 02:06
Show Gist options
  • Save mistymntncop/3fd09e83d6df306c6a2a2bead05ab2cd to your computer and use it in GitHub Desktop.
Save mistymntncop/3fd09e83d6df306c6a2a2bead05ab2cd to your computer and use it in GitHub Desktop.
Download ZIP
Raw
zipper.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <malloc.h>
#include <assert.h>
//Partially Persistent Left-Leaning Red-Black Tree
//Implemented using Zippers
//https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf
//Just pedagogical. No proper memory managagement here, would use Arenas in practice
// cl -Zi -Od /INCREMENTAL:NO zipper.c
enum {
LEFT = 0,
RIGHT = 1,
NODE_CHILD_COUNT = 2,
};
typedef enum Color Color;
enum Color {
RED = 1,
BLACK = 0,
};
typedef struct Node Node;
struct Node {
uint64_t key;
uint64_t value;
Color color;
uint32_t ref_count;
Node *children[NODE_CHILD_COUNT];
};
typedef struct Tree Tree;
struct Tree {
Node **roots;
uint32_t roots_count;
//Arena *roots_arena;
//Arena *nodes_arena;
//Node **free_list;
};
typedef struct ZipperNode ZipperNode;
struct ZipperNode {
Node *parent;
uint32_t child_index;
bool dirty;
bool dont_release;
ZipperNode *prev;
};
typedef struct Zipper Zipper;
struct Zipper {
bool dirty;
bool dont_release;
//context
Node *focus;
ZipperNode *path;
uint32_t path_count;
};
static Node *node_acquire(Node *node) {
if(node == 0) return 0;
node->ref_count++;
return node;
}
static void node_release(Node *node) {
if(node == 0) return;
assert(node->ref_count != 0);
if(--node->ref_count == 0) {
for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
node_release(node->children[i]);
}
free(node);
}
}
static Node *node_clone(Node *src) {
Node *node = calloc(1, sizeof(Node));
node->key = src->key;
node->value = src->value;
node->color = src->color;
node->ref_count = 1;
for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
node->children[i] = node_acquire(src->children[i]);
}
return node;
}
static bool is_red(Node *node) {
bool result = node && node->color == RED;
return result;
}
static void go_down(Zipper *zipper, uint32_t child_index) {
Node *current = zipper->focus;
bool dirty = false;
assert(child_index < NODE_CHILD_COUNT);
Node *child = current ? current->children[child_index] : 0;
if(zipper->dirty && child && child->ref_count == 1) {
dirty = true;
}
ZipperNode *path_node = calloc(1, sizeof(ZipperNode));
path_node->parent = current;
path_node->child_index = child_index;
path_node->dirty = zipper->dirty;
path_node->dont_release = zipper->dont_release;
path_node->prev = zipper->path;
zipper->path = path_node;
zipper->path_count++;
zipper->focus = child;
zipper->dirty = dirty;
zipper->dont_release = false;
}
static void go_up(Zipper *zipper) {
if(zipper->path != 0) {
ZipperNode *path_node = zipper->path;
zipper->path = path_node->prev;
zipper->path_count--;
Node *current = zipper->focus;
Node *parent = path_node->parent;
Node *new_focus = parent;
uint32_t child_index = path_node->child_index;
bool dirty = path_node->dirty;
Node *original_child = parent ? parent->children[child_index] : 0;
if(original_child != current) {
if(zipper->dirty && !dirty) {
Node *new_parent = node_clone(parent);
new_focus = new_parent;
dirty = true;
}
new_focus->children[child_index] = current;
if(!zipper->dont_release) {
node_release(original_child);
}
}
zipper->focus = new_focus;
zipper->dirty = dirty;
zipper->dont_release = path_node->dont_release;
free(path_node);
}
}
static Node *commit(Zipper *zipper) {
while(zipper->path != 0) {
go_up(zipper);
}
Node *root = zipper->focus;
return root;
}
static Node *mutable_focus(Zipper *zipper) {
Node *node = zipper->focus;
if(!zipper->dirty) {
node = node_clone(node);
zipper->focus = node;
zipper->dirty = true;
}
return node;
}
static void update_child(Zipper *zipper, uint32_t child_index, Node *child, bool dont_release) {
Node *node = mutable_focus(zipper);
Node *original_child = node->children[child_index];
node->children[child_index] = child;
if(!dont_release) {
node_release(original_child);
}
}
static void update_color(Zipper *zipper, Color color) {
Node *node = mutable_focus(zipper);
node->color = color;
}
static void update(Zipper *zipper, uint64_t value) {
Node *node = mutable_focus(zipper);
node->value = value;
}
static void rotate_left(Zipper *zipper) {
Node *h = mutable_focus(zipper);
Color color = h->color;
Node *x = h->children[RIGHT];
update_child(zipper, RIGHT, x->children[LEFT], true);
update_color(zipper, RED);
zipper->focus = x;
zipper->dirty = x->ref_count == 1;
zipper->dont_release = true;
update_child(zipper, LEFT, h, true);
update_color(zipper, color);
}
static void rotate_right(Zipper *zipper) {
Node *h = mutable_focus(zipper);
Color color = h->color;
Node *x = h->children[LEFT];
update_child(zipper, LEFT, x->children[RIGHT], true);
update_color(zipper, RED);
zipper->focus = x;
zipper->dirty = x->ref_count == 1;
zipper->dont_release = true;
update_child(zipper, RIGHT, h, true);
update_color(zipper, color);
}
static void flip_color(Zipper *zipper) {
go_down(zipper, LEFT);
update_color(zipper, !zipper->focus->color);
go_up(zipper);
go_down(zipper, RIGHT);
update_color(zipper, !zipper->focus->color);
go_up(zipper);
update_color(zipper, !zipper->focus->color);
}
static bool insert(Zipper *zipper, uint64_t key, uint64_t value) {
bool insert_node = true;
while(zipper->focus != 0) {
Node *node = zipper->focus;
if(is_red(node->children[LEFT]) && is_red(node->children[RIGHT])) {
flip_color(zipper);
}
if(key < node->key) {
go_down(zipper, LEFT);
} else if(key > node->key) {
go_down(zipper, RIGHT);
} else {
update(zipper, value);
insert_node = false;
break;
}
}
if(insert_node) {
Node *new_node = calloc(1, sizeof(Node));
new_node->key = key;
new_node->value = value;
new_node->color = RED;
new_node->ref_count = 1;
zipper->focus = new_node;
zipper->dirty = true;
}
while(zipper->path != 0) {
go_up(zipper);
Node *node = zipper->focus;
//balancing
if(is_red(node->children[RIGHT]) && !is_red(node->children[LEFT])) {
rotate_left(zipper);
node = zipper->focus;
}
if(is_red(node->children[LEFT]) && is_red(node->children[LEFT]->children[LEFT])) {
rotate_right(zipper);
node = zipper->focus;
}
}
update_color(zipper, BLACK);
return insert_node;
}
static Zipper init_zipper(Node *root) {
Zipper zipper = { .focus = root };
return zipper;
}
static void print_rb_tree_recurse(Node *node) {
printf("\tn_%lld_%p [label=\"%lld\\nrc: %d\"];\n", node->key, node, node->key, node->ref_count);
for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
Node *child = node->children[i];
if(child) {
char *color = child->color == RED ? "red" : "black";
uint32_t penwidth = child->color == RED ? 5 : 1;
printf("\t" "n_%lld_%p -> n_%lld_%p [color=\"%s\", penwidth=%d, dir=none];\n",
node->key, node, child->key, child, color, penwidth );
print_rb_tree_recurse(child);
}
}
}
static void print_rb_tree(Node *node) {
printf("strict digraph BST {\n");
print_rb_tree_recurse(node);
printf("}\n");
}
int main() {
Zipper zipper = init_zipper(0);
for(uint32_t i = 0; i < 10; i++) {
insert(&zipper, i, i);
}
Node *root = commit(&zipper);
zipper = init_zipper(root);
for(uint32_t i = 10; i < 20; i++) {
insert(&zipper, i, i);
}
Node *root2 = commit(&zipper);
printf("strict digraph BST {\n");
print_rb_tree_recurse(root);
print_rb_tree_recurse(root2);
printf("}\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment