rbgen.1

.\" mark rbinit as function
.\" mark rbsearch as function
.\" mark rbfind as function
.\" mark rblookup as function
.\" mark rbdelete as function
.\" mark rbdestroy as function
.\" mark rbwalk as function
.TH "RBGEN" 1 "" "" ""
.SH NAME
rbgen \- generate custom redblack search library code 
.SH "SYNOPSIS"
\fBrbgen\fR [-l] [-S \fIskeleton\fR] files...
.SH "DESCRIPTION"
.I 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 \fBmalloc\fR(3) and void pointers) type-safe.
.P
The code generated by
.I rbgen 
uses a variant of balanced binary trees that (unlike conventional AVL
trees) still performs well even when its input is partly sorted. 
.P
The interface of
.I rbgen
is modeled on that of 
.BR lex (1)
and its modern descendant 
.BR flex (1).
To use
.IR rbgen ,
you must write a spec file in three sections, like this:
.P
.nf
/* C code */

%%rbgen

(rbgen directives)

%%rbgen

/* C code */
.fi
.P
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:
.TP
%type \fItypename\fR
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.
.TP
%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.
.TP
%compare \fIfunc\fR
Required. Declare the name of your comparison function.  The function should 
take two arguments, of type const-pointer-to-item, and have semantics
like
.BR 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.
.TP
%alloc \fIfunc\fR
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
\fBmalloc\fR(3) pointers.  Should take a single const-pointer-to-item
argument. This hook will be used to initialize each item created by an 
\fIrbsearch\fR call.
.TP
%free \fIfunc\fR
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 \fBmalloc\fR(3) pointers.  Should take a single
const-pointer-to-item.  This hook will be used on each item removed by
an \fIrbdelete\fR or \fIrbdestroy\fR call.
.TP
%prefix \fIpref\fR
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.
.TP
%omit \fIfunc\fR...
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.
.TP
%static
Optional.  Change the storage class on all global declarations in the
generated code so they're not visible outside the generated module.
.TP
%sbrk
Optional. Enable SBRK allocation.  Normally,
.BR 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
.BR malloc (3)
and certain what you are doing.
.P
For the API of the generated code, see
.BR libredblack (3),
Generated versions differ in three respects:  
.P
First \fBrbinit\fR takes no
arguments. since the comparison function is compiled in.
.P
Second, arguments and return types that are void * in the stock
library will be pointers to your payload data type instead.
.P
Third, if you have specified a %prefix directive, the common prefix
of structure and function names will be different.
.SH "EXAMPLE"
.nf
#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\n");
                exit(1);
        }

	for (pp=samples; pp<samples+sizeof(samples)/sizeof(samples[0]);pp++)
	{
		val = exsearch(pp, ex);
                if(val == NULL)
                {
                        fprintf(stderr, "insufficient memory\n");
                        exit(1);
                }
	}
        for(val=exlookup(RB_LUFIRST, NULL, ex); val; val=exlookup(RB_LUNEXT, val, ex))
        {
                printf("%s:%d\n", val->pn, val->price);
        }

        exdestroy(ex);
        
        return 0;
}
.fi
.SH "FILES"
.TP
/usr/share/libredblack/redblack.[ch]
Skeleton files for code generation.
.SH "AUTHORS"
Damian Ivereigh wrote the libredblack library.  Eric S. Raymond
designed and wrote the rbgen code generator.
.SH "SEE ALSO"
.BR libredblack (3),