[igt-dev] [PATCH i-g-t 2/4] lib/igt_bst: Add a BST interface and an AVL implementation

[Andrzej Turko <andrzej.turko@linux.intel.com>]

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@linux.intel.com>
Cc: Zbigniew Kempczyński <zbigniew.kempczynski@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

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev