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, 898 insertions, 0 deletions
diff --git a/advent-of-code/2022/lib/crc32.c b/advent-of-code/2022/lib/crc32.c
new file mode 100644
index 0000000..c97a971
--- /dev/null
+++ b/advent-of-code/2022/lib/crc32.c
@@ -0,0 +1,55 @@
+#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
new file mode 100644
index 0000000..86587f1
--- /dev/null
+++ b/advent-of-code/2022/lib/crc32.h
@@ -0,0 +1,9 @@
+#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
new file mode 100644
index 0000000..d4b90a5
--- /dev/null
+++ b/advent-of-code/2022/lib/htable.c
@@ -0,0 +1,106 @@
+#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
new file mode 100644
index 0000000..3bde74f
--- /dev/null
+++ b/advent-of-code/2022/lib/htable.h
@@ -0,0 +1,29 @@
+#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
new file mode 100644
index 0000000..0a9dbc0
--- /dev/null
+++ b/advent-of-code/2022/lib/pque.c
@@ -0,0 +1,72 @@
+#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
new file mode 100644
index 0000000..0d86560
--- /dev/null
+++ b/advent-of-code/2022/lib/pque.h
@@ -0,0 +1,18 @@
+#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
new file mode 100644
index 0000000..25a951b
--- /dev/null
+++ b/advent-of-code/2022/lib/rbtree.c
@@ -0,0 +1,396 @@
+/* $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
new file mode 100644
index 0000000..4255e84
--- /dev/null
+++ b/advent-of-code/2022/lib/rbtree.h
@@ -0,0 +1,59 @@
+/*
+ * 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
new file mode 100644
index 0000000..16968a2
--- /dev/null
+++ b/advent-of-code/2022/lib/str.c
@@ -0,0 +1,130 @@
+#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
new file mode 100644
index 0000000..414adaa
--- /dev/null
+++ b/advent-of-code/2022/lib/str.h
@@ -0,0 +1,24 @@
+#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 17:54:53 +0000