Last active
January 26, 2026 04:09
-
-
Save mistymntncop/d2b54ef13911f5ef203f4160bfd06102 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 <assert.h> | |
| #include <malloc.h> | |
| //"A Persistent Union-Find Data Structure" (just the Persistent Array) | |
| //https://usr.lmf.cnrs.fr/~jcf/publis/puf-wml07.pdf | |
| //Shitty arena implementation | |
| typedef struct Arena Arena; | |
| struct Arena { | |
| uint8_t *base; | |
| uint64_t size; | |
| uint64_t capacity; | |
| uint32_t flags; | |
| }; | |
| typedef enum ArenaFlags ArenaFlags; | |
| enum ArenaFlags { | |
| ARENA_FLAGS_NONE = 0, | |
| ARENA_FLAGS_NO_ZERO = (1 << 0), | |
| }; | |
| uint8_t *arena_push(Arena *arena, uint64_t size, uint32_t flags) { | |
| uint8_t *result = 0; | |
| uint64_t remaining = arena->capacity - arena->size; | |
| if(size <= remaining) { | |
| result = &arena->base[arena->size]; | |
| if(!(flags & ARENA_FLAGS_NO_ZERO)) { | |
| memset(result, 0, size); | |
| } | |
| } | |
| arena->size += size; | |
| return result; | |
| } | |
| #define push_array(a, T, c) (T*)arena_push(a, (c)*sizeof(T), 0); | |
| #define push_array_no_zero(a, T, c) (T*)arena_push(a, (c)*sizeof(T), ARENA_FLAGS_NO_ZERO); | |
| Arena *arena_alloc(uint64_t capacity) { | |
| uint8_t *base = malloc(capacity); | |
| Arena *arena = (Arena*)base; | |
| arena->base = base; | |
| arena->size = sizeof(*arena); | |
| arena->capacity = capacity; | |
| arena->flags = 0; | |
| return arena; | |
| } | |
| typedef struct PVer PVer; | |
| struct PVer { | |
| uint32_t index; | |
| uint32_t value; | |
| PVer *next; | |
| }; | |
| typedef struct PArray PArray; | |
| struct PArray { | |
| Arena *arena; | |
| uint32_t capacity; | |
| uint32_t *values; | |
| PVer *root; | |
| }; | |
| void reroot(PArray *arr, PVer *ver) { | |
| if(arr->root == ver) { return; } | |
| arr->root = ver; | |
| //reverse pointers | |
| PVer *prev = 0; | |
| PVer *next = ver; | |
| while(next != 0) { | |
| PVer *cur = next; | |
| next = cur->next; | |
| cur->next = prev; | |
| prev = cur; | |
| } | |
| //restore values | |
| next = prev->next; | |
| while(next != 0) { | |
| PVer *cur = next; | |
| next = cur->next; | |
| uint32_t old_value = arr->values[cur->index]; | |
| arr->values[cur->index] = cur->value; | |
| prev->index = cur->index; | |
| prev->value = old_value; | |
| prev = cur; | |
| } | |
| ver->index = 0; | |
| ver->value = 0; | |
| } | |
| PArray *create(uint32_t capacity) { | |
| Arena *arena = arena_alloc(0x10000); //whatever | |
| PArray *array = push_array(arena, PArray, 1); | |
| array->arena = arena; | |
| array->capacity = capacity; | |
| array->values = push_array(arena, uint32_t, capacity); | |
| PVer *root = push_array(arena, PVer, 1); | |
| array->root = root; | |
| return array; | |
| } | |
| uint32_t get(PArray *arr, PVer *ver, uint32_t index) { | |
| assert(index < arr->capacity); | |
| reroot(arr, ver); | |
| uint32_t result = arr->values[index]; | |
| return result; | |
| } | |
| PVer *set(PArray *arr, PVer *ver, uint32_t index, uint32_t val) { | |
| assert(index < arr->capacity); | |
| reroot(arr, ver); | |
| PVer *new_ver = push_array(arr->arena, PVer, 1); | |
| arr->root = new_ver; | |
| ver->index = index; | |
| ver->value = arr->values[index]; | |
| arr->values[index] = val; | |
| ver->next = new_ver; | |
| return new_ver; | |
| } | |
| int main(int argc, char *argv) { | |
| PArray *arr = create(100); | |
| PVer *v0 = arr->root; | |
| PVer *v1 = set(arr, v0, 1, 7); | |
| PVer *v2 = set(arr, v1, 2, 8); | |
| PVer *v3 = set(arr, v1, 2, 9); | |
| PVer *v4 = set(arr, v2, 2, 10); | |
| uint32_t i0 = get(arr, v3, 2); | |
| assert(i0 == 9); | |
| uint32_t i1 = get(arr, v3, 1); | |
| assert(i1 == 7); | |
| uint32_t i2 = get(arr, v2, 2); | |
| assert(i2 == 8); | |
| uint32_t i3 = get(arr, v2, 1); | |
| assert(i3 == 7); | |
| uint32_t i4 = get(arr, v1, 1); | |
| assert(i4 == 7); | |
| uint32_t i5 = get(arr, v1, 2); | |
| assert(i5 == 0); | |
| uint32_t i6 = get(arr, v4, 1); | |
| assert(i6 == 7); | |
| uint32_t i7 = get(arr, v4, 2); | |
| assert(i7 == 10); | |
| uint32_t i8 = get(arr, v1, 1); | |
| assert(i8 == 7); | |
| uint32_t i9 = get(arr, v1, 2); | |
| assert(i9 == 0); | |
| return 0; | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment