aboutsummaryrefslogtreecommitdiff
path: root/advent-of-code/2022/lib
diff options
context:
space:
mode:
Diffstat (limited to 'advent-of-code/2022/lib')
-rw-r--r--advent-of-code/2022/lib/crc32.c55
-rw-r--r--advent-of-code/2022/lib/crc32.h9
-rw-r--r--advent-of-code/2022/lib/htable.c106
-rw-r--r--advent-of-code/2022/lib/htable.h29
-rw-r--r--advent-of-code/2022/lib/pque.c72
-rw-r--r--advent-of-code/2022/lib/pque.h18
-rw-r--r--advent-of-code/2022/lib/rbtree.c396
-rw-r--r--advent-of-code/2022/lib/rbtree.h59
-rw-r--r--advent-of-code/2022/lib/str.c130
-rw-r--r--advent-of-code/2022/lib/str.h24
10 files changed, 0 insertions, 898 deletions
diff --git a/advent-of-code/2022/lib/crc32.c b/advent-of-code/2022/lib/crc32.c
deleted file mode 100644
index c97a971..0000000
--- a/advent-of-code/2022/lib/crc32.c
+++ /dev/null
@@ -1,55 +0,0 @@
-#include "crc32.h"
-
-const uint32_t crc32_tab[] = {
- 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
- 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
- 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
- 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
- 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
- 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
- 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
- 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
- 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
- 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
- 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
- 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
- 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
- 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
- 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
- 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
- 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
- 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
- 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
- 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
- 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
- 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
- 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
- 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
- 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
- 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
- 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
- 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
- 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
- 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
- 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
- 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
- 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
- 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
- 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
- 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
- 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
- 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
- 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
- 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
- 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
- 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
- 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
-};
-
-uint32_t crc32(uint32_t crc, void *buf, int size){
- uint8_t *p = buf;
- crc = ~crc;
- while (size--)
- crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
- return ~crc;
-}
diff --git a/advent-of-code/2022/lib/crc32.h b/advent-of-code/2022/lib/crc32.h
deleted file mode 100644
index 86587f1..0000000
--- a/advent-of-code/2022/lib/crc32.h
+++ /dev/null
@@ -1,9 +0,0 @@
-#ifndef CRC32_H_
-#define CRC32_H_
-
-#include <stdint.h>
-
-uint32_t crc32(uint32_t r, void* buf, int size);
-
-#endif
-
diff --git a/advent-of-code/2022/lib/htable.c b/advent-of-code/2022/lib/htable.c
deleted file mode 100644
index d4b90a5..0000000
--- a/advent-of-code/2022/lib/htable.c
+++ /dev/null
@@ -1,106 +0,0 @@
-#include "htable.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-#define HTFL_NUL 0
-#define HTFL_VAL 1
-#define HTFL_DEL 2
-
-static void* htable_end(HTable *ht) {
- return ht->buf + ht->cap * (ht->elemsz + 1);
-}
-
-static void rebuild(HTable *ht) {
- HTable newht;
- htable_init(&newht, ht->elemsz, ht->size * 6, ht->hash, ht->eq);
- void *iter = htable_begin(ht);
- while (iter != NULL) {
- htable_insert(&newht, iter);
- iter = htable_next(ht, iter);
- }
- free(ht->buf);
- *ht = newht;
-}
-
-static uint8_t getflag(void *iter) {
- return *(uint8_t*)(iter - 1);
-}
-
-static void setflag(void *iter, uint8_t flag) {
- *(uint8_t *)(iter - 1) = flag;
-}
-
-void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void*),
- bool (*eq)(void*, void*)) {
- if (cap < 16) cap = 16;
- ht->buf = malloc(cap * (elemsz + 1));
- memset(ht->buf, 0, cap * (elemsz + 1));
- ht->size = 0;
- ht->cap = cap;
- ht->taken = 0;
- ht->begin = NULL;
- ht->elemsz = elemsz;
- ht->hash = hash;
- ht->eq = eq;
-}
-
-bool htable_insert(HTable *ht, void* elem) {
- if (ht->taken + 1 > ht->cap / 2) {
- rebuild(ht);
- }
- ht->taken++;
- ht->size++;
- int hashcode = ht->hash(elem) % ht->cap;
- void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
- while (getflag(pos) != HTFL_NUL) {
- if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return false;
- pos += ht->elemsz + 1;
- if (pos >= htable_end(ht)) { // arrived end, restart from beginning
- pos = ht->buf + 1;
- }
- }
- memcpy(pos, elem, ht->elemsz);
- setflag(pos, HTFL_VAL);
- if (pos < ht->begin || ht->begin == NULL) {
- ht->begin = pos;
- }
- return true;
-}
-
-void htable_del(HTable *ht, void* iter) {
- ht->size--;
- setflag(iter, HTFL_DEL);
- if (iter == ht->begin) {
- ht->begin = htable_next(ht, iter);
- }
-}
-
-void* htable_find(HTable *ht, void* elem) {
- int hashcode = ht->hash(elem) % ht->cap;
- void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
- while (getflag(pos) != HTFL_NUL) {
- if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return pos;
- pos += ht->elemsz + 1;
- if (pos >= htable_end(ht)) { // arrived end, restart from beginning
- pos = ht->buf + 1;
- }
- }
- return NULL;
-}
-
-void* htable_begin(HTable *ht) {
- return ht->begin;
-}
-
-void* htable_next(HTable *ht, void *iter) {
- void *pos = iter;
- do {
- pos += ht->elemsz + 1;
- if (pos >= htable_end(ht)) {
- return NULL;
- }
- } while (getflag(pos) != HTFL_VAL);
- return pos;
-}
-
diff --git a/advent-of-code/2022/lib/htable.h b/advent-of-code/2022/lib/htable.h
deleted file mode 100644
index 3bde74f..0000000
--- a/advent-of-code/2022/lib/htable.h
+++ /dev/null
@@ -1,29 +0,0 @@
-#ifndef HTABLE_H_
-#define HTABLE_H_
-
-#include <stdbool.h>
-#include <stdint.h>
-
-typedef struct {
- void *buf;
- int size;
- int cap;
- int taken;
- void* begin;
- int elemsz;
- uint32_t (*hash)(void*);
- bool (*eq)(void*, void*);
-} HTable;
-
-void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void*),
- bool (*eq)(void*, void*));
-bool htable_insert(HTable *ht, void* elem);
-void htable_del(HTable *ht, void* iter);
-
-// return a iterator
-void* htable_find(HTable *ht, void* elem);
-void* htable_begin(HTable *ht);
-void* htable_next(HTable *ht, void *iter);
-
-#endif
-
diff --git a/advent-of-code/2022/lib/pque.c b/advent-of-code/2022/lib/pque.c
deleted file mode 100644
index 0a9dbc0..0000000
--- a/advent-of-code/2022/lib/pque.c
+++ /dev/null
@@ -1,72 +0,0 @@
-#include "pque.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-void pq_init(PQue *pq, int cap, int elem_sz, int (*cmp)(void*, void*)) {
- pq->cap = cap;
- pq->size = 0;
- pq->elemsz = elem_sz;
- pq->cmp = cmp;
- pq->buf = malloc(cap * elem_sz);
-}
-
-static void swap(PQue *pq, int a, int b) {
- char buf[pq->elemsz];
- void *tmp = buf;
- int elemsz = pq->elemsz;
- memcpy(tmp, pq->buf + a*elemsz, elemsz);
- memcpy(pq->buf + a*elemsz, pq->buf + b*elemsz, elemsz);
- memcpy(pq->buf + b*elemsz, tmp, elemsz);
-}
-
-static int cmp(PQue *pq, int a, int b) {
- return pq->cmp(pq->buf + a*pq->elemsz, pq->buf + b*pq->elemsz);
-}
-
-void pq_push(PQue *pq, void *elem) {
- if (pq->size + 1 > pq->cap) {
- pq->buf = realloc(pq->buf, 2 * pq->cap * pq->elemsz);
- pq->cap *= 2;
- }
- memcpy(pq->buf + pq->size*pq->elemsz, elem, pq->elemsz);
- pq->size++;
- if (pq->size == 0) {
- return;
- }
- int i = pq->size - 1;
- while (i > 0 && cmp(pq, i, i/2) > 0) {
- swap(pq, i, i/2);
- i /= 2;
- }
-}
-
-static void heapify(PQue *pq, int idx) {
- int left, right, largest;
- left = 2 * idx +1;
- right = 2 * idx + 2;
- if (left < pq->size && cmp(pq, left, idx) > 0) {
- largest = left;
- } else {
- largest = idx;
- }
- if (right < pq->size && cmp(pq, right, largest) > 0) {
- largest = right;
- }
- if (largest != idx) {
- swap(pq, largest, idx);
- heapify(pq, largest);
- }
-}
-
-void pq_pop(PQue *pq) {
- if (pq->size == 0) return;
- memcpy(pq->buf, pq->buf+(pq->size - 1)*pq->elemsz, pq->elemsz);
- pq->size -= 1;
- heapify(pq, 0);
-}
-
-void* pq_top(PQue *pq) {
- if (pq->size == 0) return NULL;
- return pq->buf;
-}
diff --git a/advent-of-code/2022/lib/pque.h b/advent-of-code/2022/lib/pque.h
deleted file mode 100644
index 0d86560..0000000
--- a/advent-of-code/2022/lib/pque.h
+++ /dev/null
@@ -1,18 +0,0 @@
-#ifndef PQUEUE_H_
-#define PQUEUE_H_
-
-typedef struct {
- void *buf;
- int elemsz;
- int cap;
- int size;
- int (*cmp)(void*, void*);
-} PQue;
-
-void pq_init(PQue *pq, int cap, int elemsz, int (*cmp)(void*, void*));
-void pq_push(PQue *pq, void *elem);
-void pq_pop(PQue *pq);
-void* pq_top();
-
-#endif
-
diff --git a/advent-of-code/2022/lib/rbtree.c b/advent-of-code/2022/lib/rbtree.c
deleted file mode 100644
index 25a951b..0000000
--- a/advent-of-code/2022/lib/rbtree.c
+++ /dev/null
@@ -1,396 +0,0 @@
-/* $OpenBSD: tree.h,v 1.30 2020/10/10 18:03:41 otto Exp $ */
-/*
- * Copyright 2002 Niels Provos <provos@citi.umich.edu>
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include "rbtree.h"
-
-#define RED 1
-#define BLACK 0
-
-static struct rbnode *rbtree_minmax(struct rbtree *, int);
-void* rbtree_min(struct rbtree *head) {
- return rbtree_minmax(head, -1);
-}
-void* rbtree_max(struct rbtree *head) {
- return rbtree_minmax(head, 1);
-}
-
-void* rbtree_left(void *node) {
- struct rbnode *elm = node;
- if (node == NULL) return NULL;
- return elm->entry.rbe_left;
-}
-void* rbtree_right(void *node) {
- struct rbnode *elm = node;
- if (node == NULL) return NULL;
- return elm->entry.rbe_right;
-}
-void* rbtree_parent(void *node) {
- struct rbnode *elm = node;
- if (node == NULL) return NULL;
- return elm->entry.rbe_parent;
-}
-
-static void augment(struct rbtree * head, struct rbnode *elm) {
- if (head->augment != NULL) head->augment(elm);
-}
-
-static void rbtree_insert_color(struct rbtree *head, struct rbnode *elm);
-static void rbtree_remove_color(struct rbtree *head, struct rbnode *parent,
- struct rbnode *elm);
-
-static void rotate_left(struct rbtree *head, struct rbnode *elm) {
- struct rbnode *tmp = elm->entry.rbe_right;
- if ((elm->entry.rbe_right = tmp->entry.rbe_left)) {
- tmp->entry.rbe_left->entry.rbe_parent = elm;
- }
- augment(head, elm);
- if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) {
- if (elm == elm->entry.rbe_parent->entry.rbe_left)
- elm->entry.rbe_parent->entry.rbe_left = tmp;
- else
- elm->entry.rbe_parent->entry.rbe_right = tmp;
- } else {
- head->rbh_root = tmp;
- }
- tmp->entry.rbe_left = elm;
- elm->entry.rbe_parent = tmp;
- augment(head, tmp);
- if (tmp->entry.rbe_parent) {
- augment(head, tmp->entry.rbe_parent);
- }
-}
-
-static void rotate_right(struct rbtree *head, struct rbnode *elm) {
- struct rbnode *tmp = elm->entry.rbe_left;
- if ((elm->entry.rbe_left = tmp->entry.rbe_right)) {
- tmp->entry.rbe_right->entry.rbe_parent = elm;
- }
- augment(head, elm);
- if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) {
- if (elm == elm->entry.rbe_parent->entry.rbe_left)
- elm->entry.rbe_parent->entry.rbe_left = tmp;
- else
- elm->entry.rbe_parent->entry.rbe_right = tmp;
- } else {
- head->rbh_root = tmp;
- }
- tmp->entry.rbe_right = elm;
- elm->entry.rbe_parent = tmp;
- augment(head, tmp);
- if (tmp->entry.rbe_parent) {
- augment(head, tmp->entry.rbe_parent);
- }
-}
-
-static void rbtree_insert_color(struct rbtree *head, struct rbnode *elm) {
- struct rbnode *parent, *gparent, *tmp;
- while ((parent = elm->entry.rbe_parent) && parent->entry.rbe_color == 1) {
- gparent = parent->entry.rbe_parent;
- if (parent == gparent->entry.rbe_left) {
- tmp = gparent->entry.rbe_right;
- if (tmp && tmp->entry.rbe_color == 1) {
- tmp->entry.rbe_color = BLACK;
- parent->entry.rbe_color = BLACK;
- gparent->entry.rbe_color = RED;
- elm = gparent;
- continue;
- }
- if (parent->entry.rbe_right == elm) {
- rotate_left(head, parent);
- tmp = parent;
- parent = elm;
- elm = tmp;
- }
- parent->entry.rbe_color = BLACK;
- gparent->entry.rbe_color = RED;
- rotate_right(head, gparent);
- } else {
- tmp = gparent->entry.rbe_left;
- if (tmp && tmp->entry.rbe_color == 1) {
- tmp->entry.rbe_color = BLACK;
- parent->entry.rbe_color = BLACK;
- gparent->entry.rbe_color = RED;;
- elm = gparent;
- continue;
- }
- if (parent->entry.rbe_left == elm) {
- rotate_right(head, parent);
- tmp = parent;
- parent = elm;
- elm = tmp;
- }
- parent->entry.rbe_color = BLACK;
- gparent->entry.rbe_color = RED;
- rotate_left(head, gparent);
- }
- }
- head->rbh_root->entry.rbe_color = BLACK;
-}
-
-static void rbtree_remove_color(struct rbtree *head, struct rbnode *parent,
- struct rbnode *elm) {
- struct rbnode *tmp;
- while ((elm == NULL || elm->entry.rbe_color == 0) &&
- elm != head->rbh_root) {
- if (parent->entry.rbe_left == elm) {
- tmp = parent->entry.rbe_right;
- if (tmp->entry.rbe_color == 1) {
- tmp->entry.rbe_color = BLACK;
- parent->entry.rbe_color = RED;
- rotate_left(head, parent);
- tmp = parent->entry.rbe_right;
- }
- if ((tmp->entry.rbe_left == NULL ||
- tmp->entry.rbe_left->entry.rbe_color == 0) &&
- (tmp->entry.rbe_right == NULL ||
- tmp->entry.rbe_right->entry.rbe_color == 0)) {
- tmp->entry.rbe_color = RED;
- elm = parent;
- parent = elm->entry.rbe_parent;
- } else {
- if (tmp->entry.rbe_right == NULL ||
- tmp->entry.rbe_right->entry.rbe_color == 0) {
- struct rbnode *oleft;
- if ((oleft = tmp->entry.rbe_left))
- oleft->entry.rbe_color = BLACK;
- tmp->entry.rbe_color = RED;
- rotate_right(head, tmp);
- tmp = parent->entry.rbe_right;
- }
- tmp->entry.rbe_color = parent->entry.rbe_color;
- parent->entry.rbe_color = BLACK;
- if (tmp->entry.rbe_right)
- tmp->entry.rbe_right->entry.rbe_color = BLACK;
- rotate_left(head, parent);
- elm = head->rbh_root;
- break;
- }
- } else {
- tmp = parent->entry.rbe_left;
- if (tmp->entry.rbe_color == 1) {
- tmp->entry.rbe_color = BLACK;
- parent->entry.rbe_color = RED;
- rotate_right(head, parent);
- tmp = parent->entry.rbe_left;
- }
- if ((tmp->entry.rbe_left == NULL ||
- tmp->entry.rbe_left->entry.rbe_color == 0) &&
- (tmp->entry.rbe_right == NULL ||
- tmp->entry.rbe_right->entry.rbe_color == 0)) {
- tmp->entry.rbe_color = RED;
- elm = parent;
- parent = elm->entry.rbe_parent;
- } else {
- if (tmp->entry.rbe_left == NULL ||
- tmp->entry.rbe_left->entry.rbe_color == 0) {
- struct rbnode *oright;
- if ((oright = tmp->entry.rbe_right))
- oright->entry.rbe_color = BLACK;
- tmp->entry.rbe_color = RED;
- rotate_left(head, tmp);
- tmp = parent->entry.rbe_left;
- }
- tmp->entry.rbe_color = parent->entry.rbe_color;
- parent->entry.rbe_color = BLACK;
- if (tmp->entry.rbe_left)
- tmp->entry.rbe_left->entry.rbe_color = BLACK;
- rotate_right(head, parent);
- elm = head->rbh_root;
- break;
- }
- }
- }
- if (elm)
- elm->entry.rbe_color = BLACK;
-}
-
-void rbtree_remove(struct rbtree *head, void* elmv) {
- struct rbnode *elm = elmv;
- struct rbnode *child, *parent;
- int color;
- if (elm->entry.rbe_left == NULL)
- child = elm->entry.rbe_right;
- else if (elm->entry.rbe_right == NULL)
- child = elm->entry.rbe_left;
- else {
- struct rbnode *old = elm, *left;
- elm = elm->entry.rbe_right;
- while ((left = elm->entry.rbe_left))
- elm = left;
- child = elm->entry.rbe_right;
- parent = elm->entry.rbe_parent;
- color = elm->entry.rbe_color;
- if (child)
- child->entry.rbe_parent = parent;
- if (parent) {
- if (parent->entry.rbe_left == elm)
- parent->entry.rbe_left = child;
- else
- parent->entry.rbe_right = child;
- augment(head, parent);
- } else
- head->rbh_root = child;
- if (elm->entry.rbe_parent == old)
- parent = elm;
- elm->entry = old->entry;
- if (old->entry.rbe_parent) {
- if ((old->entry.rbe_parent)->entry.rbe_left == old)
- (old->entry.rbe_parent)->entry.rbe_left = elm;
- else
- (old->entry.rbe_parent)->entry.rbe_right = elm;
- augment(head, old->entry.rbe_parent);
- } else
- head->rbh_root = elm;
- old->entry.rbe_left->entry.rbe_parent = elm;
- if (old->entry.rbe_right)
- old->entry.rbe_right->entry.rbe_parent = elm;
- if (parent) {
- left = parent;
- if (head->augment != NULL) {
- do {
- augment(head, left);
- } while ((left = left->entry.rbe_parent));
- }
- }
- goto color;
- }
- parent = elm->entry.rbe_parent;
- color = elm->entry.rbe_color;
- if (child)
- child->entry.rbe_parent = parent;
- if (parent) {
- if (parent->entry.rbe_left == elm)
- parent->entry.rbe_left = child;
- else
- parent->entry.rbe_right = child;
- struct rbnode* goback = parent;
- if (head->augment != NULL) {
- do {
- augment(head, goback);
- } while ((goback = goback->entry.rbe_parent));
- }
- } else
- head->rbh_root = child;
-color:
- if (color == 0)
- rbtree_remove_color(head, parent, child);
-}
-
-void* rbtree_insert(struct rbtree *head, void *elmv) {
- struct rbnode *elm = elmv;
- struct rbnode *tmp;
- struct rbnode *parent = NULL;
- int comp = 0;
- tmp = head->rbh_root;
- while (tmp) {
- parent = tmp;
- comp = head->cmp((void*)elm->content, (void*)parent->content);
- if (comp < 0)
- tmp = tmp->entry.rbe_left;
- else if (comp > 0)
- tmp = tmp->entry.rbe_right;
- else
- return tmp;
- }
- elm->entry.rbe_parent = parent;
- elm->entry.rbe_left = elm->entry.rbe_right = NULL;
- elm->entry.rbe_color = RED;
- if (parent != NULL) {
- if (comp < 0)
- parent->entry.rbe_left = elm;
- else
- parent->entry.rbe_right = elm;
- struct rbnode* goback = parent;
- if (head->augment != NULL) {
- do {
- augment(head, goback);
- } while ((goback = goback->entry.rbe_parent));
- }
- } else
- head->rbh_root = elm;
- rbtree_insert_color(head, elm);
- return (NULL);
-}
-
-void* rbtree_find(struct rbtree *head, void *key) {
- struct rbnode *tmp = head->rbh_root;
- int comp;
- while (tmp) {
- comp = head->cmp(key, (void*)tmp->content);
- if (comp < 0)
- tmp = tmp->entry.rbe_left;
- else if (comp > 0)
- tmp = tmp->entry.rbe_right;
- else
- return tmp;
- }
- return (NULL);
-}
-
-void* rbtree_next(struct rbtree *head, void *elmv) {
- struct rbnode *elm = elmv;
- if (elm->entry.rbe_right) {
- elm = elm->entry.rbe_right;
- while (elm->entry.rbe_left)
- elm = elm->entry.rbe_left;
- } else {
- if (elm->entry.rbe_parent &&
- (elm == (elm->entry.rbe_parent)->entry.rbe_left))
- elm = elm->entry.rbe_parent;
- else {
- while (elm->entry.rbe_parent &&
- (elm == (elm->entry.rbe_parent)->entry.rbe_right))
- elm = elm->entry.rbe_parent;
- elm = elm->entry.rbe_parent;
- }
- }
- return elm;
-}
-
-static struct rbnode *rbtree_minmax(struct rbtree *head, int val) {
- struct rbnode *tmp = head->rbh_root;
- struct rbnode *parent = NULL;
- while (tmp) {
- parent = tmp;
- if (val < 0)
- tmp = tmp->entry.rbe_left;
- else
- tmp = tmp->entry.rbe_right;
- }
- return parent;
-};
-
-static void rbtree_free_impl(struct rbnode *node, void (*free_cb)(void*)) {
- if (node == NULL) return;
- if (free_cb != NULL) free_cb(node->content);
- rbtree_free_impl(node->entry.rbe_left, free_cb);
- rbtree_free_impl(node->entry.rbe_right, free_cb);
- free(node);
-}
-
-void rbtree_free(struct rbtree *head, void (*free_cb)(void*)) {
- rbtree_free_impl(head->rbh_root, free_cb);
-}
diff --git a/advent-of-code/2022/lib/rbtree.h b/advent-of-code/2022/lib/rbtree.h
deleted file mode 100644
index 4255e84..0000000
--- a/advent-of-code/2022/lib/rbtree.h
+++ /dev/null
@@ -1,59 +0,0 @@
-/*
- * Copyright 2002 Niels Provos <provos@citi.umich.edu>
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include <stdlib.h>
-
-struct rbnode {
- struct {
- struct rbnode *rbe_left;
- struct rbnode *rbe_right;
- struct rbnode *rbe_parent;
- int rbe_color;
- } entry;
- char content[0];
-};
-
-struct rbtree {
- struct rbnode *rbh_root;
- int (*cmp)(void *k1, void *k2);
- void (*augment)(void *elm);
-};
-
-typedef struct rbnode RbNode;
-typedef struct rbtree RbTree;
-
-void rbtree_remove(struct rbtree *, void* iter);
-
-// return a iterator
-void* rbtree_insert(struct rbtree *, void *treenode);
-void* rbtree_find(struct rbtree *, void *val);
-void* rbtree_next(struct rbtree *, void* iter);
-void* rbtree_min(struct rbtree *);
-void* rbtree_max(struct rbtree *);
-void* rbtree_left(void *node);
-void* rbtree_right(void *node);
-void* rbtree_parent(void *node);
-
-void rbtree_free(struct rbtree *, void (*free_cb)(void*));
diff --git a/advent-of-code/2022/lib/str.c b/advent-of-code/2022/lib/str.c
deleted file mode 100644
index 16968a2..0000000
--- a/advent-of-code/2022/lib/str.c
+++ /dev/null
@@ -1,130 +0,0 @@
-#include "str.h"
-
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-#include <stddef.h>
-#include <stdbool.h>
-#include <stdarg.h>
-#include <ctype.h>
-
-char** str_split(char *str, char delim) {
- char **ret;
-
- if (str == NULL) return NULL;
- if (*str == '\n') {
- ret = malloc(sizeof(char*));
- *ret = NULL;
- return ret;
- }
- int count = 0;
- char *begin = str;
- for (char *p = str; *p != '\0'; p++) {
- if (*p != delim && !(delim == '\0' && isspace(*p))) {
- continue;
- }
- int size = p - begin;
- if (size > 0) count++;
- }
- count++;
- ret = malloc((count + 1) * sizeof(char*));
- memset(ret, 0, (count + 1) * sizeof(char*));
-
- begin = str;
- int i = 0;
- bool finished = false;
- for (char *p = str; !finished; p++) {
- if (*p == '\0') finished = true;
- if (*p != delim && *p != '\0' && !(delim == '\0' && isspace(*p))) {
- continue;
- }
- int size = p - begin;
- if (size == 0) {
- begin = p + 1;
- continue;
- }
- char *buf = malloc(sizeof(char) * (size + 1));
- buf[size] = '\0';
- memcpy(buf, begin, size * sizeof(char));
- begin = p + 1;
- ret[i] = buf;
- i++;
- }
- return ret;
-}
-
-void str_list_free(char **list) {
- char **p = list;
- while (*p != NULL) {
- free(*p);
- p++;
- }
- free(list);
-}
-
-char* str_strip(char *str) {
- int len = strlen(str);
- char *begin = str;
- char *end = str + len - 1;
- while (isspace(*begin) && begin < end) {
- begin++;
- }
- while (isspace(*end) && end >= begin) {
- end--;
- }
- len = end - begin + 1;
- char *buf = malloc(sizeof(char) * (len) + 1);
- buf[len] = '\0';
- memcpy(buf, begin, len);
- return buf;
-}
-
-void sb_init(StrBuilder *sb) {
- *sb = (StrBuilder){.size = 0, .cap = 16};
- sb->buf = malloc(sizeof(char) * 17);
-}
-
-static void sb_reserve(StrBuilder *sb, int extra) {
- if (sb->size + extra <= sb->cap) {
- return;
- }
- int new_cap = (sb->size + extra) * 2;
- sb->buf = realloc(sb->buf, new_cap + 1);
- memset(sb->buf + sb->cap, 0, new_cap - sb->cap + 1);
- sb->cap = new_cap;
-}
-
-void sb_append(StrBuilder *sb, char *format, ...) {
- va_list va1;
- va_list va2;
- va_start(va1, format);
- va_copy(va2, va1);
- int size = vsnprintf(NULL, 0, format, va1);
- sb_reserve(sb, size);
- vsnprintf(sb->buf + sb->size, sb->cap - sb->size + 1, format, va2);
-}
-
-void sb_appendc(StrBuilder *sb, char c) {
- sb_reserve(sb, 1);
- sb->buf[sb->size] = c;
- sb->size++;
-}
-
-char* fgetline(FILE *fp) {
- StrBuilder sb;
- sb_init(&sb);
- while (true) {
- int c = fgetc(fp);
- if (c == EOF && sb.size == 0) return NULL;
- if (c != EOF) sb_appendc(&sb, c);
- if (c == EOF || c == '\n') return sb.buf;
- }
- return NULL;
-}
-
-int fpeek(FILE *fp) {
- int c = fgetc(fp);
- if (c == EOF) return c;
- ungetc(c, fp);
- return c;
-}
diff --git a/advent-of-code/2022/lib/str.h b/advent-of-code/2022/lib/str.h
deleted file mode 100644
index 414adaa..0000000
--- a/advent-of-code/2022/lib/str.h
+++ /dev/null
@@ -1,24 +0,0 @@
-#ifndef NEBUTIL_STR_H_
-#define NEBUTIL_STR_H_
-
-#include <stdio.h>
-
-char* str_strip(char *str);
-char** str_split(char *str, char delim);
-void str_list_free(char **list);
-
-typedef struct {
- char *buf;
- int size;
- int cap;
-} StrBuilder;
-
-void sb_init(StrBuilder *sb);
-void sb_append(StrBuilder *sb, char *format, ...);
-void sb_appendc(StrBuilder *sb, char c);
-
-char* fgetline(FILE* fp);
-int fpeek(FILE *fp);
-
-#endif
-
generated by cgit v1.0 at 2025-12-29 19:36:21 +0000