Content-type: text/html
Manpage of RBGEN
RBGEN
Section: (1)
Updated:
Index
Return to Main Contents
NAME
rbgen - generate custom redblack search library code
SYNOPSIS
rbgen [-l] [-S skeleton] files...
DESCRIPTION
rbgen is a code generator that customizes a binary-tree search
library for you. You can use this to generate C code for associative
arrays (like Perl and Python hashes) that is small, fast and
(unlike kluges with bare malloc(3) and void pointers) type-safe.
The code generated by
rbgen
uses a variant of balanced binary trees that (unlike conventional AVL
trees) still performs well even when its input is partly sorted.
The interface of
rbgen
is modeled on that of
lex(1)
and its modern descendant
flex(1).
To use
rbgen,
you must write a spec file in three sections, like this:
/* C code */
%%rbgen
(rbgen directives)
%%rbgen
/* C code */
The wrapper sections of C code may be empty. The section of rbgen
derivatives will be compiled into C code in the output file. The
directives section may contain comments, led with //, and the
following directives:
- %type typename
-
Required. Declares the C data type of the user's payload items. In a typical
application, this will be a struct containing some index field.
- %access {inline|pointer}
-
Optional. Says whether the data is to be carried in-line in the tree node
structure or accessed through a data pointer. Choosing `inline' is
good if the data consists of small fixed-length records, as it avoids
a level of indirection each time an item is accessed, If not
specified, the default is pointer.
- %compare func
-
Required. Declare the name of your comparison function. The function should
take two arguments, of type const-pointer-to-item, and have semantics
like
strcmp(3).
That is, it should return less than, equal to, or greater than zero if
the first argument is found, respectively, to be less than, to match,
or be greater than the second.
- %alloc func
-
Optional. Declare a function for allocating item data at node creation
time; this may be useful, for example, if your data item is to contain
malloc(3) pointers. Should take a single const-pointer-to-item
argument. This hook will be used to initialize each item created by an
rbsearch call.
- %free func
-
Optional. Declare a function for clearing item data before you
deallocate the node it's in; this will be useful, for example, if your
data item contains malloc(3) pointers. Should take a single
const-pointer-to-item. This hook will be used on each item removed by
an rbdelete or rbdestroy call.
- %prefix pref
-
Change the name prefix of the generated structures and functions
(default is "rb").
This will be useful if you need to have more than one instance of
generated redblack code, parametrized for different types, in the same
runtime.
- %omit func...
-
Optional. Specify a list of entry points to be conditioned out. The
following entry points are omittable: destroy, search, find,
delete, walk, readlist, lookup, destroy, delete,
readlist. Omitting readlist also drops out openlist and
closelist. The name prefix is automatically prepended to these names.
- %static
-
Optional. Change the storage class on all global declarations in the
generated code so they're not visible outside the generated module.
- %sbrk
-
Optional. Enable SBRK allocation. Normally,
libredblack(3)
manages its own freelist. With this directive, the code will do individual
mallocs for each node. Don't enable this unless you are pretty
intimate with the implementation of
malloc(3)
and certain what you are doing.
For the API of the generated code, see
libredblack(3),
Generated versions differ in three respects:
First rbinit takes no
arguments. since the comparison function is compiled in.
Second, arguments and return types that are void * in the stock
library will be pointers to your payload data type instead.
Third, if you have specified a %prefix directive, the common prefix
of structure and function names will be different.
EXAMPLE
#include <string.h>
#include <stdio.h>
#define PN 8
typedef struct
{
char pn[PN+1];
int price;
}
price_t;
int compare(const price_t *s1, const price_t *s2)
{
return strcmp(s1->pn, s2->pn);
}
// These are the redblack directives
%%rbgen
%type price_t
%cmp compare
%access inline // data is carried in the node structure itself.
%omit find walk delete readlist
%static
%prefix ex
%%rbgen
int main(int argc, char *argv[])
{
struct extree *ex;
const price_t samples[] =
{
{"THX1138", 40},
{"ED2317", 55},
{"NGC1136", 32},
}, *val, *pp;
if ((ex=exinit())==NULL)
{
fprintf(stderr, "insufficient memory);
exit(1);
}
for (pp=samples; pp<samples+sizeof(samples)/sizeof(samples[0]);pp++)
{
val = exsearch(pp, ex);
if(val == NULL)
{
fprintf(stderr, "insufficient memory);
exit(1);
}
}
for(val=exlookup(RB_LUFIRST, NULL, ex); val; val=exlookup(RB_LUNEXT, val, ex))
{
printf("%s:%d, val->pn, val->price);
}
exdestroy(ex);
return 0;
}
FILES
- /usr/share/libredblack/redblack.[ch]
-
Skeleton files for code generation.
AUTHORS
Damian Ivereigh wrote the libredblack library. Eric S. Raymond
designed and wrote the rbgen code generator.
SEE ALSO
libredblack(3),
Index
- NAME
-
- SYNOPSIS
-
- DESCRIPTION
-
- EXAMPLE
-
- FILES
-
- AUTHORS
-
- SEE ALSO
-
This document was created by
man2html,
using the manual pages.
Time: 03:54:38 GMT, October 25, 2003