1 files changed, 169 insertions, 0 deletions
diff --git a/ioreplay/src/datas/btree.c b/ioreplay/src/datas/btree.c
new file mode 100644
index 0000000..da5da48
--- /dev/null
+++ b/ioreplay/src/datas/btree.c
@@ -0,0 +1,169 @@
+// Copyright 2018 Mimecast Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "btree.h"
+
+btree_s* btree_new()
+{
+    btree_s *b = Malloc(btree_s);
+    *b = (btree_s) {
+        .root = NULL, .size = 0
+    };
+    return b;
+}
+
+void btree_destroy(btree_s* b)
+{
+    if (b->root)
+        btreelem_destroy_r(b->root);
+    free(b);
+}
+
+void btree_destroy2(btree_s* b)
+{
+    if (b->root)
+        btreelem_destroy_r2(b->root);
+    free(b);
+}
+
+int btree_insert(btree_s* b, int key, void *data)
+{
+    int ret = 1;
+
+    if (b->root == NULL) {
+        b->root = btreelem_new(key, data);
+        ret = 0;
+    } else {
+        ret = btreelem_insert_r(b->root, key, data);
+    }
+
+    if (ret == 0) {
+        b->size++;
+    }
+
+    return ret;
+}
+
+void* btree_get(btree_s* b, int key)
+{
+    if (b->root == NULL)
+        return NULL;
+
+    return btreelem_get_r(b->root, key);
+}
+
+void btree_print(btree_s* b)
+{
+    btreelem_print_r(b->root, 0);
+}
+
+btreelem_s* btreelem_new(int key, void *data)
+{
+    btreelem_s *e = Malloc(btreelem_s);
+    *e = (btreelem_s) {
+        .key = key, .data = data, .left = NULL, .right = NULL
+    };
+    return e;
+}
+
+void btreelem_destroy_r(btreelem_s* e)
+{
+    if (e->left) {
+        btreelem_destroy_r(e->left);
+    }
+    if (e->right) {
+        btreelem_destroy_r(e->right);
+    }
+
+    free(e);
+}
+
+void btreelem_destroy_r2(btreelem_s* e)
+{
+    if (e->left)
+        btreelem_destroy_r(e->left);
+    if (e->right)
+        btreelem_destroy_r(e->right);
+    if (e->data)
+        btree_destroy(e->data);
+
+    free(e);
+}
+
+int btreelem_insert_r(btreelem_s* e, int key, void *data)
+{
+    int ret = 0;
+
+    if (e->key == key) {
+        ret = 1;
+    }
+
+    else if (e->key > key) {
+        if (e->left == NULL) {
+            e->left = btreelem_new(key, data);
+        } else {
+            ret = btreelem_insert_r(e->left, key, data);
+        }
+    }
+
+    else {
+        if (e->right == NULL) {
+            e->right = btreelem_new(key, data);
+        } else {
+            ret = btreelem_insert_r(e->right, key, data);
+        }
+    }
+
+    return ret;
+}
+
+void* btreelem_get_r(btreelem_s* e, int key)
+{
+    void *data = NULL;
+
+    if (e->key == key) {
+        data = e->data;
+    }
+
+    else if (e->key > key) {
+        if (e->left) {
+            data = btreelem_get_r(e->left, key);
+        }
+    }
+
+    else {
+        if (e->right) {
+            data = btreelem_get_r(e->right, key);
+        }
+    }
+
+    return data;
+}
+
+void btreelem_print_r(btreelem_s* e, int depth)
+{
+    for (int i = 0; i < depth; ++i) {
+        Out(" ");
+    }
+    Put("%d\n", e->key);
+
+    if (e->left) {
+        btreelem_print_r(e->left, depth);
+    }
+
+    if (e->right) {
+        btreelem_print_r(e->right, depth+1);
+    }
+}
+