From f2c1beb5c3139238a3570d8f5052635519367d26 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Yaroslav=20de=20la=20Pe=C3=B1a=20Smirnov?= Date: Thu, 13 Oct 2022 01:13:12 +0300 Subject: Switch to vector + qsort instead of bst Doesn't improve perfomance that much (sorting is far from the hotspot), but I realized that I didn't really need a BST for this use-case and I felt dumb for using one :/ --- include/bstree.h | 68 -------------------------------------------------------- 1 file changed, 68 deletions(-) delete mode 100644 include/bstree.h (limited to 'include/bstree.h') diff --git a/include/bstree.h b/include/bstree.h deleted file mode 100644 index 9577b73..0000000 --- a/include/bstree.h +++ /dev/null @@ -1,68 +0,0 @@ -/* - * Copyright 2021 Yaroslav de la Peña Smirnov - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ -#ifndef BSTREE_H -#define BSTREE_H - -#include - -/* < 0 means a less than b; 0 means equal; > 0 means a more than b. */ -typedef int (*bst_cmp_fn)(const void *a, const void *b); -typedef void (*bst_free_fn)(void *data); - -struct bstree { - struct bstnode *root; - bst_cmp_fn cmp; - /* It can be NULL, in which case you will have to free the values manually */ - bst_free_fn free; -}; - -struct bstnode { - void *value; - struct bstnode *parent; - struct bstnode *left; - struct bstnode *right; -}; - -typedef bool (*bst_walk_cb)(struct bstnode *, void *data); - -struct bstree *bstree_new(bst_cmp_fn, bst_free_fn); - -struct bstnode *bstree_add(struct bstree *, void *val); - -/* Returns NULL if a node with the value wasn't found */ -struct bstnode *bstree_search(struct bstree *, void *val); - -struct bstnode *bstree_min(struct bstnode *); - -struct bstnode *bstree_max(struct bstnode *); - -struct bstnode *bstree_predecessor(struct bstnode *); - -struct bstnode *bstree_successor(struct bstnode *); - -bool bstree_inorder_walk(struct bstnode *, bst_walk_cb, void *data); - -void bstree_remove(struct bstree *, struct bstnode *); - -void bstree_destroy(struct bstree *); - -#endif -- cgit v1.2.3