aboutsummaryrefslogtreecommitdiff
path: root/composed.c
diff options
context:
space:
mode:
Diffstat (limited to 'composed.c')
-rw-r--r--composed.c76
1 files changed, 76 insertions, 0 deletions
diff --git a/composed.c b/composed.c
new file mode 100644
index 00000000..f969c8f1
--- /dev/null
+++ b/composed.c
@@ -0,0 +1,76 @@
+#include "composed.h"
+
+#include <stdlib.h>
+#include <stdbool.h>
+
+#include "debug.h"
+
+struct composed *
+composed_lookup(struct composed *root, uint32_t key)
+{
+ struct composed *node = root;
+
+ while (node != NULL) {
+ if (key == node->key)
+ return node;
+
+ node = key < node->key ? node->left : node->right;
+ }
+
+ return NULL;
+}
+
+uint32_t
+composed_insert(struct composed **root, struct composed *node)
+{
+ node->left = node->right = NULL;
+
+ if (*root == NULL) {
+ *root = node;
+ return node->key;
+ }
+
+ uint32_t key = node->key;
+
+ struct composed *prev = NULL;
+ struct composed *n = *root;
+
+ while (n != NULL) {
+ if (n->key == node->key) {
+ /* TODO: wrap around at (CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO) */
+ key++;
+ }
+
+ prev = n;
+ n = key < n->key ? n->left : n->right;
+ }
+
+ xassert(prev != NULL);
+ xassert(n == NULL);
+
+ /* May have been changed */
+ node->key = key;
+
+ if (key < prev->key) {
+ xassert(prev->left == NULL);
+ prev->left = node;
+ } else {
+ xassert(prev->right == NULL);
+ prev->right = node;
+ }
+
+ return key;
+}
+
+void
+composed_free(struct composed *root)
+{
+ if (root == NULL)
+ return;
+
+ composed_free(root->left);
+ composed_free(root->right);
+
+ free(root->chars);
+ free(root);
+}