@@ -5,7 +5,7 @@ include $(src)/scripts/utils.mk
OBJS =
OBJS += histograms.o
OBJS += delta.o
-OBJS += hash.o
+OBJS += rbtree.o
OBJS := $(OBJS:%.o=$(bdir)/%.o)
@@ -358,22 +358,19 @@ int traceeval_delta_stop_size(struct traceeval *teval,
static int create_delta_iter_array(struct traceeval_iterator *iter)
{
struct traceeval *teval = iter->teval;
- struct hash_table *hist = teval->hist;
- struct hash_iter *hiter;
- struct hash_item *item;
+ struct teval_rbtree_node *node = NULL;
size_t ts_idx = teval->nr_val_types - 1;
size_t idx = 0;
- int i;
- iter->nr_entries = hash_nr_items(hist);
+ iter->nr_entries = teval->tree.nr_nodes;
iter->entries = calloc(iter->nr_entries, sizeof(*iter->entries));
if (!iter->entries) {
teval_print_err(TEVAL_CRIT, "Failed to allocate entries");
return -1;
}
- for (i = 0, hiter = hash_iter_start(hist); (item = hash_iter_next(hiter)); i++) {
- struct entry *entry = container_of(item, struct entry, hash);
+ while ((node = teval_rbtree_next(teval, node))) {
+ struct entry *entry = container_of(node, struct entry, node);
/* Only add entries where the timestamp is non zero */
if (!entry->vals[ts_idx].number_64)
@@ -2,6 +2,7 @@
#ifndef __EVAL_LOCAL_H
#define __EVAL_LOCAL_H
+#include <traceeval.h>
#include <string.h>
/* For possible future use */
@@ -15,11 +16,6 @@
#define container_of(ptr, type, field) \
(type *)((void *)(ptr) - (void *)offset_of(type, field))
-#define HASH_BITS 10 /* Start with 1K of buckets */
-#define HASH_SIZE(bits) (1 << (bits))
-#define HASH_MASK(bits) (HASH_SIZE(bits) - 1)
-
-
extern void __attribute__ ((format (printf, 2, 3)))
teval_print_err(int level, const char *fmt, ...);
@@ -36,22 +32,25 @@ do { \
return (a) != (b); \
} while (0) \
-struct hash_item {
- struct hash_item *next;
- unsigned key;
+struct teval_rbtree_node {
+ struct teval_rbtree_node *parent;
+ struct teval_rbtree_node *left;
+ struct teval_rbtree_node *right;
+ int color;
};
-struct hash_iter {
- struct hash_item *next_item;
- size_t current_bucket;
-};
+typedef int (*teval_rbtree_cmp_fn)(struct traceeval *teval,
+ const struct teval_rbtree_node *A, const struct teval_rbtree_node *B);
-/* A table of key-value entries */
-struct hash_table {
- struct hash_item **hash;
- unsigned bits;
- size_t nr_items;
- struct hash_iter iter;
+typedef int (*teval_rbtree_search_fn)(struct traceeval *teval,
+ const struct teval_rbtree_node *n,
+ const struct traceeval_data *keys);
+
+struct teval_rbtree {
+ struct teval_rbtree_node *node;
+ teval_rbtree_search_fn search;
+ teval_rbtree_cmp_fn cmp;
+ size_t nr_nodes;
};
struct traceeval_stat {
@@ -67,11 +66,11 @@ struct traceeval_stat {
/* A key-value pair */
struct entry {
- struct hash_item hash;
- struct traceeval_data *keys;
- struct traceeval_data *vals;
- struct traceeval_stat *val_stats;
- size_t hitcount;
+ struct teval_rbtree_node node;
+ struct traceeval_data *keys;
+ struct traceeval_data *vals;
+ struct traceeval_stat *val_stats;
+ size_t hitcount;
};
enum {
@@ -84,8 +83,8 @@ struct traceeval_delta;
struct traceeval {
struct traceeval_type *key_types;
struct traceeval_type *val_types;
- struct hash_table *hist;
struct traceeval_delta *tdelta;
+ struct teval_rbtree tree;
unsigned int flags;
ssize_t nr_key_types;
ssize_t nr_val_types;
@@ -122,49 +121,20 @@ extern int _teval_get_entry(struct traceeval *teval, const struct traceeval_data
extern void _teval_update_stat(struct traceeval_type *type, struct traceeval_stat *stat,
unsigned long long val, unsigned long long ts);
-extern struct hash_table *hash_alloc(void);
-extern void hash_free(struct hash_table *hash);
-extern void hash_add(struct hash_table *hash, struct hash_item *item, unsigned key);
-extern int hash_remove(struct hash_table *hash, struct hash_item *item);
-
-extern struct hash_iter *hash_iter_start(struct hash_table *hash);
-extern struct hash_item *hash_iter_next(struct hash_iter *iter);
-
-extern struct hash_iter *hash_iter_bucket(struct hash_table *hash, unsigned key);
-extern struct hash_item *hash_iter_bucket_next(struct hash_iter *iter);
-
extern void __delta_release(struct traceeval_delta *tdelta);
-static inline size_t hash_nr_items(struct hash_table *hash)
-{
- return hash->nr_items;
-}
-
-static inline unsigned long long hash_string(const char *str)
-{
- unsigned long long key = 0;
- int len = strlen(str);
- int i;
-
- for (i = 0; i < len; i++)
- key += (unsigned long long)str[i] << ((i & 7) * 8);
-
- return key;
-}
-
int _teval_insert(struct traceeval *teval,
const struct traceeval_data *keys, size_t nr_keys,
const struct traceeval_data *vals, size_t nr_vals);
- /*
- * This is a quick hashing function adapted from Donald E. Knuth's 32
- * bit multiplicative hash. See The Art of Computer Programming (TAOCP).
- * Multiplication by the Prime number, closest to the golden ratio of
- * 2^32.
- */
-static inline unsigned long long hash_number(unsigned long long val)
-{
- return val * 2654435761ULL;
-}
+void teval_rbtree_init(struct traceeval *teval, teval_rbtree_cmp_fn cmp_fn,
+ teval_rbtree_search_fn search_fn);
+struct teval_rbtree_node *teval_rbtree_find(struct traceeval *teval,
+ const struct traceeval_data *keys);
+void teval_rbtree_delete(struct traceeval *teval, struct teval_rbtree_node *node);
+int teval_rbtree_insert(struct traceeval *teval, struct teval_rbtree_node *node);
+struct teval_rbtree_node *teval_rbtree_next(struct traceeval *teval,
+ struct teval_rbtree_node *node);
+struct teval_rbtree_node *teval_rbtree_pop_nobalance(struct traceeval *teval);
#endif
deleted file mode 100644
@@ -1,123 +0,0 @@
-/* SPDX-License-Identifier: MIT */
-/*
- * libtraceeval hashtable interface implementation.
- *
- * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
- */
-
-#include <traceeval.h>
-
-#include "eval-local.h"
-
-__hidden struct hash_table *hash_alloc(void)
-{
- struct hash_table *hash;
-
- hash = calloc(1, sizeof(*hash));
- if (!hash)
- return NULL;
-
- hash->bits = HASH_BITS;
- hash->hash = calloc(HASH_SIZE(hash->bits), sizeof(*hash->hash));
- if (!hash->hash) {
- free(hash);
- hash = NULL;
- }
-
- return hash;
-}
-
-__hidden void hash_free(struct hash_table *hash)
-{
- free(hash->hash);
- free(hash);
-}
-
-__hidden void hash_add(struct hash_table *hash, struct hash_item *item, unsigned key)
-{
- key &= HASH_MASK(hash->bits);
-
- item->next = hash->hash[key];
- hash->hash[key] = item;
- item->key = key;
-
- hash->nr_items++;
-}
-
-__hidden int hash_remove(struct hash_table *hash, struct hash_item *item)
-{
- struct hash_item **parent;
-
- for (parent = &hash->hash[item->key]; *parent; parent = &(*parent)->next) {
- if (*parent == item) {
- *parent = item->next;
- hash->nr_items--;
- return 1;
- }
- }
- return 0;
-}
-
-__hidden struct hash_iter *hash_iter_start(struct hash_table *hash)
-{
- struct hash_iter *iter = &hash->iter;
- size_t i;
-
- for (i = 0; i < HASH_SIZE(hash->bits); i++) {
- if (!hash->hash[i])
- continue;
- iter->next_item = hash->hash[i];
- break;
- }
- iter->current_bucket = i;
- return iter;
-}
-
-__hidden struct hash_item *hash_iter_next(struct hash_iter *iter)
-{
- struct hash_table *hash = container_of(iter, struct hash_table, iter);
- struct hash_item *item;
-
- if (iter->current_bucket >= HASH_SIZE(hash->bits))
- return NULL;
-
- item = iter->next_item;
- if (!item)
- return NULL;
-
- iter->next_item = item->next;
- if (!iter->next_item) {
- size_t i;
-
- for (i = iter->current_bucket + 1; i < HASH_SIZE(hash->bits); i++) {
- if (!hash->hash[i])
- continue;
- iter->next_item = hash->hash[i];
- break;
- }
- iter->current_bucket = i;
- }
- return item;
-}
-
-__hidden struct hash_iter *hash_iter_bucket(struct hash_table *hash, unsigned key)
-{
- struct hash_iter *iter = &hash->iter;
-
- key &= HASH_MASK(hash->bits);
-
- iter->current_bucket = key;
- iter->next_item = hash->hash[key];
-
- return iter;
-}
-
-__hidden struct hash_item *hash_iter_bucket_next(struct hash_iter *iter)
-{
- struct hash_item *item = iter->next_item;
-
- if (item)
- iter->next_item = item->next;
-
- return item;
-}
@@ -115,12 +115,12 @@ static int compare_traceeval_data(struct traceeval *teval,
if (!orig) {
teval_print_err(TEVAL_INFO, "No source data passed in to compare");
- return -1;
+ return -2;
}
if (!copy) {
teval_print_err(TEVAL_INFO, "No destination data passed in to compare");
- return -1;
+ return -2;
}
if (type->cmp)
@@ -157,28 +157,6 @@ static int compare_traceeval_data(struct traceeval *teval,
}
}
-/*
- * Compare arrays of struct traceeval_data's with respect to @def.
- *
- * Return 1 if @orig and @copy are the same, 0 if not, and -1 on error.
- */
-static int compare_traceeval_data_set(struct traceeval *teval,
- struct traceeval_type *defs,
- struct traceeval_data *orig,
- const struct traceeval_data *copy, size_t size)
-{
- int check;
- size_t i;
-
- /* compare data arrays */
- for (i = 0; i < size; i++) {
- if ((check = compare_traceeval_data(teval, defs + i, orig + i, copy + i)))
- return check == -2 ? -1 : 0;
- }
-
- return 1;
-}
-
/*
* type_release - free a struct traceeval_type array
* @defs: The array to release
@@ -341,6 +319,11 @@ static int check_vals(struct traceeval *teval, struct traceeval_type *vals, int
return 0;
}
+static int key_cmp(struct traceeval *teval,
+ const struct teval_rbtree_node *A, const struct teval_rbtree_node *B);
+static int key_search(struct traceeval *teval, const struct teval_rbtree_node *n,
+ const struct traceeval_data *keys);
+
/*
* traceeval_init_data_size - create a traceeval descriptor
* @keys: Defines the keys to differentiate traceeval entries
@@ -426,12 +409,7 @@ struct traceeval *traceeval_init_data_size(struct traceeval_type *keys,
goto fail_release;
}
- /* alloc hist */
- teval->hist = hash_alloc();
- if (!teval->hist) {
- err_msg = "Failed to allocate memory for histogram";
- goto fail_release;
- }
+ teval_rbtree_init(teval, key_cmp, key_search);
teval->sizeof_type = sizeof_type;
teval->sizeof_data = sizeof_data;
@@ -499,26 +477,17 @@ static void free_entry(struct traceeval *teval, struct entry *entry)
}
/*
- * Free the hist_table allocated to a traceeval instance.
+ * Free all the instances in the tree.
*/
-static void hist_table_release(struct traceeval *teval)
+static void tree_release(struct traceeval *teval)
{
- struct hash_table *hist = teval->hist;
- struct hash_iter *iter;
- struct hash_item *item;
-
- if (!hist)
- return;
+ struct teval_rbtree_node *node;
- for (iter = hash_iter_start(hist); (item = hash_iter_next(iter)); ) {
- struct entry *entry = container_of(item, struct entry, hash);
+ while ((node = teval_rbtree_pop_nobalance(teval))) {
+ struct entry *entry = container_of(node, struct entry, node);
- hash_remove(hist, &entry->hash);
free_entry(teval, entry);
}
-
- hash_free(hist);
- teval->hist = NULL;
}
/*
@@ -537,7 +506,7 @@ void traceeval_release(struct traceeval *teval)
return;
__delta_release(teval->tdelta);
- hist_table_release(teval);
+ tree_release(teval);
type_release(teval->key_types, teval->nr_key_types);
type_release(teval->val_types, teval->nr_val_types);
teval->key_types = NULL;
@@ -545,41 +514,35 @@ void traceeval_release(struct traceeval *teval)
free(teval);
}
-static unsigned make_hash(struct traceeval *teval, const struct traceeval_data *keys,
- int bits)
+static int compare_keys(struct traceeval *teval, const struct traceeval_data *A,
+ const struct traceeval_data *B)
{
- const struct traceeval_type *types = teval->key_types;
- unsigned long long val;
- unsigned key = 0;
- int nr = teval->nr_key_types;
-
- for (int i = 0; i < nr; i++) {
- if (types[i].hash) {
- key += types[i].hash(teval, &types[i], &keys[i]);
- continue;
- }
+ int ret;
- switch (types[i].type) {
- case TRACEEVAL_TYPE_NUMBER_8:
- case TRACEEVAL_TYPE_NUMBER_16:
- case TRACEEVAL_TYPE_NUMBER_32:
- case TRACEEVAL_TYPE_NUMBER_64:
- case TRACEEVAL_TYPE_NUMBER:
- val = keys[i].number_64;
- break;
- case TRACEEVAL_TYPE_DELTA:
- val = keys[i].delta.delta;
- break;
- case TRACEEVAL_TYPE_STRING:
- val = hash_string(keys[i].cstring);
- break;
- default:
- val = 0;
- }
- key += hash_number(val);
+ for (size_t i = 0; i < teval->nr_key_types; i++) {
+ ret = compare_traceeval_data(teval, &teval->key_types[i],
+ &A[i], &B[i]);
+ if (ret)
+ return ret;
}
+ return 0;
+}
- return key;
+static int key_search(struct traceeval *teval, const struct teval_rbtree_node *n,
+ const struct traceeval_data *keys)
+{
+ const struct entry *entry = container_of(n, struct entry, node);
+
+ return compare_keys(teval, entry->keys, keys);
+}
+
+static int key_cmp(struct traceeval *teval,
+ const struct teval_rbtree_node *A, const struct teval_rbtree_node *B)
+{
+ const struct entry *a = container_of(A, struct entry, node);
+ const struct entry *b = container_of(B, struct entry, node);
+
+ return compare_keys(teval, a->keys, b->keys);
}
/*
@@ -590,12 +553,7 @@ static unsigned make_hash(struct traceeval *teval, const struct traceeval_data *
__hidden int _teval_get_entry(struct traceeval *teval, const struct traceeval_data *keys,
struct entry **result)
{
- struct hash_table *hist = teval->hist;
- struct entry *entry = NULL;
- struct hash_iter *iter;
- struct hash_item *item;
- unsigned key;
- int check = 0;
+ struct teval_rbtree_node *node;
int i;
if (!teval || !keys) {
@@ -610,20 +568,13 @@ __hidden int _teval_get_entry(struct traceeval *teval, const struct traceeval_da
}
}
- key = make_hash(teval, keys, hist->bits);
-
- for (iter = hash_iter_bucket(hist, key); (item = hash_iter_bucket_next(iter)); ) {
- entry = container_of(item, struct entry, hash);
+ node = teval_rbtree_find(teval, keys);
+ if (!node)
+ return 0;
- check = compare_traceeval_data_set(teval, teval->key_types,
- entry->keys, keys, teval->nr_key_types);
- if (check)
- break;
- }
+ *result = container_of(node, struct entry, node);
- if (check > 0)
- *result = entry;
- return check;
+ return 1;
}
__hidden void _teval_update_stat(struct traceeval_type *type,
@@ -912,22 +863,6 @@ void traceeval_results_release(struct traceeval *teval,
}
}
-static struct entry *create_hist_entry(struct traceeval *teval,
- const struct traceeval_data *keys)
-{
- struct hash_table *hist = teval->hist;
- unsigned key = make_hash(teval, keys, hist->bits);
- struct entry *entry;
-
- entry = calloc(1, sizeof(*entry));
- if (!entry)
- return NULL;
-
- hash_add(hist, &entry->hash, key);
-
- return entry;
-}
-
static unsigned long long get_timestamp(struct traceeval *teval,
const struct traceeval_data *vals)
{
@@ -950,7 +885,7 @@ static int create_entry(struct traceeval *teval,
unsigned long long ts;
struct entry *entry;
- entry = create_hist_entry(teval, keys);
+ entry = calloc(1, sizeof(*entry));
if (!entry) {
teval_print_err(TEVAL_CRIT, "Failed to allocate histogram");
return -1;
@@ -976,6 +911,8 @@ static int create_entry(struct traceeval *teval,
entry->vals = new_vals;
entry->hitcount = 1;
+ teval_rbtree_insert(teval, &entry->node);
+
teval->update_counter++;
teval->nr_elements++;
@@ -1324,7 +1261,6 @@ int traceeval_insert_size(struct traceeval *teval,
int traceeval_remove_size(struct traceeval *teval,
const struct traceeval_data *keys, size_t nr_keys)
{
- struct hash_table *hist = teval->hist;
struct entry *entry;
int check;
@@ -1340,7 +1276,7 @@ int traceeval_remove_size(struct traceeval *teval,
if (check < 1)
return check;
- hash_remove(hist, &entry->hash);
+ teval_rbtree_delete(teval, &entry->node);
free_entry(teval, entry);
/* update_counter is used to know if there was an update. */
@@ -1384,22 +1320,22 @@ void traceeval_iterator_put(struct traceeval_iterator *iter)
static int create_iter_array(struct traceeval_iterator *iter)
{
struct traceeval *teval = iter->teval;
- struct hash_table *hist = teval->hist;
- struct hash_iter *hiter;
- struct hash_item *item;
+ struct teval_rbtree_node *node = NULL;
int i;
- iter->nr_entries = hash_nr_items(hist);
+ iter->nr_entries = teval->nr_elements;
iter->entries = calloc(iter->nr_entries, sizeof(*iter->entries));
if (!iter->entries) {
teval_print_err(TEVAL_CRIT, "Failed to allocate array");
return -1;
}
- for (i = 0, hiter = hash_iter_start(hist); (item = hash_iter_next(hiter)); i++) {
- struct entry *entry = container_of(item, struct entry, hash);
+ while ((node = teval_rbtree_next(teval, node))) {
+ struct entry *entry = container_of(node, struct entry, node);
- iter->entries[i] = entry;
+ if (i < iter->nr_entries)
+ iter->entries[i] = entry;
+ i++;
}
/* Loop must match entries */
@@ -1824,7 +1760,6 @@ struct traceeval_stat *traceeval_iterator_stat(struct traceeval_iterator *iter,
int traceeval_iterator_remove(struct traceeval_iterator *iter)
{
struct traceeval *teval = iter->teval;
- struct hash_table *hist = teval->hist;
struct entry *entry;
if (iter->next < 1 || iter->next > iter->nr_entries)
@@ -1834,7 +1769,7 @@ int traceeval_iterator_remove(struct traceeval_iterator *iter)
if (!entry)
return 0;
- hash_remove(hist, &entry->hash);
+ teval_rbtree_delete(teval, &entry->node);
free_entry(teval, entry);
/* The entry no longer exists */
new file mode 100644
@@ -0,0 +1,455 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright (C) 2023 Google, Steven Rostedt <rostedt@goodmis.org>
+ *
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include "eval-local.h"
+
+enum {
+ RED,
+ BLACK,
+};
+
+void __hidden teval_rbtree_init(struct traceeval *teval, teval_rbtree_cmp_fn cmp_fn,
+ teval_rbtree_search_fn search_fn)
+{
+ struct teval_rbtree *tree = &teval->tree;
+
+ memset(tree, 0, sizeof(*tree));
+ tree->search = search_fn;
+ tree->cmp = cmp_fn;
+}
+
+static bool is_left(struct teval_rbtree_node *node)
+{
+ return node == node->parent->left;
+}
+
+static struct teval_rbtree_node **get_parent_ptr(struct teval_rbtree *tree,
+ struct teval_rbtree_node *node)
+{
+ if (!node->parent)
+ return &tree->node;
+ else if (is_left(node))
+ return &node->parent->left;
+ else
+ return &node->parent->right;
+}
+
+static void rotate_left(struct teval_rbtree *tree,
+ struct teval_rbtree_node *node)
+{
+ struct teval_rbtree_node **parent_ptr = get_parent_ptr(tree, node);
+ struct teval_rbtree_node *parent = node->parent;
+ struct teval_rbtree_node *old_right = node->right;
+
+ *parent_ptr = old_right;
+ node->right = old_right->left;
+ old_right->left = node;
+
+ if (node->right)
+ node->right->parent = node;
+ node->parent = old_right;
+ old_right->parent = parent;
+}
+
+static void rotate_right(struct teval_rbtree *tree,
+ struct teval_rbtree_node *node)
+{
+ struct teval_rbtree_node **parent_ptr = get_parent_ptr(tree, node);
+ struct teval_rbtree_node *parent = node->parent;
+ struct teval_rbtree_node *old_left = node->left;
+
+ if (*parent_ptr != node)
+ breakpoint();
+ *parent_ptr = old_left;
+ node->left = old_left->right;
+ old_left->right = node;
+
+ if (node->left)
+ node->left->parent = node;
+ node->parent = old_left;
+ old_left->parent = parent;
+}
+
+static void insert_tree(struct traceeval *teval,
+ struct teval_rbtree_node *node)
+{
+ struct teval_rbtree *tree = &teval->tree;
+ struct teval_rbtree_node *next = tree->node;
+ struct teval_rbtree_node *last_next = NULL;
+ bool went_left = false;
+
+ while (next) {
+ last_next = next;
+ if (tree->cmp(teval, next, node) > 0) {
+ next = next->right;
+ went_left = false;
+ } else {
+ next = next->left;
+ went_left = true;
+ }
+ }
+
+ if (!last_next) {
+ tree->node = node;
+ return;
+ }
+
+ if (went_left)
+ last_next->left = node;
+ else
+ last_next->right = node;
+
+ node->parent = last_next;
+}
+
+static int check_node(struct teval_rbtree *tree, struct teval_rbtree_node *node)
+{
+ if (!node->parent) {
+ if (tree->node != node)
+ goto fail;
+ } else {
+ if (!is_left(node)) {
+ if (node->parent->right != node)
+ goto fail;
+ }
+ }
+ return 0;
+fail:
+ printf("FAILED ON NODE!");
+ breakpoint();
+ return -1;
+}
+
+static void check_tree(struct teval_rbtree *tree)
+{
+ struct teval_rbtree_node *node = tree->node;
+
+ if (node) {
+ if (check_node(tree, node))
+ return;
+ while (node->left) {
+ node = node->left;
+ if (check_node(tree, node))
+ return;
+ }
+ }
+
+ while (node) {
+ if (check_node(tree, node))
+ return;
+ if (node->right) {
+ node = node->right;
+ if (check_node(tree, node))
+ return;
+ while (node->left) {
+ node = node->left;
+ if (check_node(tree, node))
+ return;
+ }
+ continue;
+ }
+ while (node->parent) {
+ if (is_left(node))
+ break;
+ node = node->parent;
+ if (check_node(tree, node))
+ return;
+ }
+ node = node->parent;
+ }
+}
+
+int __hidden teval_rbtree_insert(struct traceeval *teval,
+ struct teval_rbtree_node *node)
+{
+ struct teval_rbtree *tree = &teval->tree;
+ struct teval_rbtree_node *uncle;
+
+ memset(node, 0, sizeof(*node));
+
+ insert_tree(teval, node);
+ node->color = RED;
+ while (node && node->parent && node->parent->color == RED) {
+ if (is_left(node->parent)) {
+ uncle = node->parent->parent->right;
+ if (uncle && uncle->color == RED) {
+ node->parent->color = BLACK;
+ uncle->color = BLACK;
+ node->parent->parent->color = RED;
+ node = node->parent->parent;
+ } else {
+ struct teval_rbtree_node old_pp = *node->parent->parent;
+ struct teval_rbtree_node old_p = *node->parent;
+ struct teval_rbtree_node old_node = *node;
+ if (!is_left(node)) {
+ node = node->parent;
+ rotate_left(tree, node);
+ check_tree(tree);
+ }
+ node->parent->color = BLACK;
+ node->parent->parent->color = RED;
+ rotate_right(tree, node->parent->parent);
+ if (old_node.parent == node->parent ||
+ old_p.parent == node ||
+ old_pp.parent == node)
+ check_tree(tree);
+ }
+ } else {
+ uncle = node->parent->parent->left;
+ if (uncle && uncle->color == RED) {
+ node->parent->color = BLACK;
+ uncle->color = BLACK;
+ node->parent->parent->color = RED;
+ node = node->parent->parent;
+ } else {
+ if (is_left(node)) {
+ node = node->parent;
+ rotate_right(tree, node);
+ check_tree(tree);
+ }
+ node->parent->color = BLACK;
+ node->parent->parent->color = RED;
+ rotate_left(tree, node->parent->parent);
+ check_tree(tree);
+ }
+ }
+ }
+ check_tree(tree);
+ tree->node->color = BLACK;
+ tree->nr_nodes++;
+ return 0;
+}
+
+__hidden struct teval_rbtree_node *
+teval_rbtree_find(struct traceeval *teval, const struct traceeval_data *keys)
+{
+ struct teval_rbtree *tree = &teval->tree;
+ struct teval_rbtree_node *node = tree->node;
+ int ret;
+
+ while (node) {
+ ret = tree->search(teval, node, keys);
+ if (!ret)
+ return node;
+ if (ret > 0)
+ node = node->right;
+ else
+ node = node->left;
+ }
+ return NULL;
+}
+
+static struct teval_rbtree_node *next_node(struct teval_rbtree_node *node)
+{
+ if (node->right) {
+ node = node->right;
+ while (node->left)
+ node = node->left;
+ return node;
+ }
+
+ while (node->parent && !is_left(node))
+ node = node->parent;
+
+ return node->parent;
+}
+
+static void tree_fixup(struct teval_rbtree *tree, struct teval_rbtree_node *node)
+{
+ while (node->parent && node->color == BLACK) {
+ if (is_left(node)) {
+ struct teval_rbtree_node *old_right = node->parent->right;
+
+ if (old_right->color == RED) {
+ old_right->color = BLACK;
+ node->parent->color = RED;
+ rotate_left(tree, node->parent);
+ old_right = node->parent->right;
+ }
+ if (old_right->left->color == BLACK &&
+ old_right->right->color == BLACK) {
+ old_right->color = RED;
+ node = node->parent;
+ } else {
+ if (old_right->right->color == BLACK) {
+ old_right->left->color = BLACK;
+ old_right->color = RED;
+ rotate_right(tree, old_right);
+ old_right = node->parent->right;
+ }
+ old_right->color = node->parent->color;
+ node->parent->color = BLACK;
+ old_right->right->color = BLACK;
+ rotate_left(tree, node->parent);
+ node = tree->node;
+ }
+ } else {
+ struct teval_rbtree_node *old_left = node->parent->left;
+
+ if (old_left->color == RED) {
+ old_left->color = BLACK;
+ node->parent->color = RED;
+ rotate_right(tree, node->parent);
+ old_left = node->parent->left;
+ }
+ if (old_left->right->color == BLACK &&
+ old_left->left->color == BLACK) {
+ old_left->color = RED;
+ node = node->parent;
+ } else {
+ if (old_left->left->color == BLACK) {
+ old_left->right->color = BLACK;
+ old_left->color = RED;
+ rotate_left(tree, old_left);
+ old_left = node->parent->left;
+ }
+ old_left->color = node->parent->color;
+ node->parent->color = BLACK;
+ old_left->left->color = BLACK;
+ rotate_right(tree, node->parent);
+ node = tree->node;
+ }
+ }
+ }
+ node->color = BLACK;
+}
+
+__hidden void teval_rbtree_delete(struct traceeval *teval,
+ struct teval_rbtree_node *node)
+{
+ struct teval_rbtree *tree = &teval->tree;
+ struct teval_rbtree_node *x, *y;
+ bool do_fixup = false;
+
+ if (!node->left && !node->right) {
+ tree->node = NULL;
+ goto out;
+ }
+
+ if (!node->left || !node->right)
+ y = node;
+ else
+ y = next_node(node);
+
+ if (y->left)
+ x = y->left;
+ else
+ x = y->right;
+
+ x->parent = y->parent;
+
+ if (!x->parent) {
+ tree->node = x;
+ } else {
+ if (is_left(y))
+ y->parent->left = x;
+ else
+ y->parent->right = x;
+ }
+
+ do_fixup = y->color == BLACK;
+
+ if (y != node) {
+ y->color = node->color;
+ y->parent = node->parent;
+ y->left = node->left;
+ y->right = node->right;
+ if (y->left)
+ y->left->parent = y;
+ if (y->right)
+ y->right->parent = y;
+ if (!y->parent) {
+ tree->node = y;
+ } else {
+ if (is_left(node))
+ y->parent->left = y;
+ else
+ y->parent->right = y;
+ }
+ }
+
+ if (do_fixup)
+ tree_fixup(tree, x);
+
+ out:
+ node->parent = node->left = node->right = NULL;
+ tree->nr_nodes--;
+}
+
+__hidden struct teval_rbtree_node *teval_rbtree_next(struct traceeval *teval,
+ struct teval_rbtree_node *node)
+{
+ struct teval_rbtree *tree = &teval->tree;
+ check_tree(tree);
+ /*
+ * When either starting or the previous iteration returned a
+ * node with a right branch, then go to the first node (if starting)
+ * or the right node, and then return the left most node.
+ */
+ if (!node || node->right) {
+ if (!node)
+ node = tree->node;
+ else
+ node = node->right;
+ while (node->left)
+ node = node->left;
+ return node;
+ }
+
+ /*
+ * If we are here, then the previous iteration returned the
+ * left most node of the tree or the right branch. If this
+ * is a left node, then simply return the parent. If this
+ * is a right node, then keep going up until its a left node,
+ * or we finished the iteration.
+ *
+ * If we are here and are the top node, then there is no right
+ * node, and this is finished (return NULL).
+ */
+ if (!node->parent || is_left(node))
+ return node->parent;
+
+ do {
+ node = node->parent;
+ } while (node->parent && !is_left(node));
+
+ return node->parent;
+}
+
+/*
+ * Used for freeing a tree, just quickly pop off the children in
+ * no particular order. This will corrupt the tree! That is,
+ * do not do any inserting or deleting of this tree after calling
+ * this function.
+ */
+__hidden struct teval_rbtree_node *
+teval_rbtree_pop_nobalance(struct traceeval *teval)
+{
+ struct teval_rbtree *tree = &teval->tree;
+ struct teval_rbtree_node *node = tree->node;
+
+ if (!node)
+ return NULL;
+
+ while (node->left)
+ node = node->left;
+
+ while (node->right)
+ node = node->right;
+
+ if (node->parent) {
+ if (is_left(node))
+ node->parent->left = NULL;
+ else
+ node->parent->right = NULL;
+ } else {
+ tree->node = NULL;
+ }
+
+ return node;
+}