0
I Use This!
Activity Not Available

Project Summary

AVL_FILE(3) AVL_FILE(3)
NAME
AVL_FILE - file-based AVL-tree functions.
SYNOPSIS
#include
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),

Tags

No tags have been added

In a Nutshell, AVL_FILE...

 No code available to analyze

Open Hub computes statistics on FOSS projects by examining source code and commit history in source code management systems. This project has no code locations, and so Open Hub cannot perform this analysis

Is this project's source code hosted in a publicly available repository? Do you know the URL? If you do, click the button below and tell us so that Open Hub can generate statistics! It's fast and easy - try it and see!

Add a code location

GNU General Public License v3.0 or later
Permitted

Commercial Use

Modify

Distribute

Place Warranty

Use Patent Claims

Forbidden

Sub-License

Hold Liable

Required

Distribute Original

Disclose Source

Include Copyright

State Changes

Include License

Include Install Instructions

These details are provided for information only. No information here is legal advice and should not be used as such.

All Licenses

This Project has No vulnerabilities Reported Against it

Did You Know...

  • ...
    there are over 3,000 projects on the Open Hub with security vulnerabilities reported against them
  • ...
    anyone with an Open Hub account can update a project's tags
  • ...
    in 2016, 47% of companies did not have formal process in place to track OS code
  • ...
    check out hot projects on the Open Hub

 No code available to analyze

Open Hub computes statistics on FOSS projects by examining source code and commit history in source code management systems. This project has no code locations, and so Open Hub cannot perform this analysis

Is this project's source code hosted in a publicly available repository? Do you know the URL? If you do, click the button below and tell us so that Open Hub can generate statistics! It's fast and easy - try it and see!

Add a code location

Community Rating

Be the first to rate this project
Click to add your rating
   Spinner
Review this Project!
Sample ohloh analysis