From 815cde44e5060ad093347bb47fc66d41c9d3a3ed Mon Sep 17 00:00:00 2001
From: tslil clingman <tslil@posteo.de>
Date: Sun, 24 Jan 2021 12:07:18 -0500
Subject: Still trying |

---
 include/tt_treap.c | 150 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 150 insertions(+)
 create mode 100644 include/tt_treap.c

(limited to 'include/tt_treap.c')

diff --git a/include/tt_treap.c b/include/tt_treap.c
new file mode 100644
index 0000000..b48ffd4
--- /dev/null
+++ b/include/tt_treap.c
@@ -0,0 +1,150 @@
+#include "tt_treap.h"
+
+// ===================================================================
+// Variables
+// ===================================================================
+
+uint32_t tt_num_cached;
+static tt_entry_t * root;
+
+// ===================================================================
+// Helper declarations
+// ===================================================================
+
+void recurse_tree(tt_entry_t *n);
+tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
+													 const uint8_t depth, const float value);
+void bubble_up(tt_entry_t *n);
+
+// ===================================================================
+// Exported functions
+// ===================================================================
+
+int tt_init(void) {
+	root = NULL;
+	tt_num_cached = 0;
+	return EXIT_SUCCESS;
+}
+
+void tt_free(void) {
+	recurse_tree(root);
+	return;
+}
+
+tt_entry_t *tt_seek(const uint64_t key) {
+	if (root == NULL) return NULL;
+	tt_entry_t * n = root;
+
+	while (n != NULL && n->key != key) {
+		if (n->key > key) n = n->right;
+		else n = n->left;
+	}
+	return n;
+}
+
+int tt_insert(const uint64_t key, const enum TT_FLAG flag,
+										const uint8_t depth, const float value) {
+	tt_entry_t *m = new_treap_node(key, flag, depth, value);
+	if (root == NULL) {
+		root = m;
+		tt_num_cached = 1;
+		return EXIT_SUCCESS;
+	}
+	tt_entry_t *s = root, *n = root;
+	// Find the correct position by doing a BST traversal
+	while (n!=NULL) {
+		s = n;
+		if (n->key >= key) n = n->right;
+		else n = n->left;
+	}
+	// Make it a leaf
+	if (s->key > key) s->right = m;
+	else s->left = m;
+	m->parent = s;
+	// Now bubble upward to satisfy the heap property
+	bubble_up(m);
+	tt_num_cached++;
+	return EXIT_SUCCESS;
+}
+
+// ===================================================================
+// Helper implementations
+// ===================================================================
+
+void recurse_tree(tt_entry_t *n) {
+	if (n==NULL) return;
+	if (n->left != NULL) recurse_tree(n->left);
+	if (n->right != NULL) recurse_tree(n->right);
+	free(n);
+}
+
+tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
+													 const uint8_t depth, const float value) {
+	tt_entry_t *n = malloc(sizeof(struct treap_node_s));
+	// TODO: trap
+	n->key = key;
+	n->flag = flag;
+	n->depth = depth;
+	n->value = value;
+	n->left = NULL;
+	n->right = NULL;
+	n->parent = NULL;
+	XORSHIFT64; n->weight = RANDOM32;
+	return n;
+}
+
+void rotate_left(tt_entry_t *n) {
+	tt_entry_t *a = n->parent, *b = a->left, *c = n->left;
+	/*
+		We are the right child, so do this
+					 a           n
+					/ \         / \
+				 b   n  -->  a   d
+						/ \     / \
+					 c   d   b   c
+	*/
+	n->parent = a->parent;
+	// We may have to repair one level up as well
+	if (a->parent!=NULL) {
+		if (a->parent->left == a) a->parent->left = n;
+		else a->parent->right = n;
+	}
+	a->parent = n;
+	n->left = a; a->parent = n;
+	a->left = b; if (b!=NULL) b->parent = a;
+	a->right = c; if (c!=NULL) c->parent = a;
+}
+
+void rotate_right(tt_entry_t *n) {
+	tt_entry_t *a = n->parent, *b = a->right, *d = n->right;
+	 /*
+		 We are the left child, so do this
+				 a           n
+				/ \         / \
+			 n   b  -->  c   a
+			/ \             / \
+		 c   d           d   b
+	 */
+	n->parent = a->parent;
+	// We may have to repair one level up as well
+	if (a->parent!=NULL) {
+		if (a->parent->left == a) a->parent->left = n;
+		else a->parent->right = n;
+	}
+	a->parent = n;
+	n->right = a; a->parent = n;
+	a->left = d; if (d!=NULL) d->parent = a;
+	a->right = b; if (b!=NULL) b->parent = a;
+}
+
+//This preserves the BST quality of the treap
+void bubble_up(tt_entry_t *n) {
+	// Nothing to be done in this case
+	if (n==NULL || n->parent == NULL) return;
+	// Bubble until the treap invariants are satisfied
+	while (n->parent != NULL && n->weight < n->parent->weight) {
+		if (n->parent->left == n) rotate_right(n);
+		else rotate_left(n);
+	}
+	if (n->parent == NULL) root = n;
+}
-- 
cgit v1.2.3