Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Python C Module example: building a simplistic hash table with the help of some Redis libraries (https://github.com/antirez/redis - http://redis.io/).
/*
- setup.py
from distutils.core import setup, Extension
module = Extension('ht', sources = ['zmalloc.c', 'sds.c', 'dict.c', 'python-c-module-example.c'])
setup(name = 'Hash Table', version = '1.0', ext_modules = [module])
- install.sh
# Fetch dependencies from https://github.com/antirez/redis
wget https://raw.github.com/antirez/redis/2.6/src/fmacros.h
wget https://raw.github.com/antirez/redis/2.6/src/config.h
wget https://raw.github.com/antirez/redis/2.6/src/dict.h
wget https://raw.github.com/antirez/redis/2.6/src/dict.c
wget https://raw.github.com/antirez/redis/2.6/src/zmalloc.h
wget https://raw.github.com/antirez/redis/2.6/src/zmalloc.c
wget https://raw.github.com/antirez/redis/2.6/src/sds.h
wget https://raw.github.com/antirez/redis/2.6/src/sds.c
cp /usr/include/assert.h redisassert.h
# Compile the extension
python setup.py install && python ./test.py
rm fmacros.h config.h dict.* zmalloc.* sds.* redisassert.h
- test.py
import ht
ht.set('key:1', 'aaaa')
ht.set('key:2', 'bbbb')
print ht.get('key:1')
print ht.exists('key:1')
print ht.exists('a random key')
print ht.delete('key:1')
print ht.get('key:1')
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <limits.h>
#include <sys/time.h>
#include <ctype.h>
#include <Python.h>
#include "sds.h"
typedef unsigned short int bool;
#define true 1
#define false 0
#define BUCKETS 128
typedef struct Entry {
unsigned int hash;
sds key;
sds value;
} Entry;
typedef struct Bucket {
unsigned long size;
Entry *table;
} Bucket;
typedef struct HTable {
unsigned long length;
Bucket buckets[BUCKETS];
} HTable;
/*
This is a global object which may not be the best solution,
but will do for the example
*/
static HTable HT;
static PyObject *ht_set(PyObject *self, PyObject *args) {
char *value, *key;
if ( !PyArg_ParseTuple(args, "ss", &key, &value) )
return NULL;
char *k = sdsnew(key);
char *v = sdsnew(value);
unsigned int hash = dictGenHashFunction(k, sdslen(k));
unsigned short int bucket = hash % BUCKETS;
unsigned long position = HT.buckets[bucket].size;
if ( position == 0 ){
HT.buckets[bucket].table = (Entry*)malloc(sizeof(Entry));
} else {
HT.buckets[bucket].table = (Entry*)realloc(HT.buckets[bucket].table, sizeof(Entry)*(position + 1));
}
HT.buckets[bucket].table[position].hash = hash;
HT.buckets[bucket].table[position].key = k;
HT.buckets[bucket].table[position].value = v;
HT.buckets[bucket].size += 1;
HT.length += 1;
return Py_BuildValue("iiss", bucket, hash, HT.buckets[bucket].table[position].key, HT.buckets[bucket].table[position].value);
}
static PyObject *ht_length(PyObject *self, PyObject *args) {
return Py_BuildValue("i", HT.length);
}
Entry * find(char *key) {
char *k = sdsnew(key);
unsigned int hash = dictGenHashFunction(k, sdslen(k));
unsigned short int bucket = hash % BUCKETS;
Bucket object_bucket = HT.buckets[bucket];
Entry *e;
unsigned long c = 0;
bool found = false;
/* This is a list lookup for the time ... */
for(c=0; c < object_bucket.size; c++){
if ( object_bucket.table[c].hash == hash ){
e = &object_bucket.table[c];
found = true;
break;
}
}
if ( found ){
return e;
} else {
return NULL;
}
}
static PyObject *ht_exists(PyObject *self, PyObject *args) {
char *key;
if ( !PyArg_ParseTuple(args, "s", &key) )
return NULL;
if ( find(sdsnew(key)) ) {
Py_RETURN_TRUE;
} else {
Py_RETURN_FALSE;
}
}
static PyObject *ht_del(PyObject *self, PyObject *args) {
char *key;
if ( !PyArg_ParseTuple(args, "s", &key) )
return NULL;
Entry *e = find(sdsnew(key));
if ( e ) {
unsigned int hash = (*e).hash;
char *value = (*e).value;
// instead of deleting we nullify the record in-place
(*e).hash = 0;
(*e).key = sdsnew("");
(*e).value = sdsnew("");
return Py_BuildValue("iss", hash, key, value);
} else {
Py_RETURN_NONE;
}
}
static PyObject *ht_get(PyObject *self, PyObject *args) {
char *key;
if ( !PyArg_ParseTuple(args, "s", &key) )
return NULL;
Entry *e = find(sdsnew(key));
if ( e ) {
return Py_BuildValue("iss", (*e).hash, (*e).key, (*e).value);
} else {
Py_RETURN_NONE;
}
}
static PyMethodDef HtMethods[] = {
{"set", ht_set, METH_VARARGS, "Add a key-value to the table"},
{"get", ht_get, METH_VARARGS, "Get a value from the table"},
{"delete", ht_del, METH_VARARGS, "Delete a key-value from the table"},
{"exists", ht_exists, METH_VARARGS, "Check if a key exists in the table"},
{"length", ht_length, METH_VARARGS, "Get the current table size"},
{NULL, NULL, 0, NULL}
};
void initht(void) {
(void) Py_InitModule("ht", HtMethods);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment