.TH AVLTREE 3 "20 November 1999"
.SH 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

.SH SYNOPSIS AND DESCRIPTION

The \fBAVLtree\fR library is a small, in-memory, non-recursive,
malloc-based index package that serves the same general purpose 
as B-trees and hash tables, \fIi.e.\fR a \fBkey\fR is used to obtain a
\fBpointer\fR (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):

.nf
    #define AVL_DEFAULTKEYLEN   (4 * sizeof(int))

    typedef struct {
        void            *recptr;
        unsigned int    count;
        char            key[AVL_DEFAULTKEYLEN]; 
                        /* can be of any length */
    } rectype;
.fi

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.

.nf
\fB\&#include <avltree.h>\fR
.P
\fBvoid avl_create_index(AVL_IX_DESC *pix, int dup, int keylength);\fR
.IP
Creates an index according to the \fIdup\fR parameter:
.nf

  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

.fi
If AVL_COUNT_DUPS is used, the \fBcount\fR field is filled in
on all successful searches; otherwise it is ignored.
If \fIkeylength\fR 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.
.P
\fBvoid avl_destroy_index(AVL_IX_DESC *pix);\fR
.IP
Destroys an index created with avl_create_index(), freeing all
the associated memory.
.P
\fBint avl_add_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);\fR
.IP
Add a key+recptr to the index according to index type.
.P
\fBint avl_find_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);\fR
.IP
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.
.P
\fBint avl_locate_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);\fR
.IP
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.
.P
\fBint avl_delete_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);\fR
.IP
Delete key in index.
.P
\fBint avl_first_key(AVL_IX_DESC *pix);\fR
.IP
Set index to first key.
.P
\fBint avl_last_key(AVL_IX_DESC *pix);\fR
.IP
Set index to last key.
.P
\fBint avl_next_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);\fR
.IP
Get next key in index.
.P
\fBint avl_prev_key(AVL_IX_REC *pe, AVL_IX_DESC *pix);\fR
.IP
Get previous key in index.
.P
\fBint avl_find_exact(AVL_IX_REC *pe, AVL_IX_DESC *pix);\fR
.IP
Find exact match (key+recptr).

.SH EXAMPLES

Example 1: using string indexing with the counting function to implement
the equivalent of:
.sp
\fB% sort text_file | uniq -c\fR
.P
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.

.nf
    #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 %s\n", pe->count, pe->key);

        if (ret != AVL_EOIX) {
            fprintf(stderr, "avl_next_key()\\n");
            exit(1);
        }
        exit(0);
    }
.fi

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.

.nf
        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)\n", *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)\n", *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)\n", *ip1, *ip2);
            exit(1);
        }
        if (avl_delete_key(&rec, &ix) != AVL_IX_OK) {
            fprintf(stderr, "avl_delete_key(%d %d)\n", *ip1, *ip2);
            exit(1);
        }
.fi

.SH 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.

.SH 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.