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

FreeBSD Manual Pages

  
 
  

home | help
Judy1(3)		   Library Functions Manual		      Judy1(3)

NAME
       Judy1  macros - C library for creating and accessing a dynamic array of
       bits, using any value of	a word as an index.

SYNOPSIS
       cc [flags] sourcefiles -lJudy

       #include	<Judy.h>

       int     Rc_int;				// return code - integer
       Word_t  Rc_word;				// return code - unsigned word
       Word_t  Index, Index1, Index2, Nth;

       Pvoid_t PJ1Array	= (Pvoid_t) NULL;	// initialize Judy1 array

       J1S( Rc_int,  PJ1Array, Index);		// Judy1Set()
       J1U( Rc_int,  PJ1Array, Index);		// Judy1Unset()
       J1T( Rc_int,  PJ1Array, Index);		// Judy1Test()
       J1C( Rc_word, PJ1Array, Index1, Index2);	// Judy1Count()
       J1BC(Rc_int,  PJ1Array, Nth, Index);	// Judy1ByCount()
       J1FA(Rc_word, PJ1Array);			// Judy1FreeArray()
       J1MU(Rc_word, PJ1Array);			// Judy1MemUsed()
       J1F( Rc_int,  PJ1Array, Index);		// Judy1First()
       J1N( Rc_int,  PJ1Array, Index);		// Judy1Next()
       J1L( Rc_int,  PJ1Array, Index);		// Judy1Last()
       J1P( Rc_int,  PJ1Array, Index);		// Judy1Prev()
       J1FE(Rc_int,  PJ1Array, Index);		// Judy1FirstEmpty()
       J1NE(Rc_int,  PJ1Array, Index);		// Judy1NextEmpty()
       J1LE(Rc_int,  PJ1Array, Index);		// Judy1LastEmpty()
       J1PE(Rc_int,  PJ1Array, Index);		// Judy1PrevEmpty()

