Using JudyL

JudyL functions provide a way to represent long-word values in a Judy array. These functions support large arrays of 32-bit or 64-bit values (long words). Since an initial (empty) JudyL array is represented by a null pointer, you can make JudyL arrays multi-dimensional, the equivalent of:

void * JudyLArray [4294967296][4294967296]...;

The table below shows the JudyL functions. For more information, see the JudyL(3X) man page.

JudyL example

You can find the code for this example and others on the Judy web site: http://devresource.hp.com/judy/

// FUNCTION HISTOGRAM; JUDYL DEMO PROGRAM//// This program uses JudyL to create a histogram of data generated by the// function random(3M).  Other functions could be substituted in.//// The program generates n random numbers, stores them in a JudyL array// and then prints a histogram.  All aspects of the generation and // histogram are timed so the user can see how long various JudyL functions// take.//// This demonstrates://           JudyLIns //           JudyLFirst//           JudyLNext//           JudyLLast//           JudyLCount//           JudyLByCount//           how to access a JudyL value.//// Notice that using JudyL gives you fast stores and lookups as with hashing// but without having to define a hash function, initialize the hash table// or having to predetermine a good hash table size.  It also gives you a// sorted list at the same time. Also notice that JudyLCount is much faster than you 

// can sequentially count items in an array.//#include <stdio.h>#include <sys/time.h>#include <errno.h>#include "Judy.h"// Default number of iterations (number of random numbers generated)// This may be overridden on the command line#define DEFAULT_ITER 1000000// The number of buckets the histogram is divided into.#define DEFAULT_HISTO_BUCKETS 32// Macro for correction english output for plurals#define PLURAL(count) ((count == 1) ? "" : "s")// Generic fatal error handler, pass in JError_t#define JUDY_ERROR(J) \        fprintf(stderr, "File: '%s', line: %d: Judy error: %d\n", \                __FILE__, __LINE__, JU_ERRNO(&(J))); \        exit(2);// timing routinesstruct timeval TBeg, TEnd;#define STARTTm         gettimeofday(&TBeg, NULL)#define ENDTm           gettimeofday(&TEnd, NULL)#define DeltaUSec \        ((double)(TEnd.tv_sec * 1000000.0 + TEnd.tv_usec) \        - (TBeg.tv_sec * 1000000.0 + TBeg.tv_usec))// End of timing routinesmain( int argc, char **argv){   void    *PJArray = 0;        // main JudyL array                                // key is random number, value is repeat count   void    *PJCountArray = 0;   // second JudyL array                                // key is repeat count (from PJArray)                                // value is count of items with the same                                // repeat count   JError_t JError;             // Judy error structure   ulong_t  Index;              // index in JudyLFirst/Next loop   ulong_t *PValue;             // ptr to Judy array value   ulong_t *PGenCount;          // ptr to generation count   ulong_t  num_vals;           // number of randoms to generate   ulong_t  iter;               // for loop iteration   ulong_t  unique_nums;        // number of unique randoms generated   ulong_t  random_num;         // random number   ulong_t  median;             // random number   ulong_t  tmp1, tmp2;         // temporary variable   double   random_gen_time;    // time to generate random numbers   ulong_t  histo_incr;         // histogram increment   unsigned long long ran_sum = 0;  // sum of all generated randoms// TITLE   (void) puts ("\nJudyL demonstration: random(3M) histogram");// SET NUMBER OF RANDOMS TO GENERATE   if (argc != 2)   {      // SET TO DEFAULT_ITER      num_vals = DEFAULT_ITER;      (void) printf ("Usage: %s [numvals]\n", argv[0]);      (void) printf ("  Since you did not specify a number of values, %d\n",                     num_vals);      (void) puts   ("  will be used as the number of random numbers to insert");      (void) puts   ("  into the Judy array");   }   else   {// OVERRIDE NUMBER OF RANDOMS TO GENERATE      num_vals = atol(argv[1]);   }// TIME THE GENERATION OF ALL THE RANDOM NUMBERS.  THIS TIME IS LATER// // This time is later subtracted from the insert loop time so that the// time it takes to do the actual JudyLIns can be isolated from the// total time.   (void) puts ("\ntiming random number generation");   STARTTm;     for (iter = num_vals; iter; iter--)   {      random();   }  /* end of random number generator time */   ENDTm;   random_gen_time = DeltaUSec;   (void) printf("It took %.3f sec to generate %ld random numbers\n",     random_gen_time/1000000, num_vals);   (void) printf("  (ie. %.3f uSec/number)\n\n", random_gen_time/num_vals);// REGENERATE RANDOMS AND INSERT THEM INTO A JUDYL ARRAY   (void) puts("Please wait while the random numbers are inserted into");   (void) puts("a JudyL array (with a usage count) ...");   STARTTm;   for (iter = num_vals; iter; iter--)   {      random_num = (ulong_t)random();      if ((PValue = (ulong_t *)JudyLIns(&PJArray, random_num, &JError))           == PJERR)      {         JUDY_ERROR(JError);  // exits      }      /* increment hit count */      (*PValue)++;      /* sum the random number */      ran_sum += random_num;   }  /* end of random number generator time */   ENDTm;   (void) printf("That took %.3f uSec/Index.\n",                (DeltaUSec - random_gen_time)/num_vals);// COUNT THE NUMBER OF ELEMENTS IN THE JUDYL ARRAY// IE. COUNT THE NUMBER OF UNIQUE RANDOM NUMBERS   STARTTm;   unique_nums = JudyLCount(PJArray, 0, ~0L, &JError);   ENDTm;   (void) printf("\nThere were %ld unique random numbers generated\n",                 unique_nums);   (void) printf("It took %.3f uSec to count them in the Judy array.\n",                 DeltaUSec);// FIND HOW MANY NUMBERS WERE GENERATED ONCE, TWICE, ...//// Create a new JudyL array where the index is the count from PJArray// and the value is a count of the number of elements with that count.   if (unique_nums != num_vals)   {      (void) puts("\nLooping through the entire Judy array to create a");      (void) puts("new Judy counting array (PJCountArray in the source code)");      (void) puts("...");      STARTTm;      for (Index = 0L,           PValue = (ulong_t *)JudyLFirst(PJArray, &Index, &JError);           PValue;           PValue = (ulong_t *)JudyLNext(PJArray, &Index, &JError))      {if ((PGenCount = (ulong_t *)JudyLIns(&PJCountArray, *PValue, &JError)) == PJERR)           {             JUDY_ERROR(JError);  // exits          }          (*PGenCount)++; // increment hit count       }      ENDTm;      (void) printf("That took %.3f Secs or %.3f uSec/Index\n\n",                        DeltaUSec/1000000, DeltaUSec/unique_nums);// PRINT DUPLICATES HISTOGRAM      (void) puts("Duplicates Histogram:");      for (Index = 0L,           PValue = (ulong_t *)JudyLFirst(PJCountArray, &Index, &JError);           PValue;           PValue = (ulong_t *)JudyLNext(PJCountArray, &Index, &JError))      {          (void) printf("  %ld numbers were generated %ld time%s\n",                         *PValue, Index, PLURAL(Index));      }   }// PRINT DISTRIBUTION HISTOGRAM   (void) puts("\nCompute the random number distribution by counting index");   (void) puts("ranges.");   histo_incr = ((ulong_t)~0L / DEFAULT_HISTO_BUCKETS) >> 1;   Index = 0L;   for (iter = 0; iter < DEFAULT_HISTO_BUCKETS; iter++)   {      (void) printf("  %ld unique values from %8x - %8x\n",                 JudyLCount(PJArray, Index, Index + histo_incr, &JError),                Index, Index + histo_incr);      Index += histo_incr + 1;   }// PRINT MEAN (average),//       MEDIAN (middle value, or average of two middle values)//       RANGE (low and high value)      tmp1 = (ulong_t)(ran_sum/(long long)num_vals);   (void) printf("                  mean: 0x%08x\n", tmp1);// If there were an even number of randoms generated, then average// the two middle numbers.  Otherwise, the mean is the middle value   if (num_vals & 1)   {      JudyLByCount(PJArray, num_vals/2, &tmp1, &JError);      JudyLByCount(PJArray, (num_vals/2)+1, &tmp2, &JError);      median = (tmp1 + tmp2) / 2;   }   else   {      JudyLByCount(PJArray, (num_vals+1)/2, &median, &JError);   }   (void) printf("                median: 0x%08x\n", median);   Index = 0;   JudyLFirst(PJArray, &Index, 0);   (void) printf("first random generated: 0x%08x\n", Index);   Index = ~0;   JudyLLast(PJArray, &Index, 0);   (void) printf(" last random generated: 0x%08x\n", Index);   exit(0);   /*NOTREACHED*/}  // main()

