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

FreeBSD Manual Pages

  
 
  

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

NAME
       JudyL  macros - C library for creating and accessing a dynamic array of
       words, using 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;
       PWord_t	PValue;				 // pointer to return value
       Pvoid_t PJLArray	= (Pvoid_t) NULL;	 // initialize JudyL array

       JLI( PValue,  PJLArray, Index);		// JudyLIns()
       JLD( Rc_int,  PJLArray, Index);		// JudyLDel()
       JLG( PValue,  PJLArray, Index);		// JudyLGet()
       JLC( Rc_word, PJLArray, Index1, Index2);	// JudyLCount()
       JLBC(PValue,  PJLArray, Nth, Index);	// JudyLByCount()
       JLFA(Rc_word, PJLArray);			// JudyLFreeArray()
       JLMU(Rc_word, PJLArray);			// JudyLMemUsed()
       JLF( PValue,  PJLArray, Index);		// JudyLFirst()
       JLN( PValue,  PJLArray, Index);		// JudyLNext()
       JLL( PValue,  PJLArray, Index);		// JudyLLast()
       JLP( PValue,  PJLArray, Index);		// JudyLPrev()
       JLFE(Rc_int,  PJLArray, Index);		// JudyLFirstEmpty()
       JLNE(Rc_int,  PJLArray, Index);		// JudyLNextEmpty()
       JLLE(Rc_int,  PJLArray, Index);		// JudyLLastEmpty()
       JLPE(Rc_int,  PJLArray, Index);		// JudyLPrevEmpty()

