Linux Certif

Toute la documentation sur la certification Linux LPI

rbgen

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),