Sample output

$ funhist 10000000JudyL demonstration: random(3M) histogramtiming random number generationIt took 0.416 sec to generate 10000000 random numbers  (ie. 0.042 uSec/number)Please wait while the random numbers are inserted intoa JudyL array (with a usage count) ...That took 1.619 uSec/Index.There were 10000000 unique random numbers generatedIt took 76.000 uSec to count them in the Judy array.Compute the random number distribution by counting indexranges.  311914 unique values from        0 -  3ffffff  311770 unique values from  4000000 -  7ffffff  311556 unique values from  8000000 -  bffffff  312178 unique values from  c000000 -  fffffff  310960 unique values from 10000000 - 13ffffff  311522 unique values from 14000000 - 17ffffff  312201 unique values from 18000000 - 1bffffff  312361 unique values from 1c000000 - 1fffffff  312487 unique values from 20000000 - 23ffffff  311927 unique values from 24000000 - 27ffffff  313360 unique values from 28000000 - 2bffffff  312025 unique values from 2c000000 - 2fffffff  311236 unique values from 30000000 - 33ffffff  310973 unique values from 34000000 - 37ffffff  310617 unique values from 38000000 - 3bffffff  312275 unique values from 3c000000 - 3fffffff  311417 unique values from 40000000 - 43ffffff  312189 unique values from 44000000 - 47ffffff  311290 unique values from 48000000 - 4bffffff  311570 unique values from 4c000000 - 4fffffff  311224 unique values from 50000000 - 53ffffff  311750 unique values from 54000000 - 57ffffff  311372 unique values from 58000000 - 5bffffff  311764 unique values from 5c000000 - 5fffffff  311227 unique values from 60000000 - 63ffffff  311947 unique values from 64000000 - 67ffffff  311845 unique values from 68000000 - 6bffffff  311913 unique values from 6c000000 - 6fffffff  311941 unique values from 70000000 - 73ffffff  311813 unique values from 74000000 - 77ffffff  311703 unique values from 78000000 - 7bffffff  335673 unique values from 7c000000 - 7fffffff                  mean: 0x3fff3e9c                median: 0x40220000first random generated: 0x0000012b last random generated: 0x7fffff10