DESCRIPTION
       A JudyL array is	the equivalent of an array of  word-sized  values.   A
       Value is	addressed by an	Index (key).  The array	may be sparse, and the
       Index may be any	word-sized number.  Memory to support the array	is al-
       located	as index/value pairs are inserted, and released	as index/value
       pairs are deleted.  A JudyL array can also be thought of	as  a  mapper,
       that is "map" a word to another word/pointer.

       As  with	 an  ordinary array, there are no duplicate indexes in a JudyL
       array.

       The value may be	used as	a scalar, or a pointer to a structure or block
       of data (or even	another	Judy array).

       A JudyL array is	allocated with a NULL pointer

       Pvoid_t PJLArray	= (Pvoid_t) NULL;

       Using  the macros described here, rather	than the JudyL function	calls,
       the default error handling sends	a message to the  standard  error  and
       terminates  the	program	with exit(1);.	For other error	handling meth-
       ods,  see  the  ERRORS  section.	  JLI(	PValue,	   PJLArray,   Index);
       // JudyLIns()

       Because	the  macro forms are sometimes faster and have a simpler error
       handling	interface than the equivalent JudyL functions,	they  are  the
       preferred way of	calling	the JudyL functions.

	JLI(PValue, PJLArray, Index) //	JudyLIns()
		      Insert an	Index and Value	into the JudyL array PJLArray.
		      If the Index is successfully inserted, the Value is ini-
		      tialized	to  0.	If  the	Index was already present, the
		      Value is not modified.

		      Return PValue pointing to	Value.	Your program  can  use
		      this  pointer  to	 read  or  modify Value	until the next
		      JLI() (insert), JLD() (delete) or	JLFA() (freearray)  is
		      executed on PJLArray. Examples:

		      *PValue =	1234;
		      Value = *PValue;

		      Return  PValue  set to PJERR if a	malloc() fail occured.
		      Note:  JLI()  and	 JLD()	reorganize  the	 JudyL	array.
		      Therefore, PValue	returned from previous JudyL calls be-
		      come invalid and must be re-acquired.

	JLD(Rc_int, PJLArray, Index) //	JudyLDel()
		      Delete the Index/Value pair from the JudyL array.

		      Return Rc_int set	to 1 if	successful.  Return Rc_int set
		      to  0  if	 Index	was not	present.  Return Rc_int	set to
		      JERR if a	malloc() fail occured.

	JLG(PValue, PJLArray, Index) //	JudyLGet()
		      Get the pointer PValue  associated  with	Index  in  the
		      PJLArray Judy array.

		      Return  PValue  pointing to Value.  Return PValue	set to
		      NULL if the Index	was not	present.  Return PValue	set to
		      PJERR if a malloc() fail occured.

	JLC(Rc_word, PJLArray, Index1, Index2) // JudyLCount()
		      Count  the  number of indexes present in the JudyL array
		      PJLArray between Index1 and Index2 (inclusive).

		      Return Rc_word set to the	count.	A return  value	 of  0
		      can be valid as a	count.

		      To count all indexes present in a	JudyL array, use:

		      JLC(Rc_word, PJLArray, 0,	-1);

	JLBC(PValue, PJLArray, Nth, Index) // JudyLByCount()
		      Locate  the Nth index that is present in the JudyL array
		      PJLArray (Nth = 1	returns	the first index	present).

		      Return PValue pointing to	its Value and Index set	to the
		      Nth  index if found, otherwise return PValue set to NULL
		      (the value of Index is undefined).

	JLFA(Rc_word, PJLArray)	// JudyLFreeArray()
		      Given a pointer to a JudyL array,	free the entire	 array
		      (much faster than	using a	JLN(), JLD() loop).

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

	JLMU(Rc_word, PJLArray)	// JudyLMemUsed()
		      Return Rc_word set to the	number of bytes	of memory mal-
		      loc()'ed	by PJLArray.  This is a	very fast routine, and
		      may be used before and after a JLI() or JLD() call  with
		      little performance impact.

	JudyL Search Functions
		      JLF(),  JLN(),  JLL(), JLP() allow you to	search for in-
		      dexes in the array.  You may search inclusively  or  ex-
		      clusively,  in either forward or reverse directions.  If
		      successful, Index	is returned set	to  the	 found	index,
		      and  PValue  is  returned	 set  to  a pointer to Index's
		      Value.  If unsuccessful, PValue is returned set to NULL,
		      and  Index  contains no useful information.  PValue must
		      be tested	for non-NULL prior to  using  Index,  since  a
		      search failure is	possible.

		      JLFE(),  JLNE(),	JLLE(),	JLPE() allow you to search for
		      indexes that are not present  ("empty")  in  the	array.
		      You  may	search	inclusively  or	exclusively, in	either
		      forward or reverse directions.  If successful, Index  is
		      returned	set  to	 a  not	 present  ("empty") index, and
		      Rc_int is	returned set to	1.  If unsuccessful, Rc_int is
		      returned	set to 0, and and Index	contains no useful in-
		      formation.  Rc_int must be checked prior to using	Index,
		      since a search failure is	possible.

	JLF(PValue, PJLArray, Index) //	JudyLFirst()
		      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.)	 JLF()
		      is typically used	to begin a sorted-order	 scan  of  the
		      indexes present in a JudyL array.

	JLN(PValue, PJLArray, Index) //	JudyLNext()
		      Search  (exclusive)  for	the next index present that is
		      greater than the passed Index.  JLN() is typically  used
		      to  continue  a sorted-order scan	of the indexes present
		      in a JudyL array,	or to locate a "neighbor" of  a	 given
		      index.

	JLL(PValue, PJLArray, Index) //	JudyLLast()
		      Search  (inclusive)  for	the last index present that is
		      equal to or less than the	passed Index.  (Start with In-
		      dex  =  -1, that is, all ones, to	find the last index in
		      the array.)  JLL() is typically used to begin a reverse-
		      sorted-order  scan of the	indexes	present	in a JudyL ar-
		      ray.

	JLP(PValue, PJLArray, Index) //	JudyLPrev()
		      Search (exclusive) for the previous index	 present  that
		      is  less than the	passed Index.  JLP() is	typically used
		      to continue a reverse-sorted-order scan of  the  indexes
		      present in a JudyL array,	or to locate a "neighbor" of a
		      given index.

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

	JLNE(Rc_int, PJLArray, Index) // JudyLNextEmpty()
		      Search (exclusive) for the next  index  absent  that  is
		      greater than the passed Index.

	JLLE(Rc_int, PJLArray, Index) // JudyLLastEmpty()
		      Search  (inclusive)  for	the  last index	absent that is
		      equal to or less than the	passed Index.  (Start with In-
		      dex  = -1, that is, all ones, to find the	last index ab-
		      sent in the array.)

	JLPE(Rc_int, PJLArray, Index) // JudyLPrevEmpty()
		      Search (exclusive) for the previous index	absent that is
		      less than	the passed Index.

