Emulating Mappings

In this example, we will emulate a hash table (pretty much a dictionary); elements are Python objects.

staticforward PyTypeObject Hash_Type;
#define HASH_SIZE 256
struct bucket {
  long hash;
  PyObject *object;
  struct bucket *next;
};

typedef struct {
  PyObject_HEAD
  int size;
  struct bucket *table[HASH_SIZE];
} Hash;
#define Hash_Check(v) ((PyObject *)(v)->ob_type == &Hash_Type)
#define Hash_size(v)  ((Hash *)(v)->size)
#define Hash_table(v) ((Hash *)(v)->table)

The Hash type contains an array of singly-linked lists, the size field should contain the total number of items in the lists. In this implementation, the key is not stored; subscript assignment is by hash value only. The keys() and items() functions should raise an exception.

Registering Methods

Define a variable of type PyMappingMethods and include a pointer to it in the tp_as_mapping slot in the PyTypeObject definition of a new type.

PyMappingMethods counter_as_mapping = {
    Hash_Len,         /* inquiry mp_length;                 /* __len__ */
    Hash_GetItem,     /* binaryfunc mp_subscript            /* __getitem__ */
    Hash_SetItem,     /* objobjargproc mp_ass_subscript;    /* __setitem__ */
};

As with emulating sequences, to remove an item from a mapping, the object passed to the function in the mp_ass_subscript slot is NULL.

If a slot does not contain a function, replace it with 0.

Getting the length

The length here is stored in the structure, but could be determined by other means.

int
Hash_len(self)
  PyObject *self;
  { return Hash_size(self);
  }

Accessing an item

It is up to the subscript functions to handle when the key is unhashable.

PyObject *
Hash_GetItem(self, key)
  PyObject *self, *key;
  { int hash_value, index;
    struct bucket *p;

    hash_value = PyObject_Hash(key);
    if (hash_value == -1)
      return (PyObject *)NULL;
    index = hash_value % HASH_SIZE;
    p = Hash_table(self)[index];
    for (; p != NULL; p = p->next)
      if (p->hash == hash_value)
        return p->object;
    PyErr_SetObject(PyExc_KeyError, key);
    return (PyObject *)NULL;
  }

The key is a Python object of any type.

Assigning an item

int
Hash_SetItem(self, key, value)
  PyObject *self, *key, *value;
  { int hash_value, index;
    struct bucket *p, *r;

    hash_value = PyObject_Hash(key);
    if (hash_value == -1)
      return -1;
    index = hash_value % HASH_SIZE;
    p = Hash_table(self)[index];

    if (p == NULL) {
      if (value == NULL) {
        PyErr_SetObject(PyExc_KeyError, key);
        return -1;
      } else {
        p = (struct bucket *)Py_Malloc(sizeof(struct bucket));
        p->hash = hash_value;
        p->object = value;
        Py_INCREF(value);
        p->next = NULL;
        Hash_table(self)[index] = p;
        Hash_size(self)++;
      }
    } else {

      for (r = NULL; p != NULL; r = p, p = p->next)
        if (p->hash == hash_value)
          break;

      if (value == NULL && p == NULL) {
        PyErr_SetObject(PyExc_KeyError, key);
        return -1;
      } else if (p == NULL) {
        p = (struct bucket *)Py_Malloc(sizeof(struct bucket));
        p->hash = hash_value;
        p->object = value;
        Py_INCREF(value);
        p->next = r->next;
        r->next = p;
        Hash_size(self)++;
      } else if (value == NULL) {
        if (r == NULL)
          Hash_table(self)[index] = p->next;
        else
          r->next = p->next;
        Py_DECREF(value);
        p->hash = -1;
        p->object = p->next = NULL;
        Py_Free(p);
        Hash_size(self)--;
      } else {
        Py_DECREF(p->object);
        p->object = value;
        Py_INCREF(p->object);
      }
    }
    return 0;
  }

Other methods

has_key
items
keys
values

Suggested methods

clear
copy
get
update