Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
RBGEN(1)							      RBGEN(1)

       rbgen - generate	custom redblack	search library code

       rbgen [-l] [-S skeleton]	files...

       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  de-
       scendant	 flex(1).   To	use rbgen, you must write a spec file in three
       sections, like this:

       /* C code */


       (rbgen directives)


       /* 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  di-

       %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 re-
	      turn less	than, equal to,	or greater than	zero if	the first  ar-
	      gument  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.

	      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.

       #include	<string.h>
       #include	<stdio.h>

       #define PN     8

       typedef struct
	   char	pn[PN+1];
	   int price;

       int compare(const price_t *s1, const price_t *s2)
	   return strcmp(s1->pn, s2->pn);

       // These	are the	redblack directives
       %type price_t
       %cmp compare
       %access inline	   // data is carried in the node structure itself.
       %omit find walk delete readlist
       %prefix ex

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

	    for	(pp=samples; pp<samples+sizeof(samples)/sizeof(samples[0]);pp++)
		 val = exsearch(pp, ex);
		       if(val == NULL)
			       fprintf(stderr, "insufficient memory0);
	       for(val=exlookup(RB_LUFIRST, NULL, ex); val; val=exlookup(RB_LUNEXT, val, ex))
		       printf("%s:%d0, val->pn,	val->price);


	       return 0;

	      Skeleton files for code generation.

       Damian  Ivereigh	 wrote	the  libredblack library.  Eric	S. Raymond de-
       signed and wrote	the rbgen code generator.




Want to link to this manual page? Use this URL:

home | help