Last active
July 8, 2025 02:06
-
-
Save mistymntncop/3fd09e83d6df306c6a2a2bead05ab2cd to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment