RBGEN(1)RBGEN(1)NAMErbgen - generate custom redblack search library code
SYNOPSISrbgen [-l] [-S skeleton] files...
DESCRIPTIONrbgen 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 de‐
rivatives will be compiled into C code in the output file. The direc‐
tives 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. Choos‐
ing `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 ini‐
tialize 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 gener‐
ated module.
%sbrk Optional. Enable SBRK allocation. Normally, libredblack(3) man‐
ages 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 ver‐
sions differ in three respects:
First rbinit takes no arguments. since the comparison function is com‐
piled 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 memory0);
exit(1);
}
for (pp=samples; pp<samples+sizeof(samples)/sizeof(samples[0]);pp++)
{
val = exsearch(pp, ex);
if(val == NULL)
{
fprintf(stderr, "insufficient memory0);
exit(1);
}
}
for(val=exlookup(RB_LUFIRST, NULL, ex); val; val=exlookup(RB_LUNEXT, val, ex))
{
printf("%s:%d0, 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 ALSOlibredblack(3),
RBGEN(1)
