Skip to content

Instantly share code, notes, and snippets.

@basinilya
Last active July 4, 2017 17:25
Show Gist options
  • Save basinilya/70c0515200358e9f44f62b8f49bef898 to your computer and use it in GitHub Desktop.
Save basinilya/70c0515200358e9f44f62b8f49bef898 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <sys/types.h>
#include <string.h>
#include <stdlib.h>
#include <glib.h>
/* opaque glib structures */
typedef struct _GTreeNode GTreeNode;
struct _GTree
{
GTreeNode *root;
GCompareDataFunc key_compare;
GDestroyNotify key_destroy_func;
GDestroyNotify value_destroy_func;
gpointer key_compare_data;
guint nnodes;
gint ref_count;
};
struct _GTreeNode
{
gpointer key; /* key for this node */
gpointer value; /* value stored at this node */
GTreeNode *left; /* left subtree */
GTreeNode *right; /* right subtree */
gint8 balance; /* height (right) - height (left) */
guint8 left_child;
guint8 right_child;
};
static inline GTreeNode *
g_tree_last_node(GTree *tree)
{
GTreeNode *tmp;
if (!tree->root)
return NULL;
tmp = tree->root;
while (tmp->right_child)
tmp = tmp->right;
return tmp;
}
typedef enum {
FIND_EXACT = 0,
FIND_FLOOR = 0x2,
FIND_CEIL = 0x20,
FIND_LOWER = (FIND_FLOOR + 1),
FIND_HIGHER = (FIND_CEIL + 1)
} find_mode;
static GTreeNode *
g_tree_find_node_ex (GTree *tree,
gconstpointer key,
GCompareDataFunc key_compare,
find_mode mode
)
{
GTreeNode *node;
gint cmp;
GTreeNode *last_lesser_node = NULL;
GTreeNode *last_greater_node = NULL;
node = tree->root;
if (!node)
return NULL;
while (1)
{
cmp = key_compare (key, node->key, tree->key_compare_data);
if (cmp == 0) {
if (mode == FIND_LOWER) {
cmp = -1;
} else if (mode == FIND_HIGHER) {
cmp = 1;
} else {
return node;
}
}
if (cmp < 0)
{
if (!node->left_child) {
if ( (mode & FIND_FLOOR) ) {
return last_lesser_node; /* can be null */
}
if ( (mode & FIND_CEIL) ) {
return node;
}
return NULL;
}
last_greater_node = node;
node = node->left;
}
else
{
if (!node->right_child) {
if ( (mode & FIND_CEIL) ) {
return last_greater_node; /* can be null */
}
if ( (mode & FIND_FLOOR) ) {
return node;
}
return NULL;
}
last_lesser_node = node;
node = node->right;
}
}
}
#ifdef GTREEEX_DEBUG
static
gint compare_int(gconstpointer p1, gconstpointer p2) {
int i1 = GPOINTER_TO_INT(p1);
int i2 = GPOINTER_TO_INT(p2);
/* printf("%d %d\n", i1, i2); */
return i1 == i2 ? 0 : i1 > i2 ? 1 : -1;
}
static inline char *node_key(GTreeNode *node, char buf[11]) {
return node ? (sprintf(buf, "%d", GPOINTER_TO_INT(node->key)),buf) : "NULL";
}
static GTree *tree;
static inline void put(int key, int val) {
g_tree_insert(tree, GINT_TO_POINTER(key), GINT_TO_POINTER(key));
}
static inline GTreeNode *get(int key) {
return g_tree_find_node_ex(tree, GINT_TO_POINTER(key), tree->key_compare, FIND_EXACT);
}
static gint always_gt(gconstpointer a, gconstpointer b, gpointer user_data) {
return 1;
}
static gint always_lt(gconstpointer a, gconstpointer b, gpointer user_data) {
return -1;
}
static inline GTreeNode *lastKey() {
return g_tree_find_node_ex(tree, NULL, always_gt, FIND_FLOOR);
}
static inline GTreeNode *firstKey() {
return g_tree_find_node_ex(tree, NULL, always_lt, FIND_CEIL);
}
static inline GTreeNode *floorKey(int key) {
return g_tree_find_node_ex(tree, GINT_TO_POINTER(key), tree->key_compare, FIND_FLOOR);
}
static inline GTreeNode *lowerKey(int key) {
return g_tree_find_node_ex(tree, GINT_TO_POINTER(key), tree->key_compare, FIND_LOWER);
}
static inline GTreeNode *higherKey(int key) {
return g_tree_find_node_ex(tree, GINT_TO_POINTER(key), tree->key_compare, FIND_HIGHER);
}
static inline GTreeNode *ceilingKey(int key) {
return g_tree_find_node_ex(tree, GINT_TO_POINTER(key), tree->key_compare, FIND_CEIL);
}
static inline void _assertEquals(int line, int expected, GTreeNode *actual_node) {
char buf[11];
if (actual_node && GINT_TO_POINTER(expected) == actual_node->key) return;
printf(":%d expected: %d actual: %s\n", line, expected, node_key(actual_node, buf));
exit(1);
}
static inline void _assertNull(int line, GTreeNode *actual_node) {
char buf[11];
if (!actual_node) return;
printf(":%d expected: NULL actual: %s\n", line, node_key(actual_node, buf));
exit(1);
}
#define assertNull(actual_node) _assertNull(__LINE__, actual_node)
#define assertEquals(expected, actual_node) _assertEquals(__LINE__, expected, actual_node)
int main(int argc, char *argv[]) {
int i;
tree = g_tree_new(compare_int);
for (i = -7; i <= 7; i += 2) {
put(i, i);
}
assertEquals(-7, firstKey());
assertEquals(7, lastKey());
assertNull(get(-8));
assertNull(floorKey(-8));
assertEquals(-7, ceilingKey(-8));
assertNull(lowerKey(-8));
assertEquals(-7, higherKey(-8));
assertEquals(-7, get(-7));
assertEquals(-7, floorKey(-7));
assertEquals(-7, ceilingKey(-7));
assertNull(lowerKey(-7));
assertEquals(-5, higherKey(-7));
assertNull(get(-6));
assertEquals(-7, floorKey(-6));
assertEquals(-5, ceilingKey(-6));
assertEquals(-7, lowerKey(-6));
assertEquals(-5, higherKey(-6));
assertEquals(-5, get(-5));
assertEquals(-5, floorKey(-5));
assertEquals(-5, ceilingKey(-5));
assertEquals(-7, lowerKey(-5));
assertEquals(-3, higherKey(-5));
assertNull(get(-4));
assertEquals(-5, floorKey(-4));
assertEquals(-3, ceilingKey(-4));
assertEquals(-5, lowerKey(-4));
assertEquals(-3, higherKey(-4));
assertEquals(-3, get(-3));
assertEquals(-3, floorKey(-3));
assertEquals(-3, ceilingKey(-3));
assertEquals(-5, lowerKey(-3));
assertEquals(-1, higherKey(-3));
assertNull(get(-2));
assertEquals(-3, floorKey(-2));
assertEquals(-1, ceilingKey(-2));
assertEquals(-3, lowerKey(-2));
assertEquals(-1, higherKey(-2));
assertEquals(-1, get(-1));
assertEquals(-1, floorKey(-1));
assertEquals(-1, ceilingKey(-1));
assertEquals(-3, lowerKey(-1));
assertEquals(1, higherKey(-1));
assertNull(get(0));
assertEquals(-1, floorKey(0));
assertEquals(1, ceilingKey(0));
assertEquals(-1, lowerKey(0));
assertEquals(1, higherKey(0));
assertEquals(1, get(1));
assertEquals(1, floorKey(1));
assertEquals(1, ceilingKey(1));
assertEquals(-1, lowerKey(1));
assertEquals(3, higherKey(1));
assertNull(get(2));
assertEquals(1, floorKey(2));
assertEquals(3, ceilingKey(2));
assertEquals(1, lowerKey(2));
assertEquals(3, higherKey(2));
assertEquals(3, get(3));
assertEquals(3, floorKey(3));
assertEquals(3, ceilingKey(3));
assertEquals(1, lowerKey(3));
assertEquals(5, higherKey(3));
assertNull(get(4));
assertEquals(3, floorKey(4));
assertEquals(5, ceilingKey(4));
assertEquals(3, lowerKey(4));
assertEquals(5, higherKey(4));
assertEquals(5, get(5));
assertEquals(5, floorKey(5));
assertEquals(5, ceilingKey(5));
assertEquals(3, lowerKey(5));
assertEquals(7, higherKey(5));
assertNull(get(6));
assertEquals(5, floorKey(6));
assertEquals(7, ceilingKey(6));
assertEquals(5, lowerKey(6));
assertEquals(7, higherKey(6));
assertEquals(7, get(7));
assertEquals(7, floorKey(7));
assertEquals(7, ceilingKey(7));
assertEquals(5, lowerKey(7));
assertNull(higherKey(7));
assertNull(get(8));
assertEquals(7, floorKey(8));
assertNull(ceilingKey(8));
assertEquals(7, lowerKey(8));
assertNull(higherKey(8));
printf("PASSED\n");
return 0;
}
#endif /* GTREEEX_DEBUG */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment