mainAVL_FILE - Summary

 
 
Membership Info
Group Admin:
1 active member

Group identification
Id: 9519
System Name: avl-file
Name: AVL_FILE
Group Type: non-GNU software and documentation

Search in this Group


 

This group is not part of the GNU Project.

AVL_FILE(3)                                           AVL_FILE(3)



NAME
       AVL_FILE - file-based AVL-tree functions.

SYNOPSIS
       #include <avl_file.h>

       AVL_FILE *avl_file_open (char *fname, int32_t len, int32_t
       n_keys, avl_file_cmp_fn *cmp);
       void avl_file_close (AVL_FILE *ap);

       int32_t avl_file_insert (AVL_FILE *ap, void *data);
       int32_t avl_file_delete (AVL_FILE *ap, void *data);
       int32_t avl_file_update (AVL_FILE *ap, void *data);

       int32_t avl_file_find (AVL_FILE *ap, void  *data,  int32_t
       key);
       int32_t   avl_file_startlt   (AVL_FILE  *ap,  void  *data,
       int32_t key);
       int32_t  avl_file_startge  (AVL_FILE  *ap,   void   *data,
       int32_t key);

       int32_t  avl_file_prev  (AVL_FILE *ap, void *data, int32_t
       key);
       int32_t avl_file_next (AVL_FILE *ap, void  *data,  int32_t
       key);

       void avl_file_startseq (AVL_FILE *ap);
       int32_t avl_file_readseq (AVL_FILE *ap, void *data);

       void avl_file_lock (AVL_FILE *ap);
       void avl_file_unlock (AVL_FILE *ap);

       int64_t avl_file_getnum (AVL_FILE *ap);

       void avl_file_squash (AVL_FILE *ap);

       int32_t  avl_file_scan  (AVL_FILE  *ap, int32_t key, off_t
       off, int64_t *count);

DESCRIPTION
       These routines  implement  file-based  threaded  AVL-trees
       (height balanced binary trees) with multiple keys and con­
       current access,  using  fixed  length  records  in  single
       files.  The keys are part of the record structures, and so
       are not passed separately. A comparison function  must  be
       supplied  that  takes  as  parameters two record structure
       pointers and also a key index, to be used by  these  func­
       tions for the AVL-tree operations of inserting, searching,
       and deleting.

       The avl_file_open function opens the file fname,  creating
       it if it does not exist. The len parameter sets the length
       of the records for the file, and it cannot change once the
       file  is created.  Subsequently for the file, calls to the
       functions that require record pointers must have len  size
       buffers.  The  n_keys  parameter is the number of keys for
       this file, and cmp is a pointer to  the  comparison  func­
       tion,  which  takes  a  number from 0 to n_keys-1, and two
       pointers to records structures, and returns the result  of
       the  comparison for that key. The typedef for the compari­
       son function is:

       typedef int32_t (*avl_file_cmp_fn_t) (int32_t, const  void
       , const void );

       The  comparison  function and data record format cannot be
       altered once an AVL-tree file has been created.

       The avl_file_insert function inserts  a  new  data  record
       into   the   file.   Duplicate   keys   are  allowed.  The
       avl_file_delete function deletes a record if it  finds  an
       exact  match  for  the whole record.  The record should be
       read first, since the whole record  must  match,  and  not
       just  the  key field. If duplicates exist, the one that is
       deleted is arbitrary. The space  left  unused  by  deleted
       records gets re-used when new records are added. The func­
       tion avl_file_update finds a record with matching  key(s),
       and replaces it.

       The function avl_file_find searches the tree corresponding
       to key key, which must be from zero to n_keys-1, using the
       record  structure  pointed  to  by data, writing over that
       buffer if a record is found  with  a  matching  key.   The
       avl_file_startlt and avl_file_startge functions initialize
       tree pointers to point to the first record less than,  and
       greater  than  or  equal to respectively, for the data and
       key supplied to these functions, and over-write  the  data
       buffer  with the record if one is found.  Subsequent calls
       to avl_file_prev or avl_file_next retrieve file records in
       key order for the given key.

       Unordered  sequential  retrieval of all the records in the
       file can be done by using the  function  avl_file_startseq
       to initialize the sequential access pointer, and the func­
       tion avl_file_readseq to get the next record.

       The avl_file_lock and avl_file_unlock functions apply  and
       release co-operative locks to a file, respectively.

       The function avl_file_getnum returns a sequential (unique)
       record number for use in a file. This is provided for  the
       case that a unique key is desired.

       The  avl_file_squash  function recovers space left over by
       deleted records, and shortens the file, if  possible.  For
       files  opened by multiple processes, recovering all of the
       unused space is unlikely.

       The avl_file_scan function recursively traverses the  tree
       given  by key, counting the number of records in the tree.
       The parameter off must be passed as zero, and the  int64_t
       pointer count must point to a value initialized to zero.

