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

Revisions

  1. mistymntncop revised this gist Jul 8, 2025. 1 changed file with 2 additions and 19 deletions.
    21 changes: 2 additions & 19 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -26,10 +26,7 @@ enum Color {
    typedef struct Node Node;
    struct Node {
    uint64_t key;
    union {
    //char value_u8;
    uint64_t value;
    };
    uint64_t value;
    Color color;
    uint32_t ref_count;
    Node *children[NODE_CHILD_COUNT];
    @@ -52,7 +49,6 @@ struct ZipperNode {
    bool dirty;
    bool dont_release;


    ZipperNode *prev;
    };

    @@ -82,7 +78,7 @@ static void node_release(Node *node) {
    for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
    node_release(node->children[i]);
    }
    //free(node);
    free(node);
    }
    }

    @@ -236,18 +232,6 @@ static void flip_color(Zipper *zipper) {
    update_color(zipper, !zipper->focus->color);
    }

    static void move_red_left(Zipper *zipper) {
    Node *node = zipper->focus;
    flip_color(zipper);
    if(node->children[RIGHT] && is_red(node->children[RIGHT]->children[LEFT])) {
    go_down(zipper, RIGHT);
    rotate_right(zipper);
    go_up(zipper);
    rotate_left(zipper);
    flip_color(zipper);
    }
    }

    static bool insert(Zipper *zipper, uint64_t key, uint64_t value) {
    bool insert_node = true;
    while(zipper->focus != 0) {
    @@ -314,7 +298,6 @@ static void print_rb_tree_recurse(Node *node) {
    print_rb_tree_recurse(child);
    }
    }

    }

    static void print_rb_tree(Node *node) {
  2. mistymntncop revised this gist Jul 7, 2025. 1 changed file with 3 additions and 4 deletions.
    7 changes: 3 additions & 4 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -262,7 +262,7 @@ static bool insert(Zipper *zipper, uint64_t key, uint64_t value) {
    } else if(key > node->key) {
    go_down(zipper, RIGHT);
    } else {
    node->value = value;
    update(zipper, value);
    insert_node = false;
    break;
    }
    @@ -292,9 +292,8 @@ static bool insert(Zipper *zipper, uint64_t key, uint64_t value) {
    node = zipper->focus;
    }
    }
    if(insert_node) {
    update_color(zipper, BLACK);
    }
    update_color(zipper, BLACK);

    return insert_node;
    }

  3. mistymntncop revised this gist Jul 7, 2025. 1 changed file with 19 additions and 19 deletions.
    38 changes: 19 additions & 19 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -248,7 +248,8 @@ static void move_red_left(Zipper *zipper) {
    }
    }

    static void insert(Zipper *zipper, uint64_t key, uint64_t value) {
    static bool insert(Zipper *zipper, uint64_t key, uint64_t value) {
    bool insert_node = true;
    while(zipper->focus != 0) {
    Node *node = zipper->focus;

    @@ -261,19 +262,21 @@ static void insert(Zipper *zipper, uint64_t key, uint64_t value) {
    } else if(key > node->key) {
    go_down(zipper, RIGHT);
    } else {
    assert(!"moo");
    return; //TODO: better story
    node->value = value;
    insert_node = false;
    break;
    }
    }
    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;

    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;
    @@ -289,20 +292,17 @@ static void insert(Zipper *zipper, uint64_t key, uint64_t value) {
    node = zipper->focus;
    }
    }
    update_color(zipper, BLACK);
    if(insert_node) {
    update_color(zipper, BLACK);
    }
    return insert_node;
    }

    static Zipper init_zipper(Node *root) {
    Zipper zipper = { .focus = root };
    return zipper;
    }


    static void rb_insert(Tree *tree, uint64_t key, uint64_t value) {


    }

    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++) {
  4. mistymntncop revised this gist Jul 7, 2025. 1 changed file with 5 additions and 3 deletions.
    8 changes: 5 additions & 3 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -304,12 +304,14 @@ static void rb_insert(Tree *tree, uint64_t key, uint64_t value) {
    }

    static void print_rb_tree_recurse(Node *node) {
    printf("\tn%p [label=\"%lld\\nrc: %d\"];\n", node, node->key, node->ref_count);
    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) {
    printf("\t" "n%p -> n%p [color=\"%s\"];\n",
    node, child, child->color == RED ? "red" : "blue");
    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);
    }
    }
  5. mistymntncop revised this gist Jul 7, 2025. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -308,7 +308,8 @@ static void print_rb_tree_recurse(Node *node) {
    for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
    Node *child = node->children[i];
    if(child) {
    printf("\t" "n%p -> n%p;\n", node, child);
    printf("\t" "n%p -> n%p [color=\"%s\"];\n",
    node, child, child->color == RED ? "red" : "blue");
    print_rb_tree_recurse(child);
    }
    }
  6. mistymntncop revised this gist Jul 7, 2025. 1 changed file with 31 additions and 65 deletions.
    96 changes: 31 additions & 65 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -150,7 +150,6 @@ static void go_up(Zipper *zipper) {
    dirty = true;
    }
    new_focus->children[child_index] = current;
    //node_acquire(current);
    if(!zipper->dont_release) {
    node_release(original_child);
    }
    @@ -186,7 +185,6 @@ static void update_child(Zipper *zipper, uint32_t child_index, Node *child, bool
    Node *node = mutable_focus(zipper);
    Node *original_child = node->children[child_index];
    node->children[child_index] = child;
    //node_acquire(child);
    if(!dont_release) {
    node_release(original_child);
    }
    @@ -305,77 +303,45 @@ static void rb_insert(Tree *tree, uint64_t key, uint64_t value) {

    }

    static void print_rb_tree_recurse(Node *node) {
    printf("\tn%p [label=\"%lld\\nrc: %d\"];\n", node, node->key, node->ref_count);
    for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
    Node *child = node->children[i];
    if(child) {
    printf("\t" "n%p -> n%p;\n", node, child);
    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() {
    // A
    // / \
    // B F
    // / \ /
    // D E C
    Zipper zipper = init_zipper(0);

    Node *root = 0;
    Zipper zipper = init_zipper(0); //A

    #if 1
    for(uint32_t i = 0; i < 10; i++) {
    insert(&zipper, i, i);
    }
    #else

    insert(&zipper, 50, 'A');
    insert(&zipper, 25, 'B');
    insert(&zipper, 75, 'C');
    insert(&zipper, 12, 'D');
    insert(&zipper, 30, 'E');
    insert(&zipper, 83, 'F');
    #endif
    root = commit(&zipper); //A

    Node *root = commit(&zipper);

    zipper = init_zipper(root);

    Node *root2 = 0;
    {
    Zipper zipper = init_zipper(root);

    for(uint32_t i = 10; i < 20; i++) {
    insert(&zipper, i, i);
    }
    root2 = commit(&zipper);

    int lol = 3;
    for(uint32_t i = 10; i < 20; i++) {
    insert(&zipper, i, i);
    }


    int lol = 3;

    /*
    Zipper zipper = init_zipper(root); //A
    //update(&zipper, 'W'); //A->W
    //update(&zipper, 'X'); //W->X
    go_down(&zipper, LEFT); //B
    update(&zipper, 'P');
    go_down(&zipper, LEFT); //D
    update(&zipper, 'Y'); //D->Y
    go_up(&zipper); //B'
    go_down(&zipper, RIGHT); //E
    update(&zipper, 'Z'); //Z
    Node *new_root = commit(&zipper); //X
    */


    // X
    // / \
    // B' C
    // / \ \
    // Y Z F

    Node *root2 = commit(&zipper);

    printf("strict digraph BST {\n");
    print_rb_tree_recurse(root);
    print_rb_tree_recurse(root2);
    printf("}\n");

    return 0;
    }
  7. mistymntncop revised this gist Jul 7, 2025. 1 changed file with 30 additions and 19 deletions.
    49 changes: 30 additions & 19 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -5,6 +5,10 @@
    #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 {
    @@ -72,7 +76,7 @@ static Node *node_acquire(Node *node) {

    static void node_release(Node *node) {
    if(node == 0) return;
    //assert(node->ref_count != 0);
    assert(node->ref_count != 0);

    if(--node->ref_count == 0) {
    for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
    @@ -168,13 +172,18 @@ static Node *commit(Zipper *zipper) {
    return root;
    }

    static void update_child(Zipper *zipper, uint32_t child_index, Node *child, bool dont_release) {
    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;
    //node_acquire(child);
    @@ -184,27 +193,17 @@ static void update_child(Zipper *zipper, uint32_t child_index, Node *child, bool
    }

    static void update_color(Zipper *zipper, Color color) {
    Node *node = zipper->focus;
    if(!zipper->dirty) {
    node = node_clone(node);
    zipper->focus = node;
    zipper->dirty = true;
    }
    Node *node = mutable_focus(zipper);
    node->color = color;
    }

    static void update(Zipper *zipper, uint64_t value) {
    Node *node = zipper->focus;
    if(!zipper->dirty) {
    node = node_clone(node);
    zipper->focus = node;
    zipper->dirty = true;
    }
    Node *node = mutable_focus(zipper);
    node->value = value;
    }

    static void rotate_left(Zipper *zipper) {
    Node *h = zipper->focus;
    Node *h = mutable_focus(zipper);
    Color color = h->color;
    Node *x = h->children[RIGHT];
    update_child(zipper, RIGHT, x->children[LEFT], true);
    @@ -217,7 +216,7 @@ static void rotate_left(Zipper *zipper) {
    }

    static void rotate_right(Zipper *zipper) {
    Node *h = zipper->focus;
    Node *h = mutable_focus(zipper);
    Color color = h->color;
    Node *x = h->children[LEFT];
    update_child(zipper, LEFT, x->children[RIGHT], true);
    @@ -239,6 +238,18 @@ static void flip_color(Zipper *zipper) {
    update_color(zipper, !zipper->focus->color);
    }

    static void move_red_left(Zipper *zipper) {
    Node *node = zipper->focus;
    flip_color(zipper);
    if(node->children[RIGHT] && is_red(node->children[RIGHT]->children[LEFT])) {
    go_down(zipper, RIGHT);
    rotate_right(zipper);
    go_up(zipper);
    rotate_left(zipper);
    flip_color(zipper);
    }
    }

    static void insert(Zipper *zipper, uint64_t key, uint64_t value) {
    while(zipper->focus != 0) {
    Node *node = zipper->focus;
    @@ -253,7 +264,7 @@ static void insert(Zipper *zipper, uint64_t key, uint64_t value) {
    go_down(zipper, RIGHT);
    } else {
    assert(!"moo");
    return;
    return; //TODO: better story
    }
    }
    Node *new_node = calloc(1, sizeof(Node));
    @@ -320,14 +331,14 @@ int main() {
    #endif
    root = commit(&zipper); //A


    Node *root2 = 0;
    {
    Zipper zipper = init_zipper(root);

    for(uint32_t i = 10; i < 20; i++) {
    insert(&zipper, i, i);
    }
    Node *root2 = commit(&zipper);
    root2 = commit(&zipper);

    int lol = 3;
    }
  8. mistymntncop revised this gist Jul 7, 2025. 1 changed file with 8 additions and 6 deletions.
    14 changes: 8 additions & 6 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -168,7 +168,7 @@ static Node *commit(Zipper *zipper) {
    return root;
    }

    static void update_child(Zipper *zipper, uint32_t child_index, Node *child) {
    static void update_child(Zipper *zipper, uint32_t child_index, Node *child, bool dont_release) {
    Node *node = zipper->focus;
    if(!zipper->dirty) {
    node = node_clone(node);
    @@ -178,7 +178,9 @@ static void update_child(Zipper *zipper, uint32_t child_index, Node *child) {
    Node *original_child = node->children[child_index];
    node->children[child_index] = child;
    //node_acquire(child);
    //node_release(original_child);
    if(!dont_release) {
    node_release(original_child);
    }
    }

    static void update_color(Zipper *zipper, Color color) {
    @@ -205,25 +207,25 @@ static void rotate_left(Zipper *zipper) {
    Node *h = zipper->focus;
    Color color = h->color;
    Node *x = h->children[RIGHT];
    update_child(zipper, RIGHT, x->children[LEFT]);
    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);
    update_child(zipper, LEFT, h, true);
    update_color(zipper, color);
    }

    static void rotate_right(Zipper *zipper) {
    Node *h = zipper->focus;
    Color color = h->color;
    Node *x = h->children[LEFT];
    update_child(zipper, LEFT, x->children[RIGHT]);
    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);
    update_child(zipper, RIGHT, h, true);
    update_color(zipper, color);
    }

  9. mistymntncop revised this gist Jul 6, 2025. 1 changed file with 216 additions and 93 deletions.
    309 changes: 216 additions & 93 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -6,37 +6,56 @@
    #include <assert.h>

    //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,
    };

    #define 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;
    union {
    //char value_u8;
    uint64_t value;
    };
    Color color;
    uint32_t ref_count;
    Node *children[NODE_CHILD_COUNT];
    };

    typedef struct Tree Tree;
    struct Tree {
    Node *root;
    uint32_t node_count;
    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;

    Node *original;

    ZipperNode *prev;
    };

    typedef struct Zipper Zipper;
    struct Zipper {
    //focus in the unmodified tree
    Node *original;
    bool dirty;
    bool dont_release;

    //context
    Node *focus;
    @@ -45,86 +64,66 @@ struct Zipper {
    uint32_t path_count;
    };

    Node *node_acquire(Node *node) {
    static Node *node_acquire(Node *node) {
    if(node == 0) return 0;
    node->ref_count++;
    return node;
    }

    void node_release(Node *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);
    //free(node);
    }
    }

    static Node *node_clone(Node *src) {
    Node *node = malloc(sizeof(Node));
    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 Node **bst_search(Node **root_ptr, uint64_t key) {
    Node **node_ptr = root_ptr;

    while((*node_ptr)) {
    Node *node = *node_ptr;

    if(key < node->key) {
    node_ptr = &node->children[0];
    } else if(key > node->key) {
    node_ptr = &node->children[1];
    } else {
    return node_ptr;
    }
    }
    return node_ptr;
    }

    static Node *bst_insert(Node **root_ptr, uint64_t key, uint64_t value) {
    Node **best_match_ptr = bst_search(root_ptr, key);
    Node *best_match = *best_match_ptr;
    if(best_match && best_match->key == key) {
    return 0;
    }
    Node *node = calloc(1, sizeof(Node));
    node->ref_count = 1;
    node->key = key;
    node->value = value;

    *best_match_ptr = node;

    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;
    Node *original = zipper->original;

    bool dirty = false;

    assert(child_index < NODE_CHILD_COUNT);
    Node *child = current->children[child_index];
    Node *original_child = original ? original->children[child_index] : 0;

    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->original = original;
    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->original = original_child;
    zipper->dirty = dirty;
    zipper->dont_release = false;
    }

    static void go_up(Zipper *zipper) {
    @@ -137,25 +136,31 @@ static void go_up(Zipper *zipper) {
    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->children[child_index];
    Node *original_child = parent ? parent->children[child_index] : 0;
    if(original_child != current) {
    if(path_node->original == parent) {
    if(zipper->dirty && !dirty) {
    Node *new_parent = node_clone(parent);
    new_focus = new_parent;
    }
    node_release(original_child);
    dirty = true;
    }
    new_focus->children[child_index] = current;
    //node_acquire(current);
    if(!zipper->dont_release) {
    node_release(original_child);
    }
    }

    zipper->focus = new_focus;
    zipper->original = path_node->original;

    zipper->dirty = dirty;
    zipper->dont_release = path_node->dont_release;

    free(path_node);
    }
    }

    Node *commit(Zipper *zipper) {
    static Node *commit(Zipper *zipper) {
    while(zipper->path != 0) {
    go_up(zipper);
    }
    @@ -165,80 +170,198 @@ Node *commit(Zipper *zipper) {

    static void update_child(Zipper *zipper, uint32_t child_index, Node *child) {
    Node *node = zipper->focus;
    if(node == zipper->original) {
    if(!zipper->dirty) {
    node = node_clone(node);
    zipper->focus = node;
    zipper->dirty = true;
    }
    Node *original_child = node->children[child_index];
    node_release(original_child);

    node->children[child_index] = child;
    //node_acquire(child);
    //node_release(original_child);
    }

    static void update_color(Zipper *zipper, Color color) {
    Node *node = zipper->focus;
    if(!zipper->dirty) {
    node = node_clone(node);
    zipper->focus = node;
    zipper->dirty = true;
    }
    node->color = color;
    }

    static void update(Zipper *zipper, uint64_t value) {
    Node *node = zipper->focus;
    if(node == zipper->original) {
    if(!zipper->dirty) {
    node = node_clone(node);
    zipper->focus = node;
    zipper->dirty = true;
    }
    node->value = value;
    }

    static void replace(Zipper *zipper, Node *new_node) {
    //Node *old_node = zipper->focus;
    //node_release(old_node);
    static void rotate_left(Zipper *zipper) {
    Node *h = zipper->focus;
    Color color = h->color;
    Node *x = h->children[RIGHT];
    update_child(zipper, RIGHT, x->children[LEFT]);
    update_color(zipper, RED);
    zipper->focus = x;
    zipper->dirty = x->ref_count == 1;
    zipper->dont_release = true;
    update_child(zipper, LEFT, h);
    update_color(zipper, color);
    }

    static void rotate_right(Zipper *zipper) {
    Node *h = zipper->focus;
    Color color = h->color;
    Node *x = h->children[LEFT];
    update_child(zipper, LEFT, x->children[RIGHT]);
    update_color(zipper, RED);
    zipper->focus = x;
    zipper->dirty = x->ref_count == 1;
    zipper->dont_release = true;
    update_child(zipper, RIGHT, h);
    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 void insert(Zipper *zipper, uint64_t key, uint64_t value) {
    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 {
    assert(!"moo");
    return;
    }
    }
    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);
    }

    Zipper init_zipper(Node *root) {
    Zipper zipper = { .focus = root, .original = root };
    static Zipper init_zipper(Node *root) {
    Zipper zipper = { .focus = root };
    return zipper;
    }

    int main() {
    Node *root = 0;
    bst_insert(&root, 50, 'A');
    bst_insert(&root, 25, 'B');
    bst_insert(&root, 75, 'C');
    bst_insert(&root, 12, 'D');
    bst_insert(&root, 83, 'E');
    bst_insert(&root, 30, 'F');

    // 50

    static void rb_insert(Tree *tree, uint64_t key, uint64_t value) {


    }


    int main() {
    // A
    // / \
    // 25 75
    // / \ \
    // 12 30 83
    // B F
    // / \ /
    // D E C

    Node *root = 0;
    Zipper zipper = init_zipper(0); //A

    Zipper zipper = init_zipper(root);
    #if 1
    for(uint32_t i = 0; i < 10; i++) {
    insert(&zipper, i, i);
    }
    #else

    insert(&zipper, 50, 'A');
    insert(&zipper, 25, 'B');
    insert(&zipper, 75, 'C');
    insert(&zipper, 12, 'D');
    insert(&zipper, 30, 'E');
    insert(&zipper, 83, 'F');
    #endif
    root = commit(&zipper); //A


    {
    Zipper zipper = init_zipper(root);

    for(uint32_t i = 10; i < 20; i++) {
    insert(&zipper, i, i);
    }
    Node *root2 = commit(&zipper);

    int lol = 3;
    }

    update(&zipper, 'W');
    update(&zipper, 'X');

    go_down(&zipper, 0);
    int lol = 3;

    go_down(&zipper, 0);
    /*
    Zipper zipper = init_zipper(root); //A
    update(&zipper, 'Y');
    //update(&zipper, 'W'); //A->W
    //update(&zipper, 'X'); //W->X
    go_up(&zipper);
    go_down(&zipper, LEFT); //B
    go_down(&zipper, 1);
    update(&zipper, 'P');
    update(&zipper, 'Z');
    go_down(&zipper, LEFT); //D
    Node *new_root = commit(&zipper);
    update(&zipper, 'Y'); //D->Y
    go_down(&zipper, 0);
    go_up(&zipper); //B'
    go_down(&zipper, 0);
    go_down(&zipper, RIGHT); //E
    update(&zipper, 'Z'); //Z
    // 2222
    Node *new_root = commit(&zipper); //X
    */


    // X
    // / \
    // 25 75
    // B' C
    // / \ \
    // 666 777 83
    // Y Z F


    return 0;
  10. mistymntncop revised this gist May 16, 2025. 1 changed file with 10 additions and 7 deletions.
    17 changes: 10 additions & 7 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -72,6 +72,7 @@ static Node *node_clone(Node *src) {
    return node;
    }


    static Node **bst_search(Node **root_ptr, uint64_t key) {
    Node **node_ptr = root_ptr;

    @@ -111,7 +112,7 @@ static void go_down(Zipper *zipper, uint32_t child_index) {

    assert(child_index < NODE_CHILD_COUNT);
    Node *child = current->children[child_index];
    Node *original_child = original->children[child_index];
    Node *original_child = original ? original->children[child_index] : 0;

    ZipperNode *path_node = calloc(1, sizeof(ZipperNode));
    path_node->parent = current;
    @@ -135,14 +136,16 @@ static void go_up(Zipper *zipper) {
    Node *current = zipper->focus;
    Node *parent = path_node->parent;
    Node *new_focus = parent;
    uint32_t child_index = path_node->child_index;

    Node *original_child = parent->children[path_node->child_index];
    if(original_child != current) {
    Node *original_child = parent->children[child_index];
    if(original_child != current) {
    if(path_node->original == parent) {
    Node *new_parent = node_clone(parent);
    new_focus = new_parent;
    }
    new_focus->children[path_node->child_index] = current;
    node_release(original_child);
    new_focus->children[child_index] = current;
    }

    zipper->focus = new_focus;
    @@ -182,8 +185,8 @@ static void update(Zipper *zipper, uint64_t value) {
    }

    static void replace(Zipper *zipper, Node *new_node) {
    Node *old_node = zipper->focus;
    node_release(old_node);
    //Node *old_node = zipper->focus;
    //node_release(old_node);
    zipper->focus = new_node;
    }

    @@ -192,7 +195,7 @@ Zipper init_zipper(Node *root) {
    return zipper;
    }

    int main() {
    int main() {
    Node *root = 0;
    bst_insert(&root, 50, 'A');
    bst_insert(&root, 25, 'B');
  11. mistymntncop revised this gist May 16, 2025. 1 changed file with 20 additions and 17 deletions.
    37 changes: 20 additions & 17 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -11,6 +11,7 @@

    typedef struct Node Node;
    struct Node {
    uint64_t key;
    uint64_t value;
    uint32_t ref_count;
    Node *children[NODE_CHILD_COUNT];
    @@ -60,8 +61,9 @@ void node_release(Node *node) {
    }
    }

    Node *node_clone(Node *src) {
    static Node *node_clone(Node *src) {
    Node *node = malloc(sizeof(Node));
    node->key = src->key;
    node->value = src->value;
    node->ref_count = 1;
    for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
    @@ -70,15 +72,15 @@ Node *node_clone(Node *src) {
    return node;
    }

    Node **bst_search(Node **root_ptr, uint64_t find) {
    static Node **bst_search(Node **root_ptr, uint64_t key) {
    Node **node_ptr = root_ptr;

    while((*node_ptr)) {
    Node *node = *node_ptr;

    if(find < node->value) {
    if(key < node->key) {
    node_ptr = &node->children[0];
    } else if(find > node->value) {
    } else if(key > node->key) {
    node_ptr = &node->children[1];
    } else {
    return node_ptr;
    @@ -87,14 +89,15 @@ Node **bst_search(Node **root_ptr, uint64_t find) {
    return node_ptr;
    }

    Node *bst_insert(Node **root_ptr, uint64_t value) {
    Node **best_match_ptr = bst_search(root_ptr, value);
    static Node *bst_insert(Node **root_ptr, uint64_t key, uint64_t value) {
    Node **best_match_ptr = bst_search(root_ptr, key);
    Node *best_match = *best_match_ptr;
    if(best_match && best_match->value == value) {
    if(best_match && best_match->key == key) {
    return 0;
    }
    Node *node = calloc(1, sizeof(Node));
    node->ref_count = 1;
    node->key = key;
    node->value = value;

    *best_match_ptr = node;
    @@ -191,12 +194,12 @@ Zipper init_zipper(Node *root) {

    int main() {
    Node *root = 0;
    bst_insert(&root, 50);
    bst_insert(&root, 25);
    bst_insert(&root, 75);
    bst_insert(&root, 12);
    bst_insert(&root, 83);
    bst_insert(&root, 30);
    bst_insert(&root, 50, 'A');
    bst_insert(&root, 25, 'B');
    bst_insert(&root, 75, 'C');
    bst_insert(&root, 12, 'D');
    bst_insert(&root, 83, 'E');
    bst_insert(&root, 30, 'F');

    // 50
    // / \
    @@ -206,20 +209,20 @@ int main() {

    Zipper zipper = init_zipper(root);

    update(&zipper, 1111);
    update(&zipper, 2222);
    update(&zipper, 'W');
    update(&zipper, 'X');

    go_down(&zipper, 0);

    go_down(&zipper, 0);

    update(&zipper, 666);
    update(&zipper, 'Y');

    go_up(&zipper);

    go_down(&zipper, 1);

    update(&zipper, 777);
    update(&zipper, 'Z');

    Node *new_root = commit(&zipper);

  12. mistymntncop revised this gist May 16, 2025. 1 changed file with 50 additions and 18 deletions.
    68 changes: 50 additions & 18 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -12,6 +12,7 @@
    typedef struct Node Node;
    struct Node {
    uint64_t value;
    uint32_t ref_count;
    Node *children[NODE_CHILD_COUNT];
    };

    @@ -33,16 +34,42 @@ struct ZipperNode {

    typedef struct Zipper Zipper;
    struct Zipper {
    Node *focus;

    //focus in the unmodified tree
    Node *original;

    //context
    Node *focus;

    ZipperNode *path;
    uint32_t path_count;
    };

    Node *node_acquire(Node *node) {
    if(node == 0) return 0;
    node->ref_count++;
    return node;
    }

    void node_release(Node *node) {
    if(node == 0) return;
    if(--node->ref_count == 0) {
    for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
    node_release(node->children[i]);
    }
    free(node);
    }
    }

    Node *node_clone(Node *src) {
    Node *node = malloc(sizeof(Node));
    node->value = src->value;
    node->ref_count = 1;
    for(uint32_t i = 0; i < NODE_CHILD_COUNT; i++) {
    node->children[i] = node_acquire(src->children[i]);
    }
    return node;
    }

    Node **bst_search(Node **root_ptr, uint64_t find) {
    Node **node_ptr = root_ptr;

    @@ -67,14 +94,15 @@ Node *bst_insert(Node **root_ptr, uint64_t value) {
    return 0;
    }
    Node *node = calloc(1, sizeof(Node));
    node->ref_count = 1;
    node->value = value;

    *best_match_ptr = node;

    return node;
    }

    void go_down(Zipper *zipper, uint32_t child_index) {
    static void go_down(Zipper *zipper, uint32_t child_index) {
    Node *current = zipper->focus;
    Node *original = zipper->original;

    @@ -95,28 +123,29 @@ void go_down(Zipper *zipper, uint32_t child_index) {
    zipper->original = original_child;
    }

    void go_up(Zipper *zipper) {
    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;

    Node *original_child = parent->children[path_node->child_index];
    if(original_child != current) {
    if(path_node->original == parent) { //allow in-place mutation of in-progress uncommitted tree
    Node *new_parent = malloc(sizeof(Node));
    memcpy(new_parent, parent, sizeof(*new_parent));
    if(path_node->original == parent) {
    Node *new_parent = node_clone(parent);
    new_focus = new_parent;
    }
    new_focus->children[path_node->child_index] = current;
    }

    zipper->path = path_node->prev;
    zipper->path_count--;

    zipper->focus = new_focus;
    zipper->original = path_node->original;

    free(path_node);
    }
    }

    @@ -128,27 +157,30 @@ Node *commit(Zipper *zipper) {
    return root;
    }

    void update_child(Zipper *zipper, uint32_t child_index, Node *children) {
    static void update_child(Zipper *zipper, uint32_t child_index, Node *child) {
    Node *node = zipper->focus;
    if(node == zipper->original) {
    node = malloc(sizeof(Node));
    memcpy(node, zipper->focus, sizeof(*node));
    node = node_clone(node);
    zipper->focus = node;
    }
    node->children[child_index] = children;
    Node *original_child = node->children[child_index];
    node_release(original_child);

    node->children[child_index] = child;
    }

    void update(Zipper *zipper, uint64_t value) {
    static void update(Zipper *zipper, uint64_t value) {
    Node *node = zipper->focus;
    if(node == zipper->original) {
    node = malloc(sizeof(Node));
    memcpy(node, zipper->focus, sizeof(*node));
    node = node_clone(node);
    zipper->focus = node;
    }
    node->value = value;
    }

    void replace(Zipper *zipper, Node *new_node) {
    static void replace(Zipper *zipper, Node *new_node) {
    Node *old_node = zipper->focus;
    node_release(old_node);
    zipper->focus = new_node;
    }

  13. mistymntncop revised this gist May 14, 2025. 1 changed file with 12 additions and 9 deletions.
    21 changes: 12 additions & 9 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -128,15 +128,14 @@ Node *commit(Zipper *zipper) {
    return root;
    }

    void insert_children(Zipper *zipper, Node *children[NODE_CHILD_COUNT]) {
    Node *node = malloc(sizeof(Node));
    memcpy(&node->children, children, sizeof(node->children));
    node->value = zipper->focus->value;
    zipper->focus = node;
    }

    void replace(Zipper *zipper, Node *new_node) {
    zipper->focus = new_node;
    void update_child(Zipper *zipper, uint32_t child_index, Node *children) {
    Node *node = zipper->focus;
    if(node == zipper->original) {
    node = malloc(sizeof(Node));
    memcpy(node, zipper->focus, sizeof(*node));
    zipper->focus = node;
    }
    node->children[child_index] = children;
    }

    void update(Zipper *zipper, uint64_t value) {
    @@ -149,6 +148,10 @@ void update(Zipper *zipper, uint64_t value) {
    node->value = value;
    }

    void replace(Zipper *zipper, Node *new_node) {
    zipper->focus = new_node;
    }

    Zipper init_zipper(Node *root) {
    Zipper zipper = { .focus = root, .original = root };
    return zipper;
  14. mistymntncop revised this gist May 14, 2025. 1 changed file with 8 additions and 2 deletions.
    10 changes: 8 additions & 2 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -76,21 +76,23 @@ Node *bst_insert(Node **root_ptr, uint64_t value) {

    void go_down(Zipper *zipper, uint32_t child_index) {
    Node *current = zipper->focus;
    Node *original = zipper->original;

    assert(child_index < NODE_CHILD_COUNT);
    Node *child = current->children[child_index];
    Node *original_child = original->children[child_index];

    ZipperNode *path_node = calloc(1, sizeof(ZipperNode));
    path_node->parent = current;
    path_node->child_index = child_index;
    path_node->original = zipper->original;
    path_node->original = original;

    path_node->prev = zipper->path;
    zipper->path = path_node;
    zipper->path_count++;

    zipper->focus = child;
    zipper->original = child;
    zipper->original = original_child;
    }

    void go_up(Zipper *zipper) {
    @@ -186,6 +188,10 @@ int main() {

    Node *new_root = commit(&zipper);

    go_down(&zipper, 0);

    go_down(&zipper, 0);


    // 2222
    // / \
  15. mistymntncop revised this gist May 14, 2025. 1 changed file with 7 additions and 0 deletions.
    7 changes: 7 additions & 0 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -185,6 +185,13 @@ int main() {
    update(&zipper, 777);

    Node *new_root = commit(&zipper);


    // 2222
    // / \
    // 25 75
    // / \ \
    // 666 777 83


    return 0;
  16. mistymntncop revised this gist May 14, 2025. 1 changed file with 15 additions and 4 deletions.
    19 changes: 15 additions & 4 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -138,10 +138,13 @@ void replace(Zipper *zipper, Node *new_node) {
    }

    void update(Zipper *zipper, uint64_t value) {
    Node *node = malloc(sizeof(Node));
    memcpy(node, zipper->focus, sizeof(*node));
    Node *node = zipper->focus;
    if(node == zipper->original) {
    node = malloc(sizeof(Node));
    memcpy(node, zipper->focus, sizeof(*node));
    zipper->focus = node;
    }
    node->value = value;
    zipper->focus = node;
    }

    Zipper init_zipper(Node *root) {
    @@ -158,9 +161,17 @@ int main() {
    bst_insert(&root, 83);
    bst_insert(&root, 30);

    // 50
    // / \
    // 25 75
    // / \ \
    // 12 30 83

    Zipper zipper = init_zipper(root);

    //update(&zipper, 1111);
    update(&zipper, 1111);
    update(&zipper, 2222);

    go_down(&zipper, 0);

    go_down(&zipper, 0);
  17. mistymntncop revised this gist May 14, 2025. 1 changed file with 1 addition and 2 deletions.
    3 changes: 1 addition & 2 deletions zipper.c
    View file
    Original file line number Diff line number Diff line change
    @@ -91,7 +91,6 @@ void go_down(Zipper *zipper, uint32_t child_index) {

    zipper->focus = child;
    zipper->original = child;

    }

    void go_up(Zipper *zipper) {
    @@ -161,8 +160,8 @@ int main() {

    Zipper zipper = init_zipper(root);

    //go_down(&zipper, 0);
    //update(&zipper, 1111);
    go_down(&zipper, 0);

    go_down(&zipper, 0);

  18. mistymntncop renamed this gist May 14, 2025. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.txt → zipper.c
    View file
    File renamed without changes.
  19. mistymntncop created this gist May 14, 2025.
    181 changes: 181 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,181 @@
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
    #include <stdbool.h>
    #include <malloc.h>
    #include <assert.h>

    //Just pedagogical. No proper memory managagement here, would use Arenas in practice

    #define NODE_CHILD_COUNT 2

    typedef struct Node Node;
    struct Node {
    uint64_t value;
    Node *children[NODE_CHILD_COUNT];
    };

    typedef struct Tree Tree;
    struct Tree {
    Node *root;
    uint32_t node_count;
    };

    typedef struct ZipperNode ZipperNode;
    struct ZipperNode {
    Node *parent;
    uint32_t child_index;

    Node *original;

    ZipperNode *prev;
    };

    typedef struct Zipper Zipper;
    struct Zipper {
    Node *focus;

    //focus in the unmodified tree
    Node *original;

    //context
    ZipperNode *path;
    uint32_t path_count;
    };

    Node **bst_search(Node **root_ptr, uint64_t find) {
    Node **node_ptr = root_ptr;

    while((*node_ptr)) {
    Node *node = *node_ptr;

    if(find < node->value) {
    node_ptr = &node->children[0];
    } else if(find > node->value) {
    node_ptr = &node->children[1];
    } else {
    return node_ptr;
    }
    }
    return node_ptr;
    }

    Node *bst_insert(Node **root_ptr, uint64_t value) {
    Node **best_match_ptr = bst_search(root_ptr, value);
    Node *best_match = *best_match_ptr;
    if(best_match && best_match->value == value) {
    return 0;
    }
    Node *node = calloc(1, sizeof(Node));
    node->value = value;

    *best_match_ptr = node;

    return node;
    }

    void go_down(Zipper *zipper, uint32_t child_index) {
    Node *current = zipper->focus;

    assert(child_index < NODE_CHILD_COUNT);
    Node *child = current->children[child_index];

    ZipperNode *path_node = calloc(1, sizeof(ZipperNode));
    path_node->parent = current;
    path_node->child_index = child_index;
    path_node->original = zipper->original;

    path_node->prev = zipper->path;
    zipper->path = path_node;
    zipper->path_count++;

    zipper->focus = child;
    zipper->original = child;

    }

    void go_up(Zipper *zipper) {
    if(zipper->path != 0) {
    ZipperNode *path_node = zipper->path;
    Node *current = zipper->focus;
    Node *parent = path_node->parent;
    Node *new_focus = parent;

    Node *original_child = parent->children[path_node->child_index];
    if(original_child != current) {
    if(path_node->original == parent) { //allow in-place mutation of in-progress uncommitted tree
    Node *new_parent = malloc(sizeof(Node));
    memcpy(new_parent, parent, sizeof(*new_parent));
    new_focus = new_parent;
    }
    new_focus->children[path_node->child_index] = current;
    }

    zipper->path = path_node->prev;
    zipper->path_count--;

    zipper->focus = new_focus;
    zipper->original = path_node->original;
    }
    }

    Node *commit(Zipper *zipper) {
    while(zipper->path != 0) {
    go_up(zipper);
    }
    Node *root = zipper->focus;
    return root;
    }

    void insert_children(Zipper *zipper, Node *children[NODE_CHILD_COUNT]) {
    Node *node = malloc(sizeof(Node));
    memcpy(&node->children, children, sizeof(node->children));
    node->value = zipper->focus->value;
    zipper->focus = node;
    }

    void replace(Zipper *zipper, Node *new_node) {
    zipper->focus = new_node;
    }

    void update(Zipper *zipper, uint64_t value) {
    Node *node = malloc(sizeof(Node));
    memcpy(node, zipper->focus, sizeof(*node));
    node->value = value;
    zipper->focus = node;
    }

    Zipper init_zipper(Node *root) {
    Zipper zipper = { .focus = root, .original = root };
    return zipper;
    }

    int main() {
    Node *root = 0;
    bst_insert(&root, 50);
    bst_insert(&root, 25);
    bst_insert(&root, 75);
    bst_insert(&root, 12);
    bst_insert(&root, 83);
    bst_insert(&root, 30);

    Zipper zipper = init_zipper(root);

    //go_down(&zipper, 0);
    //update(&zipper, 1111);

    go_down(&zipper, 0);

    update(&zipper, 666);

    go_up(&zipper);

    go_down(&zipper, 1);

    update(&zipper, 777);

    Node *new_root = commit(&zipper);


    return 0;
    }