commit f5ff2b2337e0f2913f8ddaf3da7440f2e8c3a8a4
Author: Matthias Balk <mbalk@mbalk.de>
Date: Tue, 28 Jan 2020 21:51:32 +0100
Initial Commit
Diffstat:
| A | LICENSE | | | 26 | ++++++++++++++++++++++++++ |
| A | Makefile | | | 10 | ++++++++++ |
| A | btree.c | | | 103 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | btree.h | | | 28 | ++++++++++++++++++++++++++++ |
| A | btreetest.c | | | 38 | ++++++++++++++++++++++++++++++++++++++ |
| A | gencoupons.c | | | 64 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
6 files changed, 269 insertions(+), 0 deletions(-)
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,26 @@
+Copyright 2020 Matthias Balk
+
+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.
+
+3. Neither the name of the copyright holder nor the names of its contributors
+may be used to endorse or promote products derived from this software without
+specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 COPYRIGHT HOLDER OR CONTRIBUTORS 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.
diff --git a/Makefile b/Makefile
@@ -0,0 +1,10 @@
+all: btreetest gencoupons
+
+btreetest: btree.c btreetest.c
+ gcc -o btreetest btree.c btreetest.c
+
+gencoupons: btree.c gencoupons.c
+ gcc -o gencoupons btree.c gencoupons.c
+
+clean:
+ rm gencoupons btreetest
diff --git a/btree.c b/btree.c
@@ -0,0 +1,103 @@
+/**
+ * btree -- a balk tree implementation ;-)
+ * Copyright 2020 Matthias Balk
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "btree.h"
+
+
+u_int8_t bt_contains(node_t *tree, const char *data)
+{
+ int cmp = strcmp(data, tree->data);
+ if (cmp == 0)
+ return 1;
+
+ if (cmp > 0)
+ return tree->rchild ? bt_contains(tree->rchild, data) : 0;
+ else
+ return tree->lchild ? bt_contains(tree->lchild, data) : 0;
+}
+
+
+node_t* bt_new()
+{
+ node_t *tree = (node_t*) malloc(sizeof(node_t));
+ if (tree == NULL)
+ return NULL;
+
+ bzero(tree, sizeof(node_t));
+
+ return tree;
+}
+
+
+void bt_free(node_t *tree)
+{
+ if (tree->lchild != NULL)
+ {
+ bt_free(tree->lchild);
+ }
+
+ if (tree->rchild != NULL)
+ {
+ bt_free(tree->rchild);
+ }
+
+ free(tree);
+}
+
+
+void bt_free_incl_data(node_t *tree)
+{
+ free(tree->data);
+ bt_free(tree);
+}
+
+
+u_int8_t bt_add(node_t *tree, char *data)
+{
+ if (tree->data == NULL)
+ {
+ tree->data = data;
+ return 1;
+ }
+
+ int cmp = strcmp(data, tree->data);
+
+ if (cmp == 0)
+ return 0;
+
+ if (cmp > 0)
+ {
+ if (tree->rchild == NULL)
+ {
+ if ((tree->rchild = bt_new()) == NULL)
+ exit(EXIT_FAILURE); /* TODO: proper shutdown */
+ }
+ return bt_add(tree->rchild, data);
+ }
+ else
+ {
+ if (tree->lchild == NULL)
+ {
+ if ((tree->lchild = bt_new()) == NULL)
+ exit(EXIT_FAILURE); /* TODO: proper shutdown */
+ }
+ return bt_add(tree->lchild, data);
+ }
+}
+
+
+void bt_print_sorted(const node_t *tree)
+{
+ if (tree == NULL)
+ return;
+
+ bt_print_sorted(tree->lchild);
+ printf("%s\n", tree->data);
+ bt_print_sorted(tree->rchild);
+}
diff --git a/btree.h b/btree.h
@@ -0,0 +1,28 @@
+/**
+ * btree -- a balk tree implementation ;-)
+ * Copyright 2020 Matthias Balk
+ */
+
+#ifndef BTREE_H
+#define BTREE_H
+
+#include <stdlib.h>
+
+typedef struct node
+{
+ char *data;
+ void *lchild;
+ void *rchild;
+} node_t;
+
+
+node_t* bt_new();
+void bt_free(node_t *tree);
+void bt_free_incl_data(node_t *tree);
+
+u_int8_t bt_add(node_t *tree, char *data);
+u_int8_t bt_contains(node_t *tree, const char *data);
+
+void bt_print_sorted(const node_t *tree);
+
+#endif /* BTREE_H */
diff --git a/btreetest.c b/btreetest.c
@@ -0,0 +1,38 @@
+/**
+ * btree -- a balk tree implementation ;-)
+ * Copyright 2020 Matthias Balk
+ */
+
+#include "btree.h"
+
+
+int main(int argc, char **argv)
+{
+ node_t *root;
+ if ((root = bt_new()) == NULL)
+ exit(EXIT_FAILURE);
+
+ /**
+ * M
+ * / \
+ * D Q
+ * / / \
+ * C N X
+ * \
+ * O
+ */
+ bt_add(root, "M");
+ bt_add(root, "Q");
+ bt_add(root, "N");
+ bt_add(root, "D");
+ bt_add(root, "X");
+ bt_add(root, "C");
+ bt_add(root, "O");
+ bt_add(root, "Q");
+
+ bt_print_sorted(root);
+
+ bt_free(root);
+
+ return EXIT_SUCCESS;
+}
diff --git a/gencoupons.c b/gencoupons.c
@@ -0,0 +1,64 @@
+/**
+ * btree -- a balk tree implementation ;-)
+ * Copyright 2020 Matthias Balk
+ *
+ * Example program that generates random codes and uses `btree` to store and
+ * sort them.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#include "btree.h"
+
+
+#define SYMBOLS "ABCDEFGHKLMNPQRSTUVWXYZ123456789"
+#define CODELEN 8
+
+
+int main(int argc, char **argv)
+{
+ node_t *root;
+ if ((root = bt_new()) == NULL)
+ return EXIT_FAILURE;
+
+ srand(time(NULL));
+
+ int symbols_cnt = strlen(SYMBOLS);
+ int duplicate_cnt = 0;
+ int i = 0;
+ while (i < 13000000)
+ {
+ char* code = malloc((CODELEN + 1) * sizeof(char));
+ if (code == NULL)
+ {
+ perror("malloc");
+ return EXIT_FAILURE;
+ }
+
+ for (int j = 0; j < CODELEN; j++)
+ {
+ code[j] = SYMBOLS[rand() % symbols_cnt];
+ }
+ code[CODELEN] = '\0';
+
+ /* code already exists */
+ if (!bt_add(root, code)) {
+ free(code);
+ duplicate_cnt++;
+ }
+ else
+ {
+ i++;
+ }
+ }
+
+ bt_print_sorted(root);
+ printf("\nDuplicates: %d\n", duplicate_cnt);
+
+ bt_free_incl_data(root);
+
+ return EXIT_SUCCESS;
+}
