Defining a Name Set

Locating the Correct Integer

Suppose you have an array of 32-bit integers. Name 0 would be the least-significant bit (LSB) of the first integer, name 31 would be the most-significant bit (MSB) of the first integer, name 32 would be the LSB of the second integer, name 63 the MSB of the second, and so forth.

To access the word in the integer array in which a desired 〈name〉 resides, evaluate the integer quotient of the division 〈name〉/32. For example, name 23 is in integer 0, since 23/32=0, name 35 is in integer 1, since 35/32=1, and name 90 is in integer 2, since 90/32=2.

	NOTE: This explanation assumes you are using arrays whose first subscript is 0. If the first subscript is 1, you will have to add one after the integer divide.

Locating the Correct Bit

To access the appropriate bit in an integer, evaluate 〈name〉 mod 32 (where "mod" is a remainder function). For example, name 23 would be in bit 23 of its integer, since 23 mod 32=23, name 35 is in bit 3 of its integer, since 35 mod 32=3, and name 90 would be in bit 26 of its integer, since 90 mod 32=26.

Using the integer divide and mod functions, one can create efficient little routines that set or clear any desired bit in an array, regardless of its location. Depending on the computer language you are using, you could either implement these operations as subroutines or as macros. In this example, we use the C language and its macro facility:

#define setbit(array,bit)       array[(bit) / 32] |= 1 << ((bit) % 32)
#define clearbit(array,bit)     array[(bit) / 32] &= ~(1 << ((bit) % 32))

These macros do the following:

"But I Have 16-Bit Integers...

The above description works flawlessly in many cases — those cases where your machine uses 32-bit integers. However, in an actual application, you may not know (or be able to assume) that the integer wordsize is 32 bits. If you want to make your macros more general, you could use the sizeof function^[23]}:

#define wrdsz (sizeof(int) * 8)

The sizeof function above returns the number of bytes of an element of type int. You multiply this by 8 to determine the number of bits. Note that this also makes an assumption: that the number of bits in a byte is eight. This also may require a modification, although "eight bits per byte" may be a safer assumption than "four bytes per integer."

Determining the Size of the Integer Array

In many applications, nameset array sizes are determined during execution, and arrays are allocated dynamically — this makes good use of one of Display List's features: no limit on the number of names used for filtering. Or, you may want to define the array size while coding the source. In either case, you need to convert the maximum name value into an array size to determine the amount of memory to allocate. Once you have done this, you know the size of the integer array you will need for the current set, as well as any include- and exclude sets you will be using.

Of course, the size of the array depends also on the number of bits per integer, but we'll use the wrdsz macro above, so this is taken care of automatically. The number of elements required in the integer array is:

#define NameMax     n            (largest
value used)
   .
   .
   .
#define arraymax    (NameMax / wrdsz + 1)
   .
   .
   .
int   Nameset[arraymax],
      InclusionSet[arraymax]
       ExclusionSet[arraymax];          (etc.)

Note that if NameMax is an integer multiple of the number of bits in an integer, one unnecessary integer will be allocated. This is typically not even worth bothering about; you would probably consume more bytes of code trying to avoid the extra integer than you would save.

And now that you know the size of the integer array, you can either define a macro to clear all bits in a name set array...

#define clearallbits(array)    {int    I;                     \
                               for (I = 0; I < arraymax; I++) \
                                   array[I] = 0;              \
                                }

...or you could set the desired filter using zero for the 〈count〉 values. This also would clear the bits.

Again, note that you will have to tweak the above macros if your array indices start with 1 instead of 0.