A high performance generic AVL-tree container C implementation.
It can be used as a set or a map, containing any type of data.
Jung-Sang Ahn [email protected]
$ make(refer to example/avl_example.c)
Below example describes how to use AVL-tree as an ordered map of integer pairs.
We define a node for an integer pair, and a comparison function of given two nodes:
#include "avltree.h"
struct kv_node{
struct avl_node avl;
// put your data here
int key;
int value;
};
int cmp_func(struct avl_node *a, struct avl_node *b, void *aux)
{
struct node *aa, *bb;
aa = _get_entry(a, struct kv_node, avl);
bb = _get_entry(b, struct kv_node, avl);
if (aa->key < bb->key)
return -1;
else if (aa->key > bb->key)
return 1;
else
return 0;
}Example code:
- Initialize tree
struct avl_tree tree;
avl_init(&tree, NULL);- Insert
{1, 10}pair
struct kv_node *node;
node = (struct kv_node*)malloc(sizeof(struct kv_node));
node->key = 1;
node->value = 10;
avl_insert(&tree, &node->avl, cmp_func);- Insert
{2, 20}pair
struct kv_node *node;
node = (struct kv_node*)malloc(sizeof(struct kv_node));
node->key = 2;
node->value = 20;
avl_insert(&tree, &node->avl, cmp_func);- Find the value corresponding to key
1
struct kv_node query;
struct kv_node *node;
struct avl_node *cursor;
query.key = 1;
cursor = avl_search(&tree, &query.avl, cmp_func);
// get 'node' from 'cursor'
node = _get_entry(cursor, struct kv_node, avl);
printf("%d\n", node->value); // it will display 10- Iteration
struct kv_node *node;
struct avl_node *cursor;
cursor = avl_first(&tree);
while (cursor) {
// get 'node' from 'cursor'
node = _get_entry(cursor, struct kv_node, avl);
// ... do something with 'node' ...
// get next cursor
cursor = avl_next(cursor);
}- Remove the key-value pair corresponding to key
1
struct kv_node query;
struct kv_node *node;
struct avl_node *cursor;
query.key = 1;
cursor = avl_search(&tree, &query.avl, cmp_func);
if (cursor) {
// get 'node' from 'cursor'
node = _get_entry(cursor, struct kv_node, avl);
// remove from tree
avl_remove(&tree, cursor);
// free 'node'
free(node);
}$ ./avl_benchEstimated the throughput of primitive operations compared to RB-tree implementation in Linux kernel source code archive and 'set' in STL. Total 10M key-value pairs are used on a machine equipped with i7-3770 CPU (3.4GHz, 4-core 8-thread). The results are averaged over 5 runs, discarding the maximum and the minimum values.
Overall, this AVL-tree implementation is up to 3x faster than STL set (or map).
- Throughput (absolute number)
- Throughput (normalized to STL set)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent