avltree man page on DragonFly

Man page or keyword search:  
man Server   44335 pages
apropos Keyword Search (all sections)
Output format
DragonFly logo
[printable version]

AVLTREE(3)							    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 con‐
       venient 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 pag‐
       ing 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 dupli‐
	      cate 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 par‐
	      tial 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	imple‐
       ment 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 big‐
       ger  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)
[top]

List of man pages available for DragonFly

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net