Browse Source Download (without any required ccan dependencies)

Module:

avl

Summary:

Key-value dictionary based on AVL trees

Author:

Joey Adams <joeyadams3.14159@gmail.com>

Dependencies:

Description:

A simple, well-tested implementation of AVL trees for mapping unique keys to values. This implementation supports insertion, removal, lookup, and traversal.

An AVL tree is a self-balancing binary tree that performs insertion, removal, and lookup in O(log n) time per operation.

Example:

#include <ccan/avl/avl.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct tally {
     long count;
};
#define new_tally() calloc(1, sizeof(struct tally))

static void chomp(char *str)
{
     char *end = strchr(str, 0);
     if (end > str && end[-1] == '\n')
             end[-1] = 0;
}

int main(void)
{
     AVL          *avl = avl_new((total_order_noctx_cb) strcmp);
     AvlIter       i;
     struct tally *tally;
     char          line[256];
     
     while (fgets(line, sizeof(line), stdin))
     {
             chomp(line);
             
             tally = avl_lookup(avl, line);
             if (tally == NULL)
                     avl_insert(avl, strdup(line), tally = new_tally());
             
             tally->count++;
     }
     
     avl_foreach(i, avl) {
             char         *line  = i.key;
             struct tally *tally = i.value;
             
             printf("% 5ld: %s\n", tally->count, line);
             
             free(line);
             free(tally);
     }
     
     avl_free(avl);
     
     return 0;
}

License:

MIT