DESCRIPTION
       A Judy1 array is	the equivalent of a bit	array or bit map.   A  bit  is
       addressed  by  an  Index	(key).	The array may be sparse, and the Index
       may be any word-sized Value.  If	an index is present, it	 represents  a
       set  bit	 (a  bit  set  represents  an  index present).	If an index is
       absent, it represents an	unset bit (a bit unset	represents  an	absent
       index).

       A Judy1 array is	allocated with a NULL pointer

       Pvoid_t PJ1Array	= (Pvoid_t) NULL;
       Memory  to support the array is allocated as bits are set, and released
       as bits are unset.  If the Judy1	pointer	(PJ1Array) is NULL,  all  bits
       are unset (and the Judy1	array requires no memory).

       As with an ordinary array, a Judy1 array	contains no duplicate indexes.

       Using  the macros described here, rather	than the Judy1 function	calls,
       the default error handling sends	a message to the  standard  error  and
       terminates the program with exit(1).  For other error handling methods,
       see the ERRORS section.

       Because the macro forms are sometimes faster and	have a	simpler	 error
       handling	 interface  than  the  equivalent functions, they are the pre-
       ferred way of calling the Judy1 functions.

	J1S(Rc_int, PJ1Array, Index); // Judy1Set()
		      Set Index's bit in the Judy1 array PJ1Array.

		      Return Rc_int set	to 1 if	 Index's  bit  was  previously
		      unset  (successful),  otherwise 0	if the bit was already
		      set (unsuccessful).

	J1U(Rc_int, PJ1Array, Index); // Judy1Unset()
		      Unset Index's bit	in the Judy1 array PJ1Array; that  is,
		      remove Index from	the Judy1 array.

		      Return Rc_int set	to 1 if	Index's	bit was	previously set
		      (successful), otherwise 0	if the bit was	already	 unset
		      (unsuccessful).

	J1T(Rc_int, PJ1Array, Index); // Judy1Test()
		      Test if Index's bit is set in the	Judy1 array PJ1Array.

		      Return  Rc_int  set to 1 if Index's bit is set (Index is
		      present),	0 if it	is unset (Index	is absent).

	J1C(Rc_word, PJ1Array, Index1, Index2);	// Judy1Count()
		      Count the	number of indexes present in the  Judy1	 array
		      PJ1Array between Index1 and Index2 (inclusive).

		      Return  Rc_word  set  to the count.  A return Value of 0
		      can be valid as a	count, or it can  indicate  a  special
		      case  for	 fully populated array (32-bit machines	only).
		      See Judy1Count() for ways	to resolve this.

		      To count all indexes present (population)	in a Judy1 bit
		      array, use:

		      J1C(Rc_word, PJ1Array, 0,	-1);
		      Note: The	-1 promotes to the maximum index, that is, all
		      ones.

	J1BC(Rc_int, PJ1Array, Nth, Index); // Judy1ByCount()
		      Locate the Nth index that	is present in the Judy1	 array
		      PJ1Array	(Nth = 1 returns the first index present).  To
		      refer to the last	index in a fully populated array  (all
		      indexes present, which is	rare), use Nth = 0.

		      Return Rc_int set	to 1 and Index set to the Nth index if
		      found, otherwise return Rc_int set to 0  (the  Value  of
		      Index contains no	useful information).

	J1FA(Rc_word, PJ1Array); // Judy1FreeArray()
		      Free  the	 entire	Judy1 array PJ1Array (much faster than
		      using a J1N(), J1U() loop).

		      Return Rc_word set to the	number	of  bytes  freed,  and
		      PJ1Array set to NULL.

	J1MU(Rc_word, PJ1Array); // Judy1MemUsed()
		      Return Rc_word set to the	number of bytes	of memory cur-
		      rently in	use by Judy1 array PJ1Array. This  is  a  very
		      fast  routine,  and  may	be used	after a	J1S() or J1U()
		      call with	little performance impact.

	Judy1 Search Functions
		      The Judy1	search functions allow you to search  for  set
		      or  unset	bits in	the array.  You	may search inclusively
		      or exclusively, in either	forward	or reverse directions.
		      All  of  the  search  functions  use  a  similar calling
		      sequence.	 Rc_int	is returned set	to 1 for a  successful
		      search  and  the	found  Index  is  returned.  Rc_int is
		      returned set to 0	for an unsuccessful search, and	 Index
		      contains	no useful information.	The return code	Rc_int
		      must be checked prior to using the returned Index, since
		      a	search failure is possible.

	J1F(Rc_int, PJ1Array, Index); // Judy1First()
		      Search  (inclusive)  for the first index present that is
		      equal to or greater than the passed Index.  (Start  with
		      Index  = 0 to find the first index in the	array.)	 J1F()
		      is typically used	to begin a sorted-order	 scan  of  the
		      indexes present in a Judy1 array.

	J1N(Rc_int, PJ1Array, Index); // Judy1Next()
		      Search  (exclusive)  for	the next index present that is
		      greater than the passed Index.  J1N() is typically  used
		      to  continue  a sorted-order scan	of the indexes present
		      in a Judy1 array,	or to locate a "neighbor" of  a	 given
		      index.

	J1L(Rc_int, PJ1Array, Index); // Judy1Last()
		      Search  (inclusive)  for	the last index present that is
		      equal to or less than the	 passed	 Index.	  (Start  with
		      Index = -1, that is, all ones, to	find the last index in
		      the array.)  J1L() is typically used to begin a reverse-
		      sorted-order  scan  of  the  indexes  present in a Judy1
		      array.

	J1P(Rc_int, PJ1Array, Index); // Judy1Prev()
		      Search (exclusive) for the previous index	 present  that
		      is  less than the	passed Index.  J1P() is	typically used
		      to continue a reverse-sorted-order scan of  the  indexes
		      present in a Judy1 array,	or to locate a "neighbor" of a
		      given index.

	J1FE(Rc_int, PJ1Array, Index); // Judy1FirstEmpty()
		      Search (inclusive) for the first absent  index  that  is
		      equal  to	or greater than	the passed Index.  (Start with
		      Index = 0	to find	the first index	absent in the array.)

	J1NE(Rc_int, PJ1Array, Index); // Judy1NextEmpty()
		      Search (exclusive) for the next  absent  index  that  is
		      greater than the passed Index.

	J1LE(Rc_int, PJ1Array, Index); // Judy1LastEmpty()
		      Search  (inclusive)  for	the  last absent index that is
		      equal to or less than the	 passed	 Index.	  (Start  with
		      Index = -1 to find the last index	absent in the array.)

	J1PE(Rc_int, PJ1Array, Index); // Judy1PrevEmpty()
		      Search (exclusive) for the previous absent index that is
		      less than	the passed Index.

