Every now and then I get a question about an idiom I use for looping through a collection of literal structures. This is handy for little lookup tables, or using pre-defined data to populate another data structure.

This is all generic C stuff, so you can use it in Objective-C too. I’ll be walking through part of the fsevent.m example code from AMOSXP(3). It takes a set of bit flags from FSEvents (Mac OS X file system notifications) and prints out, in a human-readable format, which of the bits are set.

Making the Table

First you need a structure to hold the data. In this case, you’ll want to associate human-readable strings with bit-flag constants of the FSEventStreamEventFlags enum. So you’ll need a field with the bitflag, and another pointing to a C string that has the description:

// Lookup table for displaying human-readable translations of flags
typedef struct FlagMap {
    int bitflag;
    const char *description;
} FlagMap;

Then define the lookup table. There’s two interesting things about this table. There is no explicit sized used when declaring the flagmap array. The array will be as big as it is. There is no need to count the elements by hand and put an explicit value in the square brackets. The other is that there is no sentinel value (a zero or NULL / nil) to terminate the table. The table only contains interesting data.

static FlagMap flagmap[] = {
    { kFSEventStreamEventFlagMustScanSubDirs, "must scan subdirs"     },
    { kFSEventStreamEventFlagUserDropped,     "user dropped events"   },
    { kFSEventStreamEventFlagKernelDropped,   "kernel dropped events" },
    { kFSEventStreamEventFlagEventIdsWrapped, "event ids wrapped"     },
    { kFSEventStreamEventFlagHistoryDone,     "history playback done" },
    { kFSEventStreamEventFlagRootChanged,     "root changed"          },
    { kFSEventStreamEventFlagMount,           "mounted"               },
    { kFSEventStreamEventFlagUnmount,         "unmounted"             }
};

Now to the actual use of the table. The FSEvents callback function walks through a set of file system change events and prints out various bits of interesting information. To see what bits are set, walk through the table each time and bitwise-AND the flag to see if it’s set.
That’s the algorithm in words. Here it is in code.

...
        FSEventStreamEventFlags flags = eventFlags[i];
        // Display all of the set flags.
        FlagMap *scan = flagmap;
        FlagMap *stop = scan + sizeof(flagmap) / sizeof(*flagmap);
        while (scan < stop) {
            if (flags & scan->bitflag) {
                printf ("    %sn", scan->description);
            }
            scan++;
        }
...

Uh. OK. If you’re not familiar with C and C pointers, this may seem like gibberish. The technique is a simple scan through bytes in memory.

This is how things are laid out:

For the sake of discussion, I’ll say it’s four bytes for the constant and four bytes for the pointer. So as you scan through memory you’ll see four bytes of a constant, and four bytes for a pointer, then four more bytes of the next constant, and four more bytes for the next pointer, stacked end-to-end.

Walking the Table

So, to start out with, set the scan pointer to the start of table:

FlagMap *scan = flagmap;

Now scan points at the beginning of the table:

How do you know when to stop? If you had a sentinel value, you could keep incrementing the scan pointer until you found the “please stop now!” value. But this table doesn’t have that. Sometimes you might not have the luxury of a value that’s out of bounds you can use for a terminator. There’s also no explicit size. To know how many items to look at, you need to do a little bit of math.

The compiler knows how big the flagmap table is : 64 bytes. Four for the bit flag, four for the pointer, and eight entries. You can get this value with sizeof(flagmap).

The compiler also knows how big a single element of the table is. The table is composed of FlagMap structures, which are eight bytes each. You can get this value with sizeof(FlagMap). There’s a trick you can do with sizeof – rather than hard-coding the type, you can get the compiler to figure out what the type is. sizeof(*flagmap) will take the type of the flagmap variable, which is a C Array, which is basically a pointer to the first element of the array, and then dereferences it. The type of this is FlagMap. So, sizeof(*flagmap) will also evaluate by the compiler to 8. I prefer doing it this way, basing the sizeof off of the actual array variable, because you might change the type of the array and would have to remember to update the “size of the structure” code.

Dividing the size of the array by the size of an element gives you the number of items in it: sizeof(flagmap) / sizeof(*flagmap).

So now, the next line of code figures out where the end of the table is:

FlagMap *stop = scan + sizeof(flagmap) / sizeof(*flagmap);


The expression then turns into

FlagMap *stop = scan + 8;


If you remember your C pointer rules, when you add one to a pointer, you’re actually incrementing the value of the pointer by the number of bytes of its base type. In this case scan + 1 is the value of scan, plus eight for the eight bytes of sizeof(FlagMap). scan + 2 actually results in scan plus sixteen, and so on. By adding 8, you’re setting the end pointer to point 64 bytes after the start of the table, which happens to be the end of the table.

Technically, it’s pointing right off the end of the table. It does give you an address in memory where you know you’ve run out of table contents.

And now the preparation is over. You know where in memory to start looking for stuff (scan), you know where in memory to stop looking for stuff (stop).

Now for the loop. This is the idiom:

while (scan < stop) {
    // Do stuff with scan
    scan++;
}

So long as the scan pointer is strictly earlier in memory than the stop pointer, do some work with scan. Then increment scan by one. Remember that adding one to the scan pointer actually adds eight to it due to the size of what it points to. The pointer now points to the beginning of the next element of the table. Then you process it. Then increment it again, and point to the next element of the table, and process it again.

Here’s all the values that scan has during the course of processing:

Notice that when scan+8 == stop, the loop stops because scan is no longer strictly less than stop.

Actually Doing Stuff

What kind of work can you do? That’ll be defined by what data you have in your table. In this case,

if (flags & scan->bitflag) {
    printf ("    %sn", scan->description);
}

It takes the bitflag from the table, bitwise-ANDs it to see if it’s set in the flags gotten from the file system event. If the bit is set then the if expression evaluates to a true value, so the body of the if is taken prints the description.

Want to see some more examples of this stuff, check out this gist, which includes walking some simpler tables.