[igt-dev] [PATCH i-g-t 2/5] lib/igt_bst: Add a BST interface and an AVL implementation
Andrzej Turko
andrzej.turko at linux.intel.com
Wed Jul 28 15:12:04 UTC 2021
This adds an efficient binary search tree implementation
in order to support an allocator with best-fit strategy.
Signed-off-by: Andrzej Turko <andrzej.turko at linux.intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski at intel.com>
---
lib/igt_bst.c | 157 +++++++++++
lib/igt_bst.h | 69 +++++
lib/igt_bst_avl.c | 651 ++++++++++++++++++++++++++++++++++++++++++++++
lib/meson.build | 2 +
4 files changed, 879 insertions(+)
create mode 100644 lib/igt_bst.c
create mode 100644 lib/igt_bst.h
create mode 100644 lib/igt_bst_avl.c
diff --git a/lib/igt_bst.c b/lib/igt_bst.c
new file mode 100644
index 000000000..a24859213
--- /dev/null
+++ b/lib/igt_bst.c
@@ -0,0 +1,157 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#include "igt_bst.h"
+
+
+/**
+ * igt_bst_insert
+ * @bst: igt_bst pointer
+ * @value: a pointer value being inserted
+ * @key: the key under which the value should be stored
+ *
+ * Inserts a new value to the bst.
+ *
+ * Returns: a pointer to the newly created node.
+ */
+void *igt_bst_insert(struct igt_bst *bst, void *value, uint64_t key)
+{
+ return bst->insert(bst, value, key);
+}
+
+/**
+ * igt_bst_erase
+ * @bst: igt_bst pointer
+ * @nodeptr: a pointer to a node in the bst
+ *
+ * Erases the indicated node.
+ *
+ * Returns: the value associated with the
+ * erased node.
+ */
+void *igt_bst_erase(struct igt_bst *bst, void *nodeptr)
+{
+ return bst->erase(bst, nodeptr);
+}
+
+/**
+ * igt_bst_query_successor
+ * @bst: igt_bst pointer
+ * @key: an arbitrary key
+ *
+ * Among the elements currently present in the bst,
+ * finds the one with the smallest key not smaller than
+ * the given key.
+ *
+ * Returns: a value associated with the found element,
+ * NULL if all keys in the tree are smaller than the key
+ * parameter.
+ */
+void *igt_bst_query_successor(struct igt_bst *bst, uint64_t key)
+{
+ return bst->query_successor(bst, key);
+}
+
+/**
+ * igt_bst_query_successor
+ * Similar to igt_bst_query_predecessor, but looks for an
+ * element with the greatest key not exceeding the parameter.
+ */
+void *igt_bst_query_predecessor(struct igt_bst *bst, uint64_t key)
+{
+ return bst->query_predecessor(bst, key);
+}
+
+/**
+ * igt_bst_pop_successor
+ * Like igt_bst_query_successor, but also removes the
+ * found element from the bst.
+ */
+void *igt_bst_pop_successor(struct igt_bst *bst, uint64_t key)
+{
+ return bst->pop_successor(bst, key);
+}
+
+/**
+ * igt_bst_pop_predecessor
+ * Like igt_bst_query_predecessor, but also removes the
+ * found element from the bst.
+ */
+void *igt_bst_pop_predecessor(struct igt_bst *bst, uint64_t key)
+{
+ return bst->pop_predecessor(bst, key);
+}
+
+/* check whether the bst contains any elements */
+bool igt_bst_empty(struct igt_bst *bst)
+{
+ return bst->bst_empty(bst);
+}
+
+/* retrieve the value from the element in the bst given by the pointer to its node */
+void *igt_bst_get_value(struct igt_bst *bst, void *nodeptr)
+{
+ return bst->get_value(nodeptr);
+}
+
+/* retrieve the key from the element the bst given by the pointer to its node */
+uint64_t igt_bst_get_key(struct igt_bst *bst, void *nodeptr)
+{
+ return bst->get_key(nodeptr);
+}
+
+/**
+ * igt_bst_leftmost_entry
+ * @bst: igt_bst pointer
+ *
+ * Finds an element in the bst with the smallest key.
+ *
+ * Returns: a pointer to the found node,
+ * NULL if the bst is empty.
+ */
+void *igt_bst_leftmost_entry(struct igt_bst *bst)
+{
+ return bst->leftmost_entry(bst);
+}
+
+/**
+ * igt_bst_rightmost_entry
+ * See igt_bst_leftmost_entry.
+ */
+void *igt_bst_rightmost_entry(struct igt_bst *bst)
+{
+ return bst->rightmost_entry(bst);
+}
+
+/**
+ * igt_bst_next_entry
+ * @bst: igt_bst pointer
+ * @nodeptr: a pointer to a node in the bst
+ *
+ * Finds the next element in the bst in the
+ * nondecreasing order of keys.
+ * Can be used to iterate over all elements.
+ *
+ * Retuns: a pointer to the next node in the bst,
+ * NULL if nodeptr points to the last node.
+ */
+void *igt_bst_next_entry(struct igt_bst *bst, void *nodeptr)
+{
+ return bst->next_entry(nodeptr);
+}
+
+/**
+ * igt_bst_prev_entry
+ * Like igt_bst_next_entry, but returns the previous node.
+ */
+void *igt_bst_prev_entry(struct igt_bst *bst, void *nodeptr)
+{
+ return bst->prev_entry(nodeptr);
+}
+
+void igt_bst_free(struct igt_bst *bst)
+{
+ bst->bst_free(bst);
+}
diff --git a/lib/igt_bst.h b/lib/igt_bst.h
new file mode 100644
index 000000000..f54fca50c
--- /dev/null
+++ b/lib/igt_bst.h
@@ -0,0 +1,69 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#ifndef __IGT_BST_H
+#define __IGT_BST_H
+
+#include <stdint.h>
+#include <stdbool.h>
+
+/**
+ * SECTION: igt_bst
+ * @short_description: a binary search tree interface
+ * @title: IGT Bst
+ * @include: igt_bst.h
+ *
+ * This interface operates on binary rearch trees
+ * which store void pointers ordered by uint64_t keys.
+ */
+
+struct igt_bst {
+
+ /* private structure of the BST */
+ void *priv;
+
+ void* (*insert)(struct igt_bst *bst, void *value, uint64_t key);
+ void* (*erase)(struct igt_bst *bst, void *nodeptr);
+ void* (*pop_successor)(struct igt_bst *bst, uint64_t key);
+ void* (*pop_predecessor)(struct igt_bst *bst, uint64_t key);
+ void* (*query_successor)(struct igt_bst *bst, uint64_t key);
+ void* (*query_predecessor)(struct igt_bst *bst, uint64_t key);
+ bool (*bst_empty)(struct igt_bst *bst);
+ void* (*get_value)(void *nodeptr);
+ uint64_t (*get_key)(void *nodeptr);
+ void* (*leftmost_entry)(struct igt_bst *bst);
+ void* (*rightmost_entry)(struct igt_bst *bst);
+ void* (*next_entry)(void *nodeptr);
+ void* (*prev_entry)(void *nodeptr);
+ void (*bst_free)(struct igt_bst *bst);
+ int (*validate)(struct igt_bst *bst);
+};
+
+/* contructors */
+struct igt_bst *igt_bst_avl_create(void);
+
+#define igt_bst_for_each_node(bst, nodeptr) \
+ for ((nodeptr) = (bst)->leftmost_entry(bst); (nodeptr); (nodeptr) = (bst)->next_entry(nodeptr))
+
+#define igt_bst_for_each_node_rev(bst, nodeptr) \
+ for ((nodeptr) = (bst)->rightmost_entry(bst); (nodeptr); (nodeptr) = (bst)->prev_entry(nodeptr))
+
+
+void *igt_bst_insert(struct igt_bst *bst, void *value, uint64_t key);
+void *igt_bst_erase(struct igt_bst *bst, void *nodeptr);
+void *igt_bst_query_successor(struct igt_bst *bst, uint64_t key);
+void *igt_bst_query_predecessor(struct igt_bst *bst, uint64_t key);
+void *igt_bst_pop_successor(struct igt_bst *bst, uint64_t key);
+void *igt_bst_pop_predecessor(struct igt_bst *bst, uint64_t key);
+bool igt_bst_empty(struct igt_bst *bst);
+void *igt_bst_get_value(struct igt_bst *bst, void *nodeptr);
+uint64_t igt_bst_get_key(struct igt_bst *bst, void *nodeptr);
+void *igt_bst_leftmost_entry(struct igt_bst *bst);
+void *igt_bst_rightmost_entry(struct igt_bst *bst);
+void *igt_bst_next_entry(struct igt_bst *bst, void *nodeptr);
+void *igt_bst_prev_entry(struct igt_bst *bst, void *nodeptr);
+void igt_bst_free(struct igt_bst *bst);
+
+#endif /* IGT_BST_H */
diff --git a/lib/igt_bst_avl.c b/lib/igt_bst_avl.c
new file mode 100644
index 000000000..7245a798d
--- /dev/null
+++ b/lib/igt_bst_avl.c
@@ -0,0 +1,651 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2021 Intel Corporation
+ */
+
+#include "igt.h"
+#include "igt_bst.h"
+
+//#define AVLDBG
+#ifdef AVLDBG
+#define avl_debug(...) fprintf(stderr, __VA_ARGS__)
+#define avl_assert igt_assert
+#define avl_assert_f igt_assert_f
+#else
+#define avl_debug(...) {}
+#define avl_assert(...) {}
+#define avl_assert_f(...) {}
+#endif
+
+struct igt_avl_node {
+ uint64_t key;
+
+ struct igt_avl_node *left;
+ struct igt_avl_node *right;
+ struct igt_avl_node *parent;
+
+ int32_t height;
+
+ void *value;
+};
+
+struct igt_avl {
+ struct igt_avl_node *root;
+};
+
+static int __traverse_validate(struct igt_avl_node *node)
+{
+ int32_t node_balance, left_h, right_h;
+ int n = 1;
+
+ igt_assert(node);
+
+ left_h = 0;
+ right_h = 0;
+
+ avl_debug("at 0x%llx : < key %llu, value 0x%llx >\nleft 0x%llx ; right 0x%llx\n",
+ (unsigned long long)node,
+ (unsigned long long)node->key,
+ (unsigned long long)node->value,
+ (unsigned long long)node->left,
+ (unsigned long long)node->right);
+
+ if (node->left) {
+ igt_assert(node->left->parent == node);
+ igt_assert_f(node->key >= node->left->key,
+ "The order of keys is not preserved in the AVL tree");
+ left_h = node->left->height;
+ n += __traverse_validate(node->left);
+ }
+
+ if (node->right) {
+ igt_assert(node->right->parent == node);
+ igt_assert_f(node->right->key >= node->key,
+ "The order of keys is not preserved in the AVL tree");
+ right_h = node->right->height;
+ n += __traverse_validate(node->right);
+ }
+
+ node_balance = left_h - right_h;
+ igt_assert(node_balance <= 1 && node_balance >= -1);
+ igt_assert(node->height == (left_h > right_h ? left_h : right_h) + 1);
+
+ return n;
+}
+
+static int avl_validate(struct igt_bst *bst)
+{
+ struct igt_avl *avl = bst->priv;
+
+ avl_debug("Tree traversal:\n");
+
+ /* an empty tree */
+ if (avl->root == NULL)
+ return 0;
+
+ igt_assert(!avl->root->parent);
+ return __traverse_validate(avl->root);
+}
+
+/* fix balance of all vertices from the given node to the root */
+static inline void __avl_fix_balance(struct igt_avl *avl, struct igt_avl_node *node)
+{
+ struct igt_avl_node *left, *right, *l_left, *l_right, *r_left, *r_right;
+ int32_t left_h, right_h, l_left_h, l_right_h, r_left_h, r_right_h;
+ int32_t balance, node_h;
+
+ while (node) {
+
+ node_h = node->height;
+ left = node->left;
+ left_h = (left ? left->height : 0);
+ right = node->right;
+ right_h = (right ? right->height : 0);
+ balance = left_h - right_h;
+
+ avl_debug("Correcting a node with key %llu at 0x%llx (%llu)\n",
+ (unsigned long long)node->key,
+ (unsigned long long)node,
+ *((unsigned long long *)node->value));
+ avl_debug("Heights: %d [%d %d] : balance %d\n",
+ node_h, left_h, right_h, balance);
+
+ if (balance > 1) {
+ avl_assert(balance == 2);
+ avl_assert(left);
+
+ /* 1st case: left son's subtree is too high */
+ l_left = left->left;
+ l_left_h = (l_left ? l_left->height : 0);
+ l_right = left->right;
+ l_right_h = (l_right ? l_right->height : 0);
+
+ if (l_right_h > l_left_h) {
+ avl_assert(l_right_h == right_h + 1);
+ avl_assert(l_left_h == right_h);
+ avl_assert(l_right);
+
+ /*
+ * left son's (left's) right son (l_right) is too high,
+ * rotate the left son and its right son
+ *
+ * N N N
+ * / / /
+ * L (rotate) LR (rename) L
+ * / \ -----> / \ -----> / \
+ * LL LR L LRR LL LR
+ * / \ / \
+ * LRL LRR LL LRL
+ *
+ */
+
+ left->right = l_right->left;
+ if (l_right->left)
+ l_right->left->parent = left;
+ l_right->parent = node;
+ node->left = l_right;
+ l_right->left = left;
+ left->parent = l_right;
+
+ l_left = left;
+ left = l_right;
+ l_right = l_right->right;
+
+ l_left_h = --l_left->height;
+ l_right_h = (l_right ? l_right->height : 0);
+ left_h = ++left->height;
+ }
+
+ avl_assert(left);
+ avl_assert(left_h == right_h + 2);
+ avl_assert(l_left_h == right_h + 1);
+
+ /*
+ * rotate the node and its left son
+ *
+ * | | |
+ * N (rotate) L (rename) N
+ * / \ -----> / \ -----> / \
+ * L R LL N ... ...
+ * / \ / \
+ * LL LR LR R
+ *
+ */
+
+ node->left = l_right;
+ if (l_right)
+ l_right->parent = node;
+ left->parent = node->parent;
+ if (node->parent) {
+ if (node->parent->left == node)
+ node->parent->left = left;
+ else
+ node->parent->right = left;
+
+ } else {
+ avl->root = left;
+ }
+ node->parent = left;
+ left->right = node;
+
+ node->height = (l_right_h > right_h ? l_right_h : right_h) + 1;
+ left->height = (node->height > l_left_h ? node->height : l_left_h) + 1;
+
+ node = left;
+ }
+
+
+ if (balance < -1) {
+ avl_assert(balance == -2);
+ avl_assert(right);
+
+ /* 2nd case: right son's subtree is too high */
+ r_left = right->left;
+ r_left_h = (r_left ? r_left->height : 0);
+ r_right = right->right;
+ r_right_h = (r_right ? r_right->height : 0);
+
+ if (r_left_h > r_right_h) {
+ avl_assert(r_left_h == left_h + 1);
+ avl_assert(r_right_h == left_h);
+ avl_assert(r_left);
+
+ /*
+ * right son's (right's) left son (r_left) is too high,
+ * rotate the right son and its left son.
+ *
+ * N N N
+ * \ \ \
+ * R (rotate) RL (rename) R
+ * / \ -----> / \ -----> / \
+ * RL RR RLL R RL RR
+ * / \ / \
+ * RLL RLR RLR RR
+ *
+ */
+
+ right->left = r_left->right;
+ if (r_left->right)
+ r_left->right->parent = right;
+ r_left->parent = node;
+ node->right = r_left;
+ r_left->right = right;
+ right->parent = r_left;
+
+ r_right = right;
+ right = r_left;
+ r_left = r_left->left;
+
+ r_right_h = --r_right->height;
+ r_left_h = (r_left ? r_left->height : 0);
+ right_h = ++right->height;
+ }
+
+ avl_assert(right);
+ avl_assert(right_h == left_h + 2);
+ avl_assert(r_right_h == left_h + 1);
+
+ /*
+ * rotate the node and its right son
+ *
+ * | | |
+ * N (rotate) R (rename) N
+ * / \ -----> / \ -----> / \
+ * L R N RR ... ...
+ * / \ / \
+ * RL RR L RL
+ *
+ */
+
+ node->right = r_left;
+ if (r_left)
+ r_left->parent = node;
+ right->parent = node->parent;
+ if (node->parent) {
+ if (node->parent->left == node)
+ node->parent->left = right;
+ else
+ node->parent->right = right;
+
+ } else {
+ avl->root = right;
+ }
+ node->parent = right;
+ right->left = node;
+
+ node->height = (r_left_h > left_h ? r_left_h : left_h) + 1;
+ right->height = (node->height > r_right_h ? node->height : r_right_h) + 1;
+
+ node = right;
+ }
+
+ if (balance >= -1 && balance <= 1)
+ node->height = (left_h > right_h ? left_h : right_h) + 1;
+
+ avl_assert(node->height - node_h >= -1 && node->height - node_h <= 1);
+
+ if (node->height == node_h)
+ break;
+
+ node = node->parent;
+ }
+}
+
+static void *avl_insert(struct igt_bst *bst, void *value, uint64_t key)
+{
+ struct igt_avl *avl = bst->priv;
+ struct igt_avl_node *node, *parent;
+
+ node = avl->root;
+ parent = NULL;
+ while (node) {
+ parent = node;
+ if (key < node->key)
+ node = node->left;
+ else
+ node = node->right;
+ }
+
+ node = malloc(sizeof(struct igt_avl_node));
+ igt_assert(node);
+ node->key = key;
+ node->parent = parent;
+ node->left = NULL;
+ node->right = NULL;
+ node->height = 1;
+ node->value = value;
+ if (parent) {
+ if (key < parent->key)
+ parent->left = node;
+ else
+ parent->right = node;
+
+ __avl_fix_balance(avl, parent);
+ } else {
+ avl->root = node;
+ }
+
+ return node;
+}
+
+static inline void
+__avl_erase_node(struct igt_avl *avl, struct igt_avl_node *node,
+ struct igt_avl_node *del_pos)
+{
+ struct igt_avl_node *parent, *son;
+
+ avl_assert(node);
+ avl_assert(del_pos);
+ avl_assert(!del_pos->left || !del_pos->right);
+ son = (del_pos->left ? del_pos->left : del_pos->right);
+ parent = del_pos->parent;
+
+ avl_debug("Erasing node 0x%llx with position 0x%llx\n",
+ (unsigned long long)node, (unsigned long long)del_pos);
+
+ if (node != del_pos) {
+ /* move a node from the deleted position
+ * to place of the deleted node
+ */
+
+ del_pos->left = node->left;
+ if (del_pos->left)
+ del_pos->left->parent = del_pos;
+ del_pos->right = node->right;
+ if (del_pos->right)
+ del_pos->right->parent = del_pos;
+
+ del_pos->parent = node->parent;
+ if (node->parent) {
+ if (node->parent->left == node)
+ node->parent->left = del_pos;
+ else
+ node->parent->right = del_pos;
+
+ } else {
+ avl->root = del_pos;
+ }
+
+ del_pos->height = node->height;
+
+ if (parent == node)
+ parent = del_pos;
+
+ }
+
+ if (son)
+ son->parent = parent;
+
+ if (parent) {
+ if (parent->left == del_pos)
+ parent->left = son;
+ else
+ parent->right = son;
+
+ __avl_fix_balance(avl, parent);
+ } else {
+ avl->root = son;
+ }
+
+ avl_assert(del_pos->parent != del_pos);
+
+ free(node);
+}
+
+static void *avl_erase(struct igt_bst *bst, void *nodeptr)
+{
+ struct igt_avl_node *node, *del_pos;
+ void *value;
+
+ igt_assert(nodeptr);
+ node = (struct igt_avl_node *) nodeptr;
+ value = node->value;
+ del_pos = node->left;
+ if (del_pos) {
+ while (del_pos->right)
+ del_pos = del_pos->right;
+
+ __avl_erase_node(bst->priv, node, del_pos);
+ } else {
+ __avl_erase_node(bst->priv, node, node);
+ }
+
+ return value;
+}
+
+static void *avl_pop_successor(struct igt_bst *bst, uint64_t key)
+{
+ struct igt_avl *avl = bst->priv;
+ struct igt_avl_node *node, *succ, *parent;
+ void *value;
+
+ node = avl->root;
+ parent = NULL;
+ succ = NULL;
+ while (node) {
+ parent = node;
+ if (node->key >= key) {
+ succ = node;
+ node = node->left;
+ } else {
+ node = node->right;
+ }
+ }
+
+ if (!succ)
+ return NULL;
+
+ value = succ->value;
+ __avl_erase_node(avl, succ, parent);
+
+ return value;
+}
+
+static void *avl_pop_predecessor(struct igt_bst *bst, uint64_t key)
+{
+ struct igt_avl *avl = bst->priv;
+ struct igt_avl_node *node, *parent, *pred;
+ void *value;
+
+ node = avl->root;
+ parent = NULL;
+ pred = NULL;
+ while (node) {
+ parent = node;
+ if (node->key <= key) {
+ pred = node;
+ node = node->right;
+ } else {
+ node = node->left;
+ }
+ }
+
+ if (!pred)
+ return NULL;
+
+ value = pred->value;
+ __avl_erase_node(avl, pred, parent);
+
+ return value;
+}
+
+static void *avl_query_successor(struct igt_bst *bst, uint64_t key)
+{
+ struct igt_avl *avl = bst->priv;
+ struct igt_avl_node *node;
+ void *value = NULL;
+
+ node = avl->root;
+ while (node) {
+ if (node->key >= key) {
+ value = node->value;
+ node = node->left;
+ } else {
+ node = node->right;
+ }
+ }
+
+ return value;
+}
+
+static void *avl_query_predecessor(struct igt_bst *bst, uint64_t key)
+{
+ struct igt_avl *avl = bst->priv;
+ struct igt_avl_node *node;
+ void *value = NULL;
+
+ node = avl->root;
+ while (node) {
+ if (node->key <= key) {
+ value = node->value;
+ node = node->right;
+ } else {
+ node = node->left;
+ }
+ }
+
+ return value;
+}
+
+static bool avl_bst_empty(struct igt_bst *bst)
+{
+ struct igt_avl *avl = bst->priv;
+
+ return (avl->root == NULL);
+}
+
+
+static void *avl_get_value(void *nodeptr)
+{
+ return ((struct igt_avl_node *)nodeptr)->value;
+}
+
+static uint64_t avl_get_key(void *nodeptr)
+{
+ return ((struct igt_avl_node *)nodeptr)->key;
+}
+
+static void *avl_leftmost_entry(struct igt_bst *bst)
+{
+ struct igt_avl *avl = bst->priv;
+ struct igt_avl_node *node;
+
+ node = avl->root;
+ if (node) {
+ while (node->left)
+ node = node->left;
+ }
+
+ return node;
+}
+
+static void *avl_rightmost_entry(struct igt_bst *bst)
+{
+ struct igt_avl *avl = bst->priv;
+ struct igt_avl_node *node;
+
+ node = avl->root;
+ if (node) {
+ while (node->right)
+ node = node->right;
+ }
+ return node;
+}
+
+static void *avl_next_entry(void *nodeptr)
+{
+ struct igt_avl_node *node;
+
+ igt_assert(nodeptr);
+ node = (struct igt_avl_node *) nodeptr;
+ if (node->right) {
+ node = node->right;
+ while (node->left)
+ node = node->left;
+
+ return node;
+ }
+ while (node->parent) {
+ if (node->parent->left == node)
+ return node->parent;
+
+ node = node->parent;
+ }
+ return NULL;
+}
+
+static void *avl_prev_entry(void *nodeptr)
+{
+ struct igt_avl_node *node;
+
+ igt_assert(nodeptr);
+ node = (struct igt_avl_node *) nodeptr;
+ if (node->left) {
+ node = node->left;
+ while (node->right)
+ node = node->right;
+
+ return node;
+ }
+ while (node->parent) {
+ if (node->parent->right == node)
+ return node->parent;
+
+ node = node->parent;
+ }
+ return NULL;
+}
+
+static void __avl_free(struct igt_avl_node *node)
+{
+ avl_assert(node);
+
+ if (node->left)
+ __avl_free(node->left);
+
+ if (node->right)
+ __avl_free(node->right);
+
+ free(node);
+}
+
+static void avl_bst_free(struct igt_bst *bst)
+{
+ struct igt_avl *avl = bst->priv;
+
+ if (avl->root)
+ __avl_free(avl->root);
+
+ free(avl);
+}
+
+struct igt_bst *igt_bst_avl_create(void)
+{
+ struct igt_avl *avl;
+ struct igt_bst *bst;
+
+ avl = malloc(sizeof(struct igt_avl));
+ bst = malloc(sizeof(struct igt_bst));
+ igt_assert(avl);
+ igt_assert(bst);
+
+ avl->root = NULL;
+ bst->priv = avl;
+ bst->insert = avl_insert;
+ bst->erase = avl_erase;
+ bst->pop_successor = avl_pop_successor;
+ bst->pop_predecessor = avl_pop_predecessor;
+ bst->query_successor = avl_query_successor;
+ bst->query_predecessor = avl_query_predecessor;
+ bst->bst_empty = avl_bst_empty;
+ bst->get_value = avl_get_value;
+ bst->get_key = avl_get_key;
+ bst->leftmost_entry = avl_leftmost_entry;
+ bst->rightmost_entry = avl_rightmost_entry;
+ bst->next_entry = avl_next_entry;
+ bst->prev_entry = avl_prev_entry;
+ bst->bst_free = avl_bst_free;
+ bst->validate = avl_validate;
+
+ return bst;
+}
diff --git a/lib/meson.build b/lib/meson.build
index 67d405129..a1aa0ee12 100644
--- a/lib/meson.build
+++ b/lib/meson.build
@@ -11,6 +11,8 @@ lib_sources = [
'i915/gem_mman.c',
'i915/gem_vm.c',
'i915/intel_memory_region.c',
+ 'igt_bst.c',
+ 'igt_bst_avl.c',
'igt_collection.c',
'igt_color_encoding.c',
'igt_debugfs.c',
--
2.25.1
More information about the igt-dev
mailing list