Multi-dimensional JudyL	Arrays
       Storing	a pointer to another JudyL array in a JudyL array's Value is a
       simple way to support dynamic multi-dimensional arrays.	 These	arrays
       (or trees) built	using JudyL arrays are very fast and memory efficient.
       (In fact, that is how JudySL and	JudyHS are implemented).  An arbitrary
       number of dimensions can	be realized this way.  To terminate the	number
       of dimensions (or tree),	the Value pointer is marked to	NOT  point  to
       another	Judy  array. A JLAP_INVALID flag is used in the	least signifi-
       cant bit(s) of the pointer.  After the flag JLAP_INVALID	is removed, it
       is used as a pointer to the users data.	The Judy.h header file defines
       JLAP_INVALID.  See code fragment	below.

       Note: The current version of Judy.h changed this	flag from 0x4  to  0x1
       to  allow  for  a  malloc()  that  does not deliver memory on an	8 byte
       aligned boundry (such as	old versions of	valgrind).

       The following example code segment can be used to determine whether  or
       not a pointer points to another JudyL:

       PValue =	(PWord_t)PMultiDimArray;

       for (Dim	= 0; ;Dim++)
       {
	  if (PValue ==	(PWord_t)NULL) goto IndexNotFound;

	  /* Advance to	next dimension in array	*/
	  JLG(PValue, (Pvoid_t)*PValue,	Index[Dim]);

	  /* Check if pointer to user buffer: */
	  if (*PValue &	JLAP_INVALID)) break;
       }
       UPointer	= (UPointer_t) (*PValue	& ~JLAP_INVALID);  // mask and cast.
       printf("User object pointer is 0x%lx\n",	(Word_t) UPointer);
	      ...

       Note:   This works because malloc() guarantees to return	a pointer with
       the least bit(s)	== 0x0.	 You must remove JLAP_INVALID before using the
       pointer.

ERRORS:	See: Judy_3.htm#ERRORS
EXAMPLE
       Read  a series of index/value pairs from	the standard input, store in a
       JudyL array, and	then print out in sorted order.

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

       Word_t	Index;			   // array index
       Word_t	Value;			   // array element value
       Word_t *	PValue;			   // pointer to array element value
       int	Rc_int;			   // return code

       Pvoid_t	PJLArray = (Pvoid_t) NULL; // initialize JudyL array

       while (scanf("%lu %lu", &Index, &Value))
       {
	   JLI(PValue, PJLArray, Index);
	   If (PValue == PJERR)	goto process_malloc_failure;
	   *PValue = Value;		    // store new value
       }
       // Next,	visit all the stored indexes in	sorted order, first ascending,
       // then descending, and delete each index during	the descending pass.

       Index = 0;
       JLF(PValue, PJLArray, Index);
       while (PValue !=	NULL)
       {
	   printf("%lu %lu\n", Index, *PValue));
	   JLN(PValue, PJLArray, Index);
       }

       Index = -1;
       JLL(PValue, PJLArray, Index);
       while (PValue !=	NULL)
       {
	   printf("%lu %lu\n", Index, *PValue));

	   JLD(Rc_int, PJLArray, Index);
	   if (Rc_int == JERR) goto process_malloc_failure;

	   JLP(PValue, PJLArray, Index);
       }

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

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

								      JudyL(3)

NAME | SYNOPSIS | DESCRIPTION | Multi-dimensional JudyL Arrays | EXAMPLE | AUTHOR | SEE ALSO

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

home | help