summaryrefslogtreecommitdiffstats
path: root/src/zix
diff options
context:
space:
mode:
Diffstat (limited to 'src/zix')
-rw-r--r--src/zix/common.h54
-rw-r--r--src/zix/tree.c991
-rw-r--r--src/zix/tree.h24
3 files changed, 537 insertions, 532 deletions
diff --git a/src/zix/common.h b/src/zix/common.h
index 32019e9..730a450 100644
--- a/src/zix/common.h
+++ b/src/zix/common.h
@@ -24,42 +24,42 @@
/** @cond */
#ifdef ZIX_SHARED
-# ifdef _WIN32
-# define ZIX_LIB_IMPORT __declspec(dllimport)
-# define ZIX_LIB_EXPORT __declspec(dllexport)
-# else
-# define ZIX_LIB_IMPORT __attribute__((visibility("default")))
-# define ZIX_LIB_EXPORT __attribute__((visibility("default")))
-# endif
-# ifdef ZIX_INTERNAL
-# define ZIX_API ZIX_LIB_EXPORT
-# else
-# define ZIX_API ZIX_LIB_IMPORT
-# endif
-# define ZIX_PRIVATE static
+# ifdef _WIN32
+# define ZIX_LIB_IMPORT __declspec(dllimport)
+# define ZIX_LIB_EXPORT __declspec(dllexport)
+# else
+# define ZIX_LIB_IMPORT __attribute__((visibility("default")))
+# define ZIX_LIB_EXPORT __attribute__((visibility("default")))
+# endif
+# ifdef ZIX_INTERNAL
+# define ZIX_API ZIX_LIB_EXPORT
+# else
+# define ZIX_API ZIX_LIB_IMPORT
+# endif
+# define ZIX_PRIVATE static
#elif defined(ZIX_INLINE)
-# define ZIX_API static inline
-# define ZIX_PRIVATE static inline
+# define ZIX_API static inline
+# define ZIX_PRIVATE static inline
#else
-# define ZIX_API
-# define ZIX_PRIVATE static
+# define ZIX_API
+# define ZIX_PRIVATE static
#endif
/** @endcond */
#ifdef __cplusplus
extern "C" {
#else
-# include <stdbool.h>
+# include <stdbool.h>
#endif
typedef enum {
- ZIX_STATUS_SUCCESS,
- ZIX_STATUS_ERROR,
- ZIX_STATUS_NO_MEM,
- ZIX_STATUS_NOT_FOUND,
- ZIX_STATUS_EXISTS,
- ZIX_STATUS_BAD_ARG,
- ZIX_STATUS_BAD_PERMS
+ ZIX_STATUS_SUCCESS,
+ ZIX_STATUS_ERROR,
+ ZIX_STATUS_NO_MEM,
+ ZIX_STATUS_NOT_FOUND,
+ ZIX_STATUS_EXISTS,
+ ZIX_STATUS_BAD_ARG,
+ ZIX_STATUS_BAD_PERMS
} ZixStatus;
/**
@@ -82,7 +82,7 @@ typedef void (*ZixDestroyFunc)(void* ptr);
*/
#ifdef __cplusplus
-} /* extern "C" */
+} /* extern "C" */
#endif
-#endif /* ZIX_COMMON_H */
+#endif /* ZIX_COMMON_H */
diff --git a/src/zix/tree.c b/src/zix/tree.c
index 15cea9a..a12d411 100644
--- a/src/zix/tree.c
+++ b/src/zix/tree.c
@@ -14,8 +14,8 @@
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
-#include "zix/common.h"
#include "zix/tree.h"
+#include "zix/common.h"
#include <assert.h>
#include <stdint.h>
@@ -25,20 +25,20 @@
typedef struct ZixTreeNodeImpl ZixTreeNode;
struct ZixTreeImpl {
- ZixTreeNode* root;
- ZixDestroyFunc destroy;
- ZixComparator cmp;
- void* cmp_data;
- size_t size;
- bool allow_duplicates;
+ ZixTreeNode* root;
+ ZixDestroyFunc destroy;
+ ZixComparator cmp;
+ void* cmp_data;
+ size_t size;
+ bool allow_duplicates;
};
struct ZixTreeNodeImpl {
- void* data;
- struct ZixTreeNodeImpl* left;
- struct ZixTreeNodeImpl* right;
- struct ZixTreeNodeImpl* parent;
- int_fast8_t balance;
+ void* data;
+ struct ZixTreeNodeImpl* left;
+ struct ZixTreeNodeImpl* right;
+ struct ZixTreeNodeImpl* parent;
+ int_fast8_t balance;
};
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
@@ -50,98 +50,98 @@ struct ZixTreeNodeImpl {
// #define ZIX_TREE_HYPER_VERIFY 1
#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY)
-# include "tree_debug.h"
-# define ASSERT_BALANCE(n) assert(verify_balance(n))
+# include "tree_debug.h"
+# define ASSERT_BALANCE(n) assert(verify_balance(n))
#else
-# define ASSERT_BALANCE(n)
+# define ASSERT_BALANCE(n)
#endif
#ifdef ZIX_TREE_DUMP
-# include "tree_debug.h"
-# define DUMP(t) zix_tree_print(t->root, 0)
-# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__)
+# include "tree_debug.h"
+# define DUMP(t) zix_tree_print(t->root, 0)
+# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__)
#else
-# define DUMP(t)
-# define DEBUG_PRINTF(fmt, ...)
+# define DUMP(t)
+# define DEBUG_PRINTF(fmt, ...)
#endif
ZIX_API ZixTree*
-zix_tree_new(bool allow_duplicates,
- ZixComparator cmp,
- void* cmp_data,
- ZixDestroyFunc destroy)
+ zix_tree_new(bool allow_duplicates,
+ ZixComparator cmp,
+ void* cmp_data,
+ ZixDestroyFunc destroy)
{
- ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree));
- t->root = NULL;
- t->destroy = destroy;
- t->cmp = cmp;
- t->cmp_data = cmp_data;
- t->size = 0;
- t->allow_duplicates = allow_duplicates;
- return t;
+ ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree));
+ t->root = NULL;
+ t->destroy = destroy;
+ t->cmp = cmp;
+ t->cmp_data = cmp_data;
+ t->size = 0;
+ t->allow_duplicates = allow_duplicates;
+ return t;
}
ZIX_PRIVATE void
zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
{
- if (n) {
- zix_tree_free_rec(t, n->left);
- zix_tree_free_rec(t, n->right);
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
- }
+ if (n) {
+ zix_tree_free_rec(t, n->left);
+ zix_tree_free_rec(t, n->right);
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
+ free(n);
+ }
}
ZIX_API void
zix_tree_free(ZixTree* t)
{
- if (t) {
- zix_tree_free_rec(t, t->root);
- free(t);
- }
+ if (t) {
+ zix_tree_free_rec(t, t->root);
+ free(t);
+ }
}
ZIX_API size_t
zix_tree_size(const ZixTree* t)
{
- return t->size;
+ return t->size;
}
ZIX_PRIVATE void
rotate(ZixTreeNode* p, ZixTreeNode* q)
{
- assert(q->parent == p);
- assert(p->left == q || p->right == q);
-
- q->parent = p->parent;
- if (q->parent) {
- if (q->parent->left == p) {
- q->parent->left = q;
- } else {
- q->parent->right = q;
- }
- }
-
- if (p->right == q) {
- // Rotate left
- p->right = q->left;
- q->left = p;
- if (p->right) {
- p->right->parent = p;
- }
- } else {
- // Rotate right
- assert(p->left == q);
- p->left = q->right;
- q->right = p;
- if (p->left) {
- p->left->parent = p;
- }
- }
-
- p->parent = q;
+ assert(q->parent == p);
+ assert(p->left == q || p->right == q);
+
+ q->parent = p->parent;
+ if (q->parent) {
+ if (q->parent->left == p) {
+ q->parent->left = q;
+ } else {
+ q->parent->right = q;
+ }
+ }
+
+ if (p->right == q) {
+ // Rotate left
+ p->right = q->left;
+ q->left = p;
+ if (p->right) {
+ p->right->parent = p;
+ }
+ } else {
+ // Rotate right
+ assert(p->left == q);
+ p->left = q->right;
+ q->right = p;
+ if (p->left) {
+ p->left->parent = p;
+ }
+ }
+
+ p->parent = q;
}
/**
@@ -154,26 +154,26 @@ rotate(ZixTreeNode* p, ZixTreeNode* q)
* B C A B
*/
ZIX_PRIVATE ZixTreeNode*
-rotate_left(ZixTreeNode* p, int* height_change)
+ rotate_left(ZixTreeNode* p, int* height_change)
{
- ZixTreeNode* const q = p->right;
- *height_change = (q->balance == 0) ? 0 : -1;
+ ZixTreeNode* const q = p->right;
+ *height_change = (q->balance == 0) ? 0 : -1;
- DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data);
+ DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data);
- assert(p->balance == 2);
- assert(q->balance == 0 || q->balance == 1);
+ assert(p->balance == 2);
+ assert(q->balance == 0 || q->balance == 1);
- rotate(p, q);
+ rotate(p, q);
- // p->balance -= 1 + MAX(0, q->balance);
- // q->balance -= 1 - MIN(0, p->balance);
- --q->balance;
- p->balance = -(q->balance);
+ // p->balance -= 1 + MAX(0, q->balance);
+ // q->balance -= 1 - MIN(0, p->balance);
+ --q->balance;
+ p->balance = -(q->balance);
- ASSERT_BALANCE(p);
- ASSERT_BALANCE(q);
- return q;
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ return q;
}
/**
@@ -187,26 +187,26 @@ rotate_left(ZixTreeNode* p, int* height_change)
*
*/
ZIX_PRIVATE ZixTreeNode*
-rotate_right(ZixTreeNode* p, int* height_change)
+ rotate_right(ZixTreeNode* p, int* height_change)
{
- ZixTreeNode* const q = p->left;
- *height_change = (q->balance == 0) ? 0 : -1;
+ ZixTreeNode* const q = p->left;
+ *height_change = (q->balance == 0) ? 0 : -1;
- DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data);
+ DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data);
- assert(p->balance == -2);
- assert(q->balance == 0 || q->balance == -1);
+ assert(p->balance == -2);
+ assert(q->balance == 0 || q->balance == -1);
- rotate(p, q);
+ rotate(p, q);
- // p->balance += 1 - MIN(0, q->balance);
- // q->balance += 1 + MAX(0, p->balance);
- ++q->balance;
- p->balance = -(q->balance);
+ // p->balance += 1 - MIN(0, q->balance);
+ // q->balance += 1 + MAX(0, p->balance);
+ ++q->balance;
+ p->balance = -(q->balance);
- ASSERT_BALANCE(p);
- ASSERT_BALANCE(q);
- return q;
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ return q;
}
/**
@@ -222,35 +222,38 @@ rotate_right(ZixTreeNode* p, int* height_change)
*
*/
ZIX_PRIVATE ZixTreeNode*
-rotate_left_right(ZixTreeNode* p, int* height_change)
+ rotate_left_right(ZixTreeNode* p, int* height_change)
{
- ZixTreeNode* const q = p->left;
- ZixTreeNode* const r = q->right;
+ ZixTreeNode* const q = p->left;
+ ZixTreeNode* const r = q->right;
- assert(p->balance == -2);
- assert(q->balance == 1);
- assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+ assert(p->balance == -2);
+ assert(q->balance == 1);
+ assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
- DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n",
- (intptr_t)p->data, p->balance, q->balance, r->balance);
+ DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n",
+ (intptr_t)p->data,
+ p->balance,
+ q->balance,
+ r->balance);
- rotate(q, r);
- rotate(p, r);
+ rotate(q, r);
+ rotate(p, r);
- q->balance -= 1 + MAX(0, r->balance);
- p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
- // r->balance += MAX(0, p->balance) + MIN(0, q->balance);
+ q->balance -= 1 + MAX(0, r->balance);
+ p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
+ // r->balance += MAX(0, p->balance) + MIN(0, q->balance);
- // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0;
- // q->balance = - MAX(r->balance, 0);
- r->balance = 0;
+ // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0;
+ // q->balance = - MAX(r->balance, 0);
+ r->balance = 0;
- *height_change = -1;
+ *height_change = -1;
- ASSERT_BALANCE(p);
- ASSERT_BALANCE(q);
- ASSERT_BALANCE(r);
- return r;
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ ASSERT_BALANCE(r);
+ return r;
}
/**
@@ -266,452 +269,454 @@ rotate_left_right(ZixTreeNode* p, int* height_change)
*
*/
ZIX_PRIVATE ZixTreeNode*
-rotate_right_left(ZixTreeNode* p, int* height_change)
+ rotate_right_left(ZixTreeNode* p, int* height_change)
{
- ZixTreeNode* const q = p->right;
- ZixTreeNode* const r = q->left;
+ ZixTreeNode* const q = p->right;
+ ZixTreeNode* const r = q->left;
- assert(p->balance == 2);
- assert(q->balance == -1);
- assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+ assert(p->balance == 2);
+ assert(q->balance == -1);
+ assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
- DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n",
- (intptr_t)p->data, p->balance, q->balance, r->balance);
+ DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n",
+ (intptr_t)p->data,
+ p->balance,
+ q->balance,
+ r->balance);
- rotate(q, r);
- rotate(p, r);
+ rotate(q, r);
+ rotate(p, r);
- q->balance += 1 - MIN(0, r->balance);
- p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
- // r->balance += MAX(0, q->balance) + MIN(0, p->balance);
+ q->balance += 1 - MIN(0, r->balance);
+ p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
+ // r->balance += MAX(0, q->balance) + MIN(0, p->balance);
- // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0;
- // q->balance = - MIN(r->balance, 0);
- r->balance = 0;
- // assert(r->balance == 0);
+ // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0;
+ // q->balance = - MIN(r->balance, 0);
+ r->balance = 0;
+ // assert(r->balance == 0);
- *height_change = -1;
+ *height_change = -1;
- ASSERT_BALANCE(p);
- ASSERT_BALANCE(q);
- ASSERT_BALANCE(r);
- return r;
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ ASSERT_BALANCE(r);
+ return r;
}
ZIX_PRIVATE ZixTreeNode*
zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
{
#ifdef ZIX_TREE_HYPER_VERIFY
- const size_t old_height = height(node);
+ const size_t old_height = height(node);
#endif
- DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance);
- *height_change = 0;
- const bool is_root = !node->parent;
- assert((is_root && t->root == node) || (!is_root && t->root != node));
- ZixTreeNode* replacement = node;
- if (node->balance == -2) {
- assert(node->left);
- if (node->left->balance == 1) {
- replacement = rotate_left_right(node, height_change);
- } else {
- replacement = rotate_right(node, height_change);
- }
- } else if (node->balance == 2) {
- assert(node->right);
- if (node->right->balance == -1) {
- replacement = rotate_right_left(node, height_change);
- } else {
- replacement = rotate_left(node, height_change);
- }
- }
- if (is_root) {
- assert(!replacement->parent);
- t->root = replacement;
- }
- DUMP(t);
+ DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance);
+ *height_change = 0;
+ const bool is_root = !node->parent;
+ assert((is_root && t->root == node) || (!is_root && t->root != node));
+ ZixTreeNode* replacement = node;
+ if (node->balance == -2) {
+ assert(node->left);
+ if (node->left->balance == 1) {
+ replacement = rotate_left_right(node, height_change);
+ } else {
+ replacement = rotate_right(node, height_change);
+ }
+ } else if (node->balance == 2) {
+ assert(node->right);
+ if (node->right->balance == -1) {
+ replacement = rotate_right_left(node, height_change);
+ } else {
+ replacement = rotate_left(node, height_change);
+ }
+ }
+ if (is_root) {
+ assert(!replacement->parent);
+ t->root = replacement;
+ }
+ DUMP(t);
#ifdef ZIX_TREE_HYPER_VERIFY
- assert(old_height + *height_change == height(replacement));
+ assert(old_height + *height_change == height(replacement));
#endif
- return replacement;
+ return replacement;
}
ZIX_API ZixStatus
zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
{
- DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e);
- int cmp = 0;
- ZixTreeNode* n = t->root;
- ZixTreeNode* p = NULL;
-
- // Find the parent p of e
- while (n) {
- p = n;
- cmp = t->cmp(e, n->data, t->cmp_data);
- if (cmp < 0) {
- n = n->left;
- } else if (cmp > 0) {
- n = n->right;
- } else if (t->allow_duplicates) {
- n = n->right;
- } else {
- if (ti) {
- *ti = n;
- }
- DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
- return ZIX_STATUS_EXISTS;
- }
- }
-
- // Allocate a new node n
- if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) {
- return ZIX_STATUS_NO_MEM;
- }
- memset(n, '\0', sizeof(ZixTreeNode));
- n->data = e;
- n->balance = 0;
- if (ti) {
- *ti = n;
- }
-
- bool p_height_increased = false;
-
- // Make p the parent of n
- n->parent = p;
- if (!p) {
- t->root = n;
- } else {
- if (cmp < 0) {
- assert(!p->left);
- assert(p->balance == 0 || p->balance == 1);
- p->left = n;
- --p->balance;
- p_height_increased = !p->right;
- } else {
- assert(!p->right);
- assert(p->balance == 0 || p->balance == -1);
- p->right = n;
- ++p->balance;
- p_height_increased = !p->left;
- }
- }
-
- DUMP(t);
-
- // Rebalance if necessary (at most 1 rotation)
- assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
- if (p && p_height_increased) {
- int height_change = 0;
- for (ZixTreeNode* i = p; i && i->parent; i = i->parent) {
- if (i == i->parent->left) {
- if (--i->parent->balance == -2) {
- zix_tree_rebalance(t, i->parent, &height_change);
- break;
- }
- } else {
- assert(i == i->parent->right);
- if (++i->parent->balance == 2) {
- zix_tree_rebalance(t, i->parent, &height_change);
- break;
- }
- }
-
- if (i->parent->balance == 0) {
- break;
- }
- }
- }
-
- DUMP(t);
-
- ++t->size;
+ DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e);
+ int cmp = 0;
+ ZixTreeNode* n = t->root;
+ ZixTreeNode* p = NULL;
+
+ // Find the parent p of e
+ while (n) {
+ p = n;
+ cmp = t->cmp(e, n->data, t->cmp_data);
+ if (cmp < 0) {
+ n = n->left;
+ } else if (cmp > 0) {
+ n = n->right;
+ } else if (t->allow_duplicates) {
+ n = n->right;
+ } else {
+ if (ti) {
+ *ti = n;
+ }
+ DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
+ return ZIX_STATUS_EXISTS;
+ }
+ }
+
+ // Allocate a new node n
+ if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ memset(n, '\0', sizeof(ZixTreeNode));
+ n->data = e;
+ n->balance = 0;
+ if (ti) {
+ *ti = n;
+ }
+
+ bool p_height_increased = false;
+
+ // Make p the parent of n
+ n->parent = p;
+ if (!p) {
+ t->root = n;
+ } else {
+ if (cmp < 0) {
+ assert(!p->left);
+ assert(p->balance == 0 || p->balance == 1);
+ p->left = n;
+ --p->balance;
+ p_height_increased = !p->right;
+ } else {
+ assert(!p->right);
+ assert(p->balance == 0 || p->balance == -1);
+ p->right = n;
+ ++p->balance;
+ p_height_increased = !p->left;
+ }
+ }
+
+ DUMP(t);
+
+ // Rebalance if necessary (at most 1 rotation)
+ assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
+ if (p && p_height_increased) {
+ int height_change = 0;
+ for (ZixTreeNode* i = p; i && i->parent; i = i->parent) {
+ if (i == i->parent->left) {
+ if (--i->parent->balance == -2) {
+ zix_tree_rebalance(t, i->parent, &height_change);
+ break;
+ }
+ } else {
+ assert(i == i->parent->right);
+ if (++i->parent->balance == 2) {
+ zix_tree_rebalance(t, i->parent, &height_change);
+ break;
+ }
+ }
+
+ if (i->parent->balance == 0) {
+ break;
+ }
+ }
+ }
+
+ DUMP(t);
+
+ ++t->size;
#ifdef ZIX_TREE_VERIFY
- if (!verify(t, t->root)) {
- return ZIX_STATUS_ERROR;
- }
+ if (!verify(t, t->root)) {
+ return ZIX_STATUS_ERROR;
+ }
#endif
- return ZIX_STATUS_SUCCESS;
+ return ZIX_STATUS_SUCCESS;
}
ZIX_API ZixStatus
zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
{
- ZixTreeNode* const n = ti;
- ZixTreeNode** pp = NULL; // parent pointer
- ZixTreeNode* to_balance = n->parent; // lowest node to balance
- int8_t d_balance = 0; // delta(balance) for n->parent
-
- DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
-
- if ((n == t->root) && !n->left && !n->right) {
- t->root = NULL;
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
- --t->size;
- assert(t->size == 0);
- return ZIX_STATUS_SUCCESS;
- }
-
- // Set pp to the parent pointer to n, if applicable
- if (n->parent) {
- assert(n->parent->left == n || n->parent->right == n);
- if (n->parent->left == n) { // n is left child
- pp = &n->parent->left;
- d_balance = 1;
- } else { // n is right child
- assert(n->parent->right == n);
- pp = &n->parent->right;
- d_balance = -1;
- }
- }
-
- assert(!pp || *pp == n);
-
- int height_change = 0;
- if (!n->left && !n->right) {
- // n is a leaf, just remove it
- if (pp) {
- *pp = NULL;
- to_balance = n->parent;
- height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
- }
- } else if (!n->left) {
- // Replace n with right (only) child
- if (pp) {
- *pp = n->right;
- to_balance = n->parent;
- } else {
- t->root = n->right;
- }
- n->right->parent = n->parent;
- height_change = -1;
- } else if (!n->right) {
- // Replace n with left (only) child
- if (pp) {
- *pp = n->left;
- to_balance = n->parent;
- } else {
- t->root = n->left;
- }
- n->left->parent = n->parent;
- height_change = -1;
- } else {
- // Replace n with in-order successor (leftmost child of right subtree)
- ZixTreeNode* replace = n->right;
- while (replace->left) {
- assert(replace->left->parent == replace);
- replace = replace->left;
- }
-
- // Remove replace from parent (replace_p)
- if (replace->parent->left == replace) {
- height_change = replace->parent->right ? 0 : -1;
- d_balance = 1;
- to_balance = replace->parent;
- replace->parent->left = replace->right;
- } else {
- assert(replace->parent == n);
- height_change = replace->parent->left ? 0 : -1;
- d_balance = -1;
- to_balance = replace->parent;
- replace->parent->right = replace->right;
- }
-
- if (to_balance == n) {
- to_balance = replace;
- }
-
- if (replace->right) {
- replace->right->parent = replace->parent;
- }
-
- replace->balance = n->balance;
-
- // Swap node to delete with replace
- if (pp) {
- *pp = replace;
- } else {
- assert(t->root == n);
- t->root = replace;
- }
- replace->parent = n->parent;
- replace->left = n->left;
- n->left->parent = replace;
- replace->right = n->right;
- if (n->right) {
- n->right->parent = replace;
- }
-
- assert(!replace->parent
- || replace->parent->left == replace
- || replace->parent->right == replace);
- }
-
- // Rebalance starting at to_balance upwards.
- for (ZixTreeNode* i = to_balance; i; i = i->parent) {
- i->balance += d_balance;
- if (d_balance == 0 || i->balance == -1 || i->balance == 1) {
- break;
- }
-
- assert(i != n);
- i = zix_tree_rebalance(t, i, &height_change);
- if (i->balance == 0) {
- height_change = -1;
- }
-
- if (i->parent) {
- if (i == i->parent->left) {
- d_balance = height_change * -1;
- } else {
- assert(i == i->parent->right);
- d_balance = height_change;
- }
- }
- }
-
- DUMP(t);
-
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
-
- --t->size;
+ ZixTreeNode* const n = ti;
+ ZixTreeNode** pp = NULL; // parent pointer
+ ZixTreeNode* to_balance = n->parent; // lowest node to balance
+ int8_t d_balance = 0; // delta(balance) for n->parent
+
+ DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
+
+ if ((n == t->root) && !n->left && !n->right) {
+ t->root = NULL;
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
+ free(n);
+ --t->size;
+ assert(t->size == 0);
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ // Set pp to the parent pointer to n, if applicable
+ if (n->parent) {
+ assert(n->parent->left == n || n->parent->right == n);
+ if (n->parent->left == n) { // n is left child
+ pp = &n->parent->left;
+ d_balance = 1;
+ } else { // n is right child
+ assert(n->parent->right == n);
+ pp = &n->parent->right;
+ d_balance = -1;
+ }
+ }
+
+ assert(!pp || *pp == n);
+
+ int height_change = 0;
+ if (!n->left && !n->right) {
+ // n is a leaf, just remove it
+ if (pp) {
+ *pp = NULL;
+ to_balance = n->parent;
+ height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
+ }
+ } else if (!n->left) {
+ // Replace n with right (only) child
+ if (pp) {
+ *pp = n->right;
+ to_balance = n->parent;
+ } else {
+ t->root = n->right;
+ }
+ n->right->parent = n->parent;
+ height_change = -1;
+ } else if (!n->right) {
+ // Replace n with left (only) child
+ if (pp) {
+ *pp = n->left;
+ to_balance = n->parent;
+ } else {
+ t->root = n->left;
+ }
+ n->left->parent = n->parent;
+ height_change = -1;
+ } else {
+ // Replace n with in-order successor (leftmost child of right subtree)
+ ZixTreeNode* replace = n->right;
+ while (replace->left) {
+ assert(replace->left->parent == replace);
+ replace = replace->left;
+ }
+
+ // Remove replace from parent (replace_p)
+ if (replace->parent->left == replace) {
+ height_change = replace->parent->right ? 0 : -1;
+ d_balance = 1;
+ to_balance = replace->parent;
+ replace->parent->left = replace->right;
+ } else {
+ assert(replace->parent == n);
+ height_change = replace->parent->left ? 0 : -1;
+ d_balance = -1;
+ to_balance = replace->parent;
+ replace->parent->right = replace->right;
+ }
+
+ if (to_balance == n) {
+ to_balance = replace;
+ }
+
+ if (replace->right) {
+ replace->right->parent = replace->parent;
+ }
+
+ replace->balance = n->balance;
+
+ // Swap node to delete with replace
+ if (pp) {
+ *pp = replace;
+ } else {
+ assert(t->root == n);
+ t->root = replace;
+ }
+ replace->parent = n->parent;
+ replace->left = n->left;
+ n->left->parent = replace;
+ replace->right = n->right;
+ if (n->right) {
+ n->right->parent = replace;
+ }
+
+ assert(!replace->parent || replace->parent->left == replace ||
+ replace->parent->right == replace);
+ }
+
+ // Rebalance starting at to_balance upwards.
+ for (ZixTreeNode* i = to_balance; i; i = i->parent) {
+ i->balance += d_balance;
+ if (d_balance == 0 || i->balance == -1 || i->balance == 1) {
+ break;
+ }
+
+ assert(i != n);
+ i = zix_tree_rebalance(t, i, &height_change);
+ if (i->balance == 0) {
+ height_change = -1;
+ }
+
+ if (i->parent) {
+ if (i == i->parent->left) {
+ d_balance = height_change * -1;
+ } else {
+ assert(i == i->parent->right);
+ d_balance = height_change;
+ }
+ }
+ }
+
+ DUMP(t);
+
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
+ free(n);
+
+ --t->size;
#ifdef ZIX_TREE_VERIFY
- if (!verify(t, t->root)) {
- return ZIX_STATUS_ERROR;
- }
+ if (!verify(t, t->root)) {
+ return ZIX_STATUS_ERROR;
+ }
#endif
- return ZIX_STATUS_SUCCESS;
+ return ZIX_STATUS_SUCCESS;
}
ZIX_API ZixStatus
zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
{
- ZixTreeNode* n = t->root;
- while (n) {
- const int cmp = t->cmp(e, n->data, t->cmp_data);
- if (cmp == 0) {
- break;
- }
-
- if (cmp < 0) {
- n = n->left;
- } else {
- n = n->right;
- }
- }
-
- *ti = n;
- return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
+ ZixTreeNode* n = t->root;
+ while (n) {
+ const int cmp = t->cmp(e, n->data, t->cmp_data);
+ if (cmp == 0) {
+ break;
+ }
+
+ if (cmp < 0) {
+ n = n->left;
+ } else {
+ n = n->right;
+ }
+ }
+
+ *ti = n;
+ return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
}
ZIX_API void*
zix_tree_get(const ZixTreeIter* ti)
{
- return ti ? ti->data : NULL;
+ return ti ? ti->data : NULL;
}
ZIX_API ZixTreeIter*
-zix_tree_begin(ZixTree* t)
+ zix_tree_begin(ZixTree* t)
{
- if (!t->root) {
- return NULL;
- }
-
- ZixTreeNode* n = t->root;
- while (n->left) {
- n = n->left;
- }
- return n;
+ if (!t->root) {
+ return NULL;
+ }
+
+ ZixTreeNode* n = t->root;
+ while (n->left) {
+ n = n->left;
+ }
+ return n;
}
ZIX_API ZixTreeIter*
-zix_tree_end(ZixTree* t)
+ zix_tree_end(ZixTree* t)
{
- return NULL;
+ return NULL;
}
ZIX_API ZixTreeIter*
-zix_tree_rbegin(ZixTree* t)
+ zix_tree_rbegin(ZixTree* t)
{
- if (!t->root) {
- return NULL;
- }
-
- ZixTreeNode* n = t->root;
- while (n->right) {
- n = n->right;
- }
- return n;
+ if (!t->root) {
+ return NULL;
+ }
+
+ ZixTreeNode* n = t->root;
+ while (n->right) {
+ n = n->right;
+ }
+ return n;
}
ZIX_API ZixTreeIter*
-zix_tree_rend(ZixTree* t)
+ zix_tree_rend(ZixTree* t)
{
- return NULL;
+ return NULL;
}
ZIX_API bool
zix_tree_iter_is_end(const ZixTreeIter* i)
{
- return !i;
+ return !i;
}
ZIX_API bool
zix_tree_iter_is_rend(const ZixTreeIter* i)
{
- return !i;
+ return !i;
}
ZIX_API ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i)
+ zix_tree_iter_next(ZixTreeIter* i)
{
- if (!i) {
- return NULL;
- }
-
- if (i->right) {
- i = i->right;
- while (i->left) {
- i = i->left;
- }
- } else {
- while (i->parent && i->parent->right == i) { // i is a right child
- i = i->parent;
- }
-
- i = i->parent;
- }
-
- return i;
+ if (!i) {
+ return NULL;
+ }
+
+ if (i->right) {
+ i = i->right;
+ while (i->left) {
+ i = i->left;
+ }
+ } else {
+ while (i->parent && i->parent->right == i) { // i is a right child
+ i = i->parent;
+ }
+
+ i = i->parent;
+ }
+
+ return i;
}
ZIX_API ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i)
+ zix_tree_iter_prev(ZixTreeIter* i)
{
- if (!i) {
- return NULL;
- }
-
- if (i->left) {
- i = i->left;
- while (i->right) {
- i = i->right;
- }
- } else {
- while (i->parent && i->parent->left == i) { // i is a left child
- i = i->parent;
- }
-
- i = i->parent;
- }
-
- return i;
+ if (!i) {
+ return NULL;
+ }
+
+ if (i->left) {
+ i = i->left;
+ while (i->right) {
+ i = i->right;
+ }
+ } else {
+ while (i->parent && i->parent->left == i) { // i is a left child
+ i = i->parent;
+ }
+
+ i = i->parent;
+ }
+
+ return i;
}
diff --git a/src/zix/tree.h b/src/zix/tree.h
index 983c0ea..170e2ca 100644
--- a/src/zix/tree.h
+++ b/src/zix/tree.h
@@ -47,10 +47,10 @@ typedef struct ZixTreeNodeImpl ZixTreeIter;
Create a new (empty) tree.
*/
ZIX_API ZixTree*
-zix_tree_new(bool allow_duplicates,
- ZixComparator cmp,
- void* cmp_data,
- ZixDestroyFunc destroy);
+ zix_tree_new(bool allow_duplicates,
+ ZixComparator cmp,
+ void* cmp_data,
+ ZixDestroyFunc destroy);
/**
Free `t`.
@@ -93,13 +93,13 @@ zix_tree_get(const ZixTreeIter* ti);
Return an iterator to the first (smallest) element in `t`.
*/
ZIX_API ZixTreeIter*
-zix_tree_begin(ZixTree* t);
+ zix_tree_begin(ZixTree* t);
/**
Return an iterator the the element one past the last element in `t`.
*/
ZIX_API ZixTreeIter*
-zix_tree_end(ZixTree* t);
+ zix_tree_end(ZixTree* t);
/**
Return true iff `i` is an iterator to the end of its tree.
@@ -111,13 +111,13 @@ zix_tree_iter_is_end(const ZixTreeIter* i);
Return an iterator to the last (largest) element in `t`.
*/
ZIX_API ZixTreeIter*
-zix_tree_rbegin(ZixTree* t);
+ zix_tree_rbegin(ZixTree* t);
/**
Return an iterator the the element one before the first element in `t`.
*/
ZIX_API ZixTreeIter*
-zix_tree_rend(ZixTree* t);
+ zix_tree_rend(ZixTree* t);
/**
Return true iff `i` is an iterator to the reverse end of its tree.
@@ -129,13 +129,13 @@ zix_tree_iter_is_rend(const ZixTreeIter* i);
Return an iterator that points to the element one past `i`.
*/
ZIX_API ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i);
+ zix_tree_iter_next(ZixTreeIter* i);
/**
Return an iterator that points to the element one before `i`.
*/
ZIX_API ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i);
+ zix_tree_iter_prev(ZixTreeIter* i);
/**
@}
@@ -143,7 +143,7 @@ zix_tree_iter_prev(ZixTreeIter* i);
*/
#ifdef __cplusplus
-} /* extern "C" */
+} /* extern "C" */
#endif
-#endif /* ZIX_TREE_H */
+#endif /* ZIX_TREE_H */
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-16 19:22:08 +0000