Updating branch refs/heads/master to f3472d91253a3016d68e2941b128a0d96f52ae00 (commit) from d3cc31e6fb872e00eaad4291746c551435eea1c2 (commit)
commit f3472d91253a3016d68e2941b128a0d96f52ae00 Author: Peter de Ridder <pe...@xfce.org> Date: Tue Oct 4 21:42:13 2011 +0200 Balance the btree btree delete isn't supported libsqueeze/archive-iter.c | 2 +- libsqueeze/archive.c | 4 - libsqueeze/btree.c | 153 ++++++++++++++++++++++++++++++++++++++++++++- libsqueeze/btree.h | 1 + 4 files changed, 153 insertions(+), 7 deletions(-) diff --git a/libsqueeze/archive-iter.c b/libsqueeze/archive-iter.c index 8762777..e713cb3 100644 --- a/libsqueeze/archive-iter.c +++ b/libsqueeze/archive-iter.c @@ -29,7 +29,7 @@ #include "internals.h" #ifndef LSQ_ENTRY_CHILD_BUFFER_SIZE -#define LSQ_ENTRY_CHILD_BUFFER_SIZE 500 +#define LSQ_ENTRY_CHILD_BUFFER_SIZE 8000 #endif #ifdef LSQ_ENTRY_CHILD_BUFFER_DYNAMIC_SIZE diff --git a/libsqueeze/archive.c b/libsqueeze/archive.c index 262391b..fdac9f4 100644 --- a/libsqueeze/archive.c +++ b/libsqueeze/archive.c @@ -37,10 +37,6 @@ #include "internals.h" -#ifndef LSQ_ENTRY_CHILD_BUFFER_SIZE -#define LSQ_ENTRY_CHILD_BUFFER_SIZE 500 -#endif - static void lsq_archive_class_init(LSQArchiveClass *archive_class); diff --git a/libsqueeze/btree.c b/libsqueeze/btree.c index 869bd80..ca3c49f 100644 --- a/libsqueeze/btree.c +++ b/libsqueeze/btree.c @@ -27,7 +27,7 @@ #include "btree.h" #ifndef LSQ_BTREE_MAX_DEPTH -#define LSQ_BTREE_MAX_DEPTH 500 +#define LSQ_BTREE_MAX_DEPTH 20 #endif LSQBTree * @@ -42,13 +42,19 @@ lsq_btree_insert_sorted_single ( LSQBTree *new_entry = NULL; LSQBTree *stack[LSQ_BTREE_MAX_DEPTH]; guint stack_i = 0; + LSQArchiveEntry *swap_entry; + LSQBTree *swap_iter; + gint swap_balance; + gboolean short_side; + /* Check for a flat list */ if ( NULL != list && NULL != list->next ) { g_critical("Cannot insert into a flattened tree"); return NULL; } + /* Walk the btree */ for ( iter = list; NULL != iter; iter = *next ) { /* archive can be NULL */ @@ -56,32 +62,175 @@ lsq_btree_insert_sorted_single ( if ( 0 > cmp ) { + /* Go the the left */ next = &iter->left; } else if ( 0 < cmp ) { + /* Go to the right */ next = &iter->right; } else { + /* Logic outside this routine dictates we should never find a match */ g_critical("THIS SHOULD NOT HAPPEN!!! (the universe has just collapsed)"); return NULL; } + /* Keep a stack of the path we followed */ + g_return_val_if_fail(stack_i < LSQ_BTREE_MAX_DEPTH, NULL); stack[stack_i++] = iter; - g_return_val_if_fail(stack_i < LSQ_BTREE_MAX_DEPTH, NULL); } + /* Create a new tree element */ new_entry = g_new0(LSQBTree, 1); new_entry->entry = entry; + /* Check it this is a new tree */ if ( NULL == next ) { return new_entry; } + /* Store ourself in the parent */ *next = new_entry; + /* Balance the tree */ + while ( 0 < stack_i ) + { + iter = stack[--stack_i]; + + /* Calculate new the balance for the parent */ + if ( iter->left == new_entry ) + { + short_side = iter->balance > 0; + --iter->balance; + } + else + { + short_side = iter->balance < 0; + ++iter->balance; + } + + /* The balance in the higher parents doesn't change when the short side changed */ + if ( FALSE != short_side ) + { + break; + } + + if ( 1 < iter->balance ) + { + /* Rotate left */ + /* The code could be easier if we would just overwrite our parent left or right value. + * But instead we move that data from our right to our self and use the right tree link to be placed in the tree as if it was ourself. + */ + /* Letters are tree nodes, numbers are the data. This illustrates a rotate right. + * + * A:4 | A:2 + * / \ | / \ + * B:2 C:5 | D:1 B:4 + * / \ | / \ + * D:1 E:3 | E:3 C:5 + */ + /* Swap the data */ + swap_iter = iter->right; + swap_entry = iter->entry; + iter->entry = swap_iter->entry; + swap_iter->entry = swap_entry; + + /* Reformat the tree links */ + iter->right = swap_iter->right; + swap_iter->right = swap_iter->left; + swap_iter->left = iter->left; + iter->left = swap_iter; + + /* Fix the balance values + * + * if B > 0 + * A = A - 1 - B + * else + * A = A - 1 + * + * diff = A - 1 - B + * if diff < 0 + * B = B - 1 + diff + * else + * B = B - 1 + */ + swap_balance = swap_iter->balance; + swap_iter->balance = iter->balance - 1; + if ( 0 < swap_balance ) + { + swap_iter->balance -= swap_balance; + } + iter->balance = iter->balance - 1 - swap_balance; + if ( 0 < iter->balance ) + { + iter->balance = 0; + } + iter->balance += swap_balance - 1; + + /* We added a child so our depth was increased, but we also saved depth by rotation so our parents depth stays the same */ + if ( 0 < swap_balance ) + { + break; + } + } + else if ( -1 > iter->balance ) + { + /* Rotate right */ + /* The code could be easier if we would just overwrite our parent left or right value. + * But instead we move that data from our left to our self and use the left tree link to be placed in the tree as if it was ourself. + */ + /* Swap the data */ + swap_iter = iter->left; + swap_entry = iter->entry; + iter->entry = swap_iter->entry; + swap_iter->entry = swap_entry; + + /* Reformat the tree links */ + iter->left = swap_iter->left; + swap_iter->left = swap_iter->right; + swap_iter->right = iter->right; + iter->right = swap_iter; + + /* Fix the balance values + * + * if B < 0 + * A = A + 1 - B + * else + * A = A + 1 + * + * diff = A + 1 - B + * if diff > 0 + * B = B + 1 + diff + * else + * B = B + 1 + */ + swap_balance = swap_iter->balance; + swap_iter->balance = iter->balance + 1; + if ( 0 > swap_balance ) + { + swap_iter->balance -= swap_balance; + } + iter->balance = iter->balance + 1 - swap_balance; + if ( 0 > iter->balance ) + { + iter->balance = 0; + } + iter->balance += swap_balance + 1; + + /* We added a child so our depth was increased, but we also saved depth by rotation so our parents depth stays the same */ + if ( 0 > swap_balance ) + { + break; + } + } + + /* Store ourself in new_entry for the check in the next parent */ + new_entry = iter; + } + return list; } diff --git a/libsqueeze/btree.h b/libsqueeze/btree.h index 67a067b..a7bc8d7 100644 --- a/libsqueeze/btree.h +++ b/libsqueeze/btree.h @@ -24,6 +24,7 @@ struct _LSQBTree { LSQBTree *next; LSQBTree *left; LSQBTree *right; + gint balance; }; LSQBTree * _______________________________________________ Xfce4-commits mailing list Xfce4-commits@xfce.org https://mail.xfce.org/mailman/listinfo/xfce4-commits