ERRORS:	See: Judy_3.htm#ERRORS
EXAMPLE
       In the following	example, errors	in the J1S() or	J1U() calls  go	 to  a
       user-defined  procedure,	 process_malloc_failure.   This	 is not	needed
       when you	use the	default	JUDYERROR() macro, since  the  default	causes
       your program to exit on all failures, including malloc()	failure.

       #include	<stdio.h>
       #include	<Judy.h>

       int main()			// Example program of Judy1 macro APIs
       {
	  Word_t Index;			// index (or key)
	  Word_t Rcount;		// count of indexes (or	bits set)
	  Word_t Rc_word;		// full	word return value
	  int	 Rc_int;		// boolean values returned (0 or 1)

	  Pvoid_t PJ1Array = (Pvoid_t) NULL; //	initialize Judy1 array

	  Index	= 123456;
	  J1S(Rc_int, J1Array, Index);	// set bit at 123456
	  if (Rc_int ==	JERR) goto process_malloc_failure;
	  if (Rc_int ==	1) printf("OK -	bit successfully set at	%lu\n",	Index);
	  if (Rc_int ==	0) printf("BUG - bit already set at %lu\n", Index);

	  Index	= 654321;
	  J1T(Rc_int, J1Array, Index);	// test	if bit set at 654321
	  if (Rc_int ==	1) printf("BUG - set bit at %lu\n", Index);
	  if (Rc_int ==	0) printf("OK -	bit not	set at %lu\n", Index);

	  J1C(Rcount, J1Array, 0, -1);	// count all bits set in array
	  printf("%lu bits set in Judy1	array\n", Rcount);

	  Index	= 0;
	  J1F(Rc_int, J1Array, Index);	// find	first bit set in array
	  if (Rc_int ==	1) printf("OK -	first bit set is at %lu\n", Index);
	  if (Rc_int ==	0) printf("BUG - no bits set in	array\n");

	  J1MU(Rc_word,	J1Array);	// how much memory was used?
	  printf("%lu Indexes used %lu bytes of	memory\n", Rcount, Rc_word);

	  Index	= 123456;
	  J1U(Rc_int, J1Array, Index);	// unset bit at	123456
	  if (Rc_int ==	JERR) goto process_malloc_failure;
	  if (Rc_int ==	1) printf("OK -	bit successfully unset at %lu\n", Index);
	  if (Rc_int ==	0) printf("BUG - bit was not set at %lu\n", Index);

	  return(0);
       }

AUTHOR
       Judy was	invented by Doug Baskins and implemented by Hewlett-Packard.

SEE ALSO
       Judy(3),	JudyL(3), JudySL(3), JudyHS(3),
       malloc(),
       the Judy	website, http://judy.sourceforge.net, for more information and
       Application Notes.

								      Judy1(3)

NAME | SYNOPSIS | DESCRIPTION | EXAMPLE | AUTHOR | SEE ALSO

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Judy1&manpath=FreeBSD+12.0-RELEASE+and+Ports>

home | help