RETURN VALUE
       All  of  the functions that read or write records into the
       file return zero for success, or -1 for failure.

       Upon  successful  completion,  avl_file_open  returns   an
       AVL_FILE pointer.  Otherwise, NULL is returned.

       The avl_file_scan function returns the tree height for key
       key.  Also the number of records is returned in the  count
       parameter.

       The  avl_file_getnum  function  returns  unique sequential
       record numbers.

EXAMPLE
       An example program using two keys:

       #include "avl_file.h"

       #define RK_NUM               0     // key index
       #define RK_OBJ_NUM_REG       1

       struct r_struct {    // fixed data structure (including key fields)
          int32_t num;
          char object[24];
          int32_t reg;
          char data[100];
       };


       int32_t cmp_test (int32_t key, void *va, void *vb) {   // comparison func
tion
          struct r_struct *a, *b;
          int32_t i;

          a = (struct r_struct *) va;
          b = (struct r_struct *) vb;

          switch (key) {
          case RK_NUM:
             i = a->num - b->num;
             break;
          case RK_OBJ_NUM_REG:
             i = strcmp (a->object, b->object);
             if (i == 0) i = a->num - b->num;
             if (i == 0) i = a->reg - b->reg;
             break;
          default:
             fprintf (stderr, "cmp_r: invalid key0);
             break;
          }
          return (i);
       }

       int main (int argc, char *argv[]) {
          AVL_FILE *ap;
          struct r_struct r;
          int32_t n;

          //--- avl_file_open (fname, rec size, n_keys, cmp function)
          ap = avl_file_open ("test.avl", sizeof (struct r_struct),
                              2, (avl_file_cmp_fn_t) cmp_test);

          r.num = 1;
          strcpy (r.object, "GNU/Linux");
          r.reg = 0;
          strcpy (r.data, "SuSE");
          avl_file_insert (ap, &r);

          //...

          r.num = 1;
          n = avl_file_startge (ap, &r, RK_NUM);
          while (n == 0) {
             if (r.num > 1) break;

             printf ("%s %s0, r.object, r.data);
             n = avl_file_next (ap, &r, RK_NUM);
          }

          avl_file_close (ap);
       }
ERRORS
       These functions abort by  calling  exit()  if  the  system
       calls  to lseek(), read(), or write() fail for any reason,
       or if a corrupted file causes an attempt  to  read  beyond
       the end-of-file.

CONFORMING TO
       Not known.

SEE ALSO
       libavl,   mysql(1),   qsort(3),   bsearch(3),  tsearch(3),
       gdbm(3),




Registration Date: Fri 21 Sep 2007 06:16:24 PM UTC
License: GNU General Public License v3 or later
Development Status: 3 - Alpha

 

Latest News rss feed

No news found

Quick Overview
 Memberlist (1 member)

Communication Tools
 Mailing Lists (0 public mailing lists)

Development Tools
 Task Manager (open items: 0, total: 0)

Back to the top

Powered by Savane 3.13-d3ae.
Corresponding source code