DragonFly On-Line Manual Pages
AVLTREE(3) DragonFly Library Functions Manual AVLTREE(3)
NAME
avl_create_index, avl_destroy_index, avl_find_key, avl_locate_key,
avl_add_key, avl_delete_key, avl_first_key, avl_last_key, avl_next_key,
avl_prev_key, avl_find_exact
SYNOPSIS AND DESCRIPTION
The AVLtree library is a small, in-memory, non-recursive, malloc-based
index package that serves the same general purpose as B-trees and hash
tables, i.e. a key is used to obtain a pointer (recptr) to something in
memory. Keys are either fixed-length binary fields, or variable-length
character strings. Indexes may be initialized to accept unique keys
only, or to allow duplicate keys. In the latter case, the recptr itself
is included for indexing purposes, allowing easy location of exact
index entries when keys are identical but recptrs are not (this is
convenient for deleting entries). Examples of use are provided below.
One advantage of AVLtree is that since it is all in memory, no pre-
dimensioning of resident space is required - keys can be added until
the process runs out of memory. The performance is apparently twice
that of dbopen(3) when the latter is dimensioned to index entirely in
memory, and on the order of twenty times faster when dbopen begins
paging to an index file.
The index structure AVL_IX_DESC is opaque to the user; the record
structure AVL_IX_REC is used to pass key/pointer pairs into and out of
the index. This structure must be sized according to the keys to be
used; a cast to a larger malloc()'d or stack buffer allows for larger
keys than the default AVL_IX_REC (see EXAMPLES below):
#define AVL_DEFAULTKEYLEN (4 * sizeof(int))
typedef struct {
void *recptr;
unsigned int count;
char key[AVL_DEFAULTKEYLEN];
/* can be of any length */
} rectype;
Routines return AVL_IX_OK when successful, AVL_IX_FAIL when there is an
error, and AVL_EOIX when a sequential operation reaches the end-of-
index.
#include <avltree.h>
void avl_create_index(AVL_IX_DESC *pix, int dup, int keylength);
Creates an index according to the dup parameter:
AVL_NO_DUP_KEYS repeated key not allowed
AVL_DUP_KEYS_OK repeated key+recptr not allowed
AVL_COUNT_DUPS repeated key+recptr allowed, count repetitions
If AVL_COUNT_DUPS is used, the count field is filled in on all
successful searches; otherwise it is ignored. If keylength is
0, variable-length, null-terminated strings are expected as
keys, otherwise fixed-length binary keys are used. When
duplicate keys are allowed, the keys are ordered by recptr.
void avl_destroy_index(AVL_IX_DESC *pix);
Destroys an index created with avl_create_index(), freeing all
the associated memory.
int avl_add_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);
Add a key+recptr to the index according to index type.
int avl_find_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);
Look up a key in the index. If key is found and index type is
AVL_COUNT_DUPS, the count is set in the AVL_IX_REC.
int avl_locate_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);
Look up a key in the index, allowing for partial matches (first
part of key). If there is no match, return AVL_EOIX; if a
partial match, AVL_IX_FAIL.
int avl_delete_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);
Delete key in index.
int avl_first_key(AVL_IX_DESC *pix);
Set index to first key.
int avl_last_key(AVL_IX_DESC *pix);
Set index to last key.
int avl_next_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);
Get next key in index.
int avl_prev_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);
Get previous key in index.
int avl_find_exact(AVL_IX_REC *pe, AVL_IX_DESC *pix);
Find exact match (key+recptr).
EXAMPLES
Example 1: using string indexing with the counting function to
implement the equivalent of:
% sort text_file | uniq -c
In this case, long keys are expected, so a buffer is used for the index
entry. (The unsafe gets() is used for simplicity of the example.) The
index is simply stuffed, then read sequentially to get the strings in
alphabetical order.
#include <stdio.h>
#include <avltree.h>
main()
{
AVL_IX_DESC ix;
char buf[1024]; /* for long keys */
AVL_IX_REC *pe;
int ret;
/** set up the record and create the index **/
pe = (AVL_IX_REC *) buf;
avl_create_index(&ix, AVL_COUNT_DUPS, 0);
/** read in all the keys and index them **/
while (gets(pe->key) != NULL) {
if (avl_add_key(pe, &ix) != AVL_IX_OK) {
fprintf(stderr, "avl_add_key(%s)\n", pe->key);
exit(1);
}
}
/** go through the keys in alphabetical order **/
avl_first_key(&ix);
while ((ret=avl_next_key(pe, &ix)) == AVL_IX_OK)
printf("%4d %s0, pe->count, pe->key);
if (ret != AVL_EOIX) {
fprintf(stderr, "avl_next_key()\n");
exit(1);
}
exit(0);
}
Example 2: indexing on two integers, with duplicate keys allowed; note
that the recptrs of entries with duplicate keys can point to different
objects. In this case, the AVL_DEFAULTKEYLEN of the AVL_IX_REC is
bigger than the keysize, so a simple record struct is used instead of
casting a pointer to a larger buffer.
AVL_IX_DESC ix;
AVL_IX_REC rec;
int *ip1, *ip2;
/** set up the record and create the index **/
ip1 = (int *) rec.key;
ip2 = ip1 + 1;
avl_create_index(&ix, AVL_DUP_KEYS_OK, 2 * sizeof(int));
...
/** insert a key pointing to some_struct **/
*ip1 = first_int;
*ip2 = second_int;
rec.recptr = (void *) &some_struct;
if (avl_add_key(&rec, &ix) != AVL_IX_OK) {
fprintf(stderr, "avl_add_key(%d %d)0, *ip1, *ip2);
exit(1);
}
...
/** look up a key and get the struct pointer **/
*ip1 = first_int;
*ip2 = second_int;
if (avl_find_key(&rec, &ix) != AVL_IX_OK) {
fprintf(stderr, "avl_find_key(%d %d)0, *ip1, *ip2);
exit(1);
}
structp = (struct_type *) rec.recptr;
...
/** look up an exact index entry and delete it **/
*ip1 = first_int;
*ip2 = second_int;
rec.recptr = (void *) &some_struct;
if (avl_find_exact(&rec, &ix) != AVL_IX_OK) {
fprintf(stderr, "avl_find_exact(%d %d)0, *ip1, *ip2);
exit(1);
}
if (avl_delete_key(&rec, &ix) != AVL_IX_OK) {
fprintf(stderr, "avl_delete_key(%d %d)0, *ip1, *ip2);
exit(1);
}
BUGS
The recptr component of the index entry is defined as void * in avl.h;
this can be changed to e.g. off_t if indexing into a file is desired.
HISTORY
The first version of this code was written in Algol 68 by Gregory
Tseytin (tseyting@acm.org) who later translated it to C. The
AVL_COUNT_DUPS option was added at the suggestion of Bill Ross
(bross@nas.nasa.gov), who also packaged the code for distribution.
20 November 1999 AVLTREE(3)