Expat Internals: The Hash Tables

Written by Rhodri James

In the first walkthrough, I mentioned the parser's hash tables without giving much detail. In this article I'm going to give you some of that detail. I'm not going to look too closely at the hashing algorithm itself (it's SipHash for the curious), but I will look at how it is used to implement tables in Expat.

Absolute Basics

For the benefit of those who haven't heard this a million times before in Computer Science lectures, a hash table is a data structure that associates a piece of data with a "key", as distinct from an array which associates a piece of data with an integer index. It is a common data structure in high level languages such as Perl or Python, but in a lower level language like C¹ we need to implement our own version.

In our case the key is a text string in the parser's internal encoding (UTF-8 or UTF-16 depending on the compile-time flag XML_UNICODE). The key is passed through the hashing algorithm and converted into an index into the hash table's internal array, where the associated data will be found. Of course it's not quite that simple, or we wouldn't need a whole article to examine them.

Expat's Hash Tables

The parser uses hash tables for the things it will need to look up by name. Elements and element type declarations are held in a hash table, for instance, as are general entities, parameter entities, namespace prefixes and so on. These tables all use a single common set of data structures:

typedef const XML_Char *KEY;

typedef struct {
  KEY name;
} NAMED;

typedef struct {
  NAMED **v;
  unsigned char power;
  size_t size;
  size_t used;
  const XML_Memory_Handling_Suite *mem;
} HASH_TABLE;

The important field here is v; this is the actual table, implemented as an array of pointers to NAMED structures, which are themselves pointers to the key for each entry. There is heavy use of pointers here for several reasons; it allows the table to be dynamically resized when we add more entries, and does not need to know the size of keys or table entries in advance. The last reason there may look like it's unnecessary — surely we know the size of NAMED at compile time? — but we will see later why we want the flexibility.

Hash tables are initialised using the function hashTableInit() unsurprisingly. This starts us off with a NULL pointer in the v field, mem pointing to the suite of memory allocation functions being used by the parser, and all other fields set to zero. A completely empty table, in other words, taking up minimal space.

Inserting The First Entry

If you recall from the previous walkthrough, the Expat library mostly interacts with hash tables using the lookup() function, both to find entries as you might expect and to add new ones. Let's walk through what the code does when we call lookup() asking it to insert a new entry.

static NAMED *
lookup(XML_Parser parser, HASH_TABLE *table, KEY name, size_t createSize)
{
  size_t i;
  if (table->size == 0) {
    size_t tsize;
    if (!createSize)
      return NULL;

Let's assume that we have "foo" as a key (i.e. name == "foo", and let's also assume that our internal representation is UTF-8 for simplicity), and we want 20 bytes for our data (i.e. createSize == 20). Entering lookup(), we first check to see if we have a table allocated at all by checking the size field, the number of slots allocated in the table. For our empty table this is zero, so we next check if we are being asked to create a new entry, i.e. whether createSize is non-zero. If we were just trying to look something up in an empty table, we would return NULL at this point.

    table->power