Add an untested hash table implementation

4 files changed, 558 insertions, 219 deletions

diff --git a/Makefile.am b/Makefile.am
index 1896093..2a917c7 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -5,6 +5,7 @@ AM_CFLAGS=-Ilibffi/include @DEP_CFLAGS@
 libnul_la_SOURCES =	\
 	invoke.c	\
 	watch.c		\
+	hash.c		\
 	dbus.c		\
 	array.c		\
 	epoll.c		\
diff --git a/dbus.c b/dbus.c
index 3fd9652..5870055 100644
--- a/dbus.c
+++ b/dbus.c
@@ -13,7 +13,7 @@
  *  Library General Public License for more details.
  *
  *  You should have received a copy of the GNU Library General Public
- *  License along with this library; if not, write to the 
+ *  License along with this library; if not, write to the
  *  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  *  Boston, MA  02111-1307, USA.
  */
@@ -51,18 +51,18 @@ struct nul_dbus_interface_t
 struct nul_dbus_member_t
 {
     char *                      name;
-    
+
     /* For now only methods are supported, although
      * later we may also have properties and signals
      */
     nul_dbus_interface_t *	interface;	/* containing interface */
-    
+
     nul_dbus_function_t		function;
-    
+
     nul_dbus_parameter_t **     parameters;
     int                         n_inputs;
     int                         n_outputs;
-    
+
     nul_fun_def_t *		fun_def;
     nul_fun_def_t *		reply_fun;
 };
@@ -79,8 +79,6 @@ struct nul_dbus_type_t
     primitive_t type;
 };
 
-typedef void (* nul_free_func_t) (nul_ptr_t p);
-
 static nul_ptr_t *free_us;
 static int idle_handler;
 
@@ -88,20 +86,20 @@ static gboolean
 do_free (gpointer data)
 {
     nul_ptr_t *p;
-    
+
     for (p = free_us; *p; p += 2)
     {
         nul_free_func_t func = *p;
 
         func (*(p + 1));
     }
-        
+
     nul_array_free (free_us);
-    
+
     free_us = nul_array_new (nul_ptr_t);
-    
+
     idle_handler = 0;
-    
+
     return FALSE;
 }
 
@@ -116,10 +114,10 @@ idle_free (gpointer p, nul_free_func_t free_func)
     else
         free_us = nul_array_append (free_us, (void *)g_free);
     free_us = nul_array_append (free_us, p);
-    
+
     if (!idle_handler)
 	idle_handler = g_idle_add (do_free, NULL);
-    
+
     return p;
 }
 
@@ -143,29 +141,29 @@ introspect (nul_dbus_object_t *object)
 {
     nul_string_t *xml = nul_string_new ();
     nul_dbus_interface_t **itf;
-    
+
     xml = nul_string_append_printf (xml, "<node>\n");
-    
+
     for (itf = object->interfaces; *itf; ++itf)
     {
 	nul_dbus_interface_t *interface = *itf;
 	nul_dbus_member_t **mem;
-        
+
 	xml = nul_string_append_printf (
 	    xml, "  <interface name=\"%s\">\n", interface->name);
-        
+
 	for (mem = interface->members; *mem; ++mem)
 	{
 	    nul_dbus_member_t *member = *mem;
             int i;
-            
+
 	    xml = nul_string_append_printf (
 		xml, "    <method name=\"%s\">\n", member->name);
-            
+
 	    for (i = 0; member->parameters[i] != NULL; ++i)
 	    {
 		nul_dbus_parameter_t *parameter = member->parameters[i];
-                
+
 		xml = nul_string_append_printf (
 		    xml,
 		    "      <arg name=\"%s\" direction=\"%s\" type=\"%s\"/>\n",
@@ -173,16 +171,16 @@ introspect (nul_dbus_object_t *object)
 		    parameter->out? "out" : "in",
 		    make_signature (parameter->type));
 	    }
-            
+
 	    xml = nul_string_append_printf (
 		xml, "    </method>\n");
 	}
-        
+
 	xml = nul_string_append_printf (xml, "  </interface>\n");
     }
-    
+
     xml = nul_string_append_printf (xml, "</node>\n");
-    
+
     return idle_free (xml, (nul_free_func_t)nul_string_free);
 }
 
@@ -194,7 +192,7 @@ decode_arg (nul_arg_t **args,
 {
     int dbus_type = dbus_message_iter_get_arg_type (iter);
     nul_arg_t arg;
-    
+
     switch (parameter->type->type)
     {
     case UINT32:
@@ -205,7 +203,7 @@ decode_arg (nul_arg_t **args,
         }
         dbus_message_iter_get_basic (iter, &arg.v_uint32);
         break;
-        
+
     case INT32:
         if (dbus_type != DBUS_TYPE_INT32)
         {
@@ -214,7 +212,7 @@ decode_arg (nul_arg_t **args,
         }
         dbus_message_iter_get_basic (iter, &arg.v_int32);
         break;
-        
+
     case STRING:
         if (dbus_type != DBUS_TYPE_STRING)
         {
@@ -224,9 +222,9 @@ decode_arg (nul_arg_t **args,
         dbus_message_iter_get_basic (iter, &arg.v_pointer);
         break;
     }
-    
+
     *args = nul_array_append (*args, arg);
-    
+
     return TRUE;
 }
 
@@ -240,10 +238,10 @@ decode_message (nul_arg_t            **args,
     DBusMessageIter iter;
     char *d;
     int i;
-    
+
     if (!err)
         err = &d;
-    
+
     i = 0;
     if (dbus_message_iter_init (message, &iter))
     {
@@ -254,34 +252,34 @@ decode_message (nul_arg_t            **args,
                 *err = "Too many arguments received";
                 goto fail;
             }
-            
+
             if (!decode_arg (args, &iter, parameters[i], err))
                 goto fail;
 
             i++;
         } while (dbus_message_iter_next (&iter));
     }
-    
+
     if (i < n_parameters)
     {
         *err = "Too few arguments received";
         goto fail;
     }
-    
+
     return TRUE;
-    
+
 fail:
     while (i < n_parameters)
     {
         nul_arg_t arg;
-        
+
         memset (&arg, 0, sizeof (arg));
-        
+
         *args = nul_array_append (*args, arg);
-        
+
         i++;
     }
-    
+
     return FALSE;
 }
 
@@ -293,29 +291,29 @@ encode_message (DBusMessage *message,
 {
     DBusMessageIter iter;
     int i;
-    
+
     dbus_message_iter_init_append (message, &iter);
-    
+
     for (i = 0; i < n_parameters; ++i)
     {
 	nul_dbus_parameter_t *parameter = parameters[i];
-        
+
 	switch (parameter->type->type)
 	{
 	case UINT32:
 	    dbus_message_iter_append_basic (
 		&iter, DBUS_TYPE_UINT32, &(args[i].v_uint32));
 	    break;
-            
+
 	case INT32:
 	    dbus_message_iter_append_basic (
 		&iter, DBUS_TYPE_INT32, &(args[i].v_int32));
 	    break;
-            
+
 	case STRING:
 	    dbus_message_iter_append_basic (
 		&iter, DBUS_TYPE_STRING, &(args[i].v_pointer));
-            
+
 	    /* FIXME: it feels wrong that we are freeing data
 	     * passed in by the user. Maybe we should just make the
 	     * user idle_free it.
@@ -343,10 +341,10 @@ invoke (connection_t      *connection,
     nul_arg_t arg;
     char *err;
     int i;
-    
+
     if (!member->function)
         return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
-    
+
     /* Add the data pointer */
 
     arg.v_pointer = object->data;
@@ -354,43 +352,43 @@ invoke (connection_t      *connection,
     args = nul_array_append (args, arg);
 
     inputs = (nul_dbus_parameter_t **)member->parameters;
-        
+
     if (!decode_message (&args, message, member->n_inputs, inputs, &err))
     {
 	error_reply = dbus_message_new_error (
             message, DBUS_ERROR_FAILED, "FIXME: generate a real error");
-        
+
 	connection_send (connection, error_reply);
-        
+
 	result = DBUS_HANDLER_RESULT_HANDLED;
         goto out;
     }
-    
+
     for (i = member->n_inputs; member->parameters[i] != NULL; ++i)
     {
 	nul_dbus_parameter_t *parameter = member->parameters[i];
         nul_ptr_t *pa;
 
 	g_assert (parameter->out);
-        
+
         args = nul_array_append (args, arg);
 
         pa = &(args[nul_array_len (args) - 1].v_pointer);
 
         *pa = pa;
     }
-    
+
     rv = nul_fun_def_invoke (member->fun_def, (nul_function_t)member->function, args);
-    
+
     if (rv.v_int32)
     {
 	DBusMessage *reply = dbus_message_new_method_return (message);
-        
+
 	encode_message (reply,
 			member->n_outputs,
 			(nul_dbus_parameter_t **)&(member->parameters[member->n_inputs]),
 			&(args[member->n_inputs + 1]));
-        
+
 	connection_send (connection, reply);
 	dbus_message_unref (reply);
 
@@ -400,10 +398,10 @@ invoke (connection_t      *connection,
     {
 	result = DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
     }
-    
+
 out:
     nul_array_free (args);
-    
+
     return result;
 }
 
@@ -417,46 +415,46 @@ message_function (connection_t *connection,
     const char *msg_member = dbus_message_get_member (message);
     nul_dbus_object_t *object = data;
     nul_dbus_interface_t **itf;
-    
+
     g_assert (strcmp (object->name, msg_path) == 0);
-    
+
     /* Introspection */
     if (strcmp (msg_interface, INTROSPECT_INTERFACE) == 0 &&
 	strcmp (msg_member, INTROSPECT_METHOD) == 0)
     {
 	DBusMessage *reply = dbus_message_new_method_return (message);
 	const char *xml = introspect (object);
-        
+
 	dbus_message_append_args (reply,
 				  DBUS_TYPE_STRING, &xml,
 				  DBUS_TYPE_INVALID);
-        
+
 	connection_send (connection, reply);
-        
+
 	return TRUE;
     }
-    
+
     /* Normal method */
     for (itf = object->interfaces; *itf; ++itf)
     {
 	nul_dbus_interface_t *interface = *itf;
-        
+
 	if (strcmp (msg_interface, interface->name) == 0)
 	{
             nul_dbus_member_t **mem;
-            
+
 	    for (mem = interface->members; *mem; ++mem)
 	    {
 		nul_dbus_member_t *member = *mem;
-                
+
 		if (strcmp (member->name, msg_member) == 0)
 		    return invoke (connection, object, member, message);
 	    }
 	}
     }
-    
+
     g_print ("got unknown message\n");
-    
+
     return FALSE;
 }
 
@@ -465,20 +463,20 @@ make_ptr_array (gpointer first, va_list parameters)
 {
     nul_ptr_t *array = nul_array_new (nul_ptr_t);
     gpointer v;
-    
+
     if (first)
     {
         array = nul_array_append (array, first);
-        
+
 	v = va_arg (parameters, gpointer);
 	while (v)
 	{
 	    array = nul_array_append (array, v);
-            
+
 	    v = va_arg (parameters, gpointer);
 	}
     }
-    
+
     return array;
 }
 
@@ -489,19 +487,19 @@ make_service (const char *name,
 	      va_list args)
 {
     nul_dbus_service_t *service = g_new0 (nul_dbus_service_t, 1);
-    
+
     service->name = g_strdup (name);
-    
+
     service->objects = (nul_dbus_object_t **)make_ptr_array (object1, args);
-    
+
     service->connection = connection;
-    
+
     if (!service->connection)
     {
 	/* FIXME */
 	return NULL;
     }
-    
+
     return service;
 }
 
@@ -512,13 +510,13 @@ nul_dbus_session_service (const char *name,
 {
     va_list args;
     nul_dbus_service_t *service;
-    
+
     va_start (args, object1);
-    
+
     service = make_service (name, connection_new_session(), object1, args);
-    
+
     va_end (args);
-    
+
     return service;
 }
 
@@ -526,10 +524,10 @@ gboolean
 nul_dbus_service_start (nul_dbus_service_t *service)
 {
     int i;
-    
+
     if (service->running)
 	return FALSE;
-    
+
     if (connection_request_name (service->connection,
                                  service->name))
     {
@@ -541,12 +539,12 @@ nul_dbus_service_start (nul_dbus_service_t *service)
             connection_register_object (
                 service->connection, object->name, message_function, object);
         }
-    
+
         service->running = TRUE;
 
         return TRUE;
     }
-    
+
     return FALSE;
 }
 
@@ -554,10 +552,10 @@ void
 nul_dbus_service_stop (nul_dbus_service_t *service)
 {
     nul_dbus_object_t **obj;
-    
+
     if (!service->running)
 	return;
-    
+
     for (obj = service->objects; *obj != NULL; ++obj)
     {
         nul_dbus_object_t *object = *obj;
@@ -565,9 +563,9 @@ nul_dbus_service_stop (nul_dbus_service_t *service)
         connection_unregister_object (
             service->connection, object->name);
     }
-    
+
     connection_release_name (service->connection, service->name);
-    
+
     service->running = FALSE;
 }
 
@@ -579,16 +577,16 @@ nul_dbus_object (const char *name,
 {
     nul_dbus_object_t *object = g_new0 (nul_dbus_object_t, 1);
     va_list args;
-    
+
     object->name = g_strdup (name);
     object->data = data;
-    
+
     va_start (args, interface1);
     object->interfaces = (nul_dbus_interface_t **)make_ptr_array (interface1, args);
     va_end (args);
-    
+
     /* Add introspection interface */
-    
+
     /* Note: the actual introspection is special cased in invoke(), but we
      * still add it here so that introspection can treat the introspection
      * interface as any other interface
@@ -604,7 +602,7 @@ nul_dbus_object (const char *name,
                     nul_dbus_type_string()),
                 NULL),
             NULL));
-    
+
     return object;
 }
 
@@ -616,16 +614,16 @@ nul_dbus_interface (const char *name,
     nul_dbus_interface_t *interface = g_new0 (nul_dbus_interface_t, 1);
     va_list parameters;
     nul_dbus_member_t **mem;
-    
+
     interface->name = g_strdup (name);
-    
+
     va_start (parameters, member1);
     interface->members = (nul_dbus_member_t **)make_ptr_array (member1, parameters);
     va_end (parameters);
-    
+
     for (mem = interface->members; *mem; ++mem)
 	(* mem)->interface = interface;
-    
+
     return interface;
 }
 
@@ -633,9 +631,9 @@ static nul_dbus_type_t *
 type_copy (const nul_dbus_type_t *type)
 {
     nul_dbus_type_t *copy = g_new0 (nul_dbus_type_t, 1);
-    
+
     copy->type = type->type;
-    
+
     return copy;
 }
 
@@ -651,7 +649,7 @@ invoke_type_from_nul_dbus_type (nul_dbus_type_t *t)
     case STRING:
 	return NUL_TYPE_POINTER;
     }
-    
+
     g_warning ("Unknown type %d\n", t->type);
     return -1;
 }
@@ -661,21 +659,21 @@ make_fun_def (nul_dbus_member_t *member)
 {
     nul_type_t *types;
     int i;
-    
+
     types = idle_free (g_new0 (nul_type_t,
                                nul_array_len (member->parameters) + 1), NULL);
     types[0] = NUL_TYPE_POINTER; /* For object->data */
-    
+
     for (i = 1; i < nul_array_len (member->parameters); ++i)
     {
 	nul_dbus_parameter_t *par = member->parameters[i - 1];
-        
+
 	if (par->out)
 	    types[i] = NUL_TYPE_POINTER;
 	else
 	    types[i] = invoke_type_from_nul_dbus_type (par->type);
     }
-    
+
     return nul_fun_def_new (NUL_TYPE_INT,
 			    nul_array_len (member->parameters) + 1,
 			    types);
@@ -687,25 +685,25 @@ make_reply_fun (nul_dbus_member_t *member)
     nul_type_t *types;
     nul_dbus_parameter_t **p;
     int n;
-    
+
     types = idle_free (g_new0 (nul_type_t,
                                nul_array_len (member->parameters) + 2), NULL);
-    
+
     n = 0;
     for (p = member->parameters; *p; ++p)
     {
 	nul_dbus_parameter_t *par = *p;
-        
+
         g_assert (*p != NULL);
         g_assert (par != NULL);
-        
+
 	if (par->out)
 	    types[n++] = invoke_type_from_nul_dbus_type (par->type);
     }
-    
+
     types[n++] = NUL_TYPE_POINTER;	/* data */
     types[n++] = NUL_TYPE_POINTER;	/* const GError *err */
-    
+
     return nul_fun_def_new (NUL_TYPE_VOID, n, types);
 }
 
@@ -718,23 +716,23 @@ nul_dbus_method (const char *name,
     nul_dbus_member_t *member = g_new0 (nul_dbus_member_t, 1);
     va_list parameters;
     nul_dbus_parameter_t **p;
-    
+
     member->name = g_strdup (name);
     member->function = function;
-    
+
     va_start (parameters, parameter1);
     member->parameters = (nul_dbus_parameter_t **)make_ptr_array (parameter1, parameters);
     va_end (parameters);
-    
+
     member->n_inputs = 0;
     member->n_outputs = 0;
     for (p = member->parameters; *p; ++p)
     {
 	nul_dbus_parameter_t *par = *p;
-        
+
         g_assert (*p != NULL);
         g_assert (par != NULL);
-        
+
 	if (par->out)
 	{
 	    member->n_outputs++;
@@ -742,7 +740,7 @@ nul_dbus_method (const char *name,
 	else
 	{
 	    member->n_inputs++;
-            
+
 	    if (member->n_outputs)
 	    {
 		g_critical ("All output parameters must be specified after the input parameters");
@@ -750,10 +748,10 @@ nul_dbus_method (const char *name,
 	    }
 	}
     }
-    
+
     member->fun_def = make_fun_def (member);
     member->reply_fun = make_reply_fun (member);
-    
+
     return member;
 }
 
@@ -763,13 +761,13 @@ make_parameter (const char *name,
 		gboolean out)
 {
     nul_dbus_parameter_t *parameter = g_new0 (nul_dbus_parameter_t, 1);
-    
+
     parameter->name = g_strdup (name);
     parameter->type = type_copy (type);
     parameter->out = out;
-    
+
     return parameter;
-}    
+}
 
 nul_dbus_parameter_t *
 nul_dbus_parameter_in (const char *name,
@@ -789,9 +787,9 @@ static nul_dbus_type_t *
 make_type (nul_type_t t)
 {
     nul_dbus_type_t *type = idle_free (g_new0 (nul_dbus_type_t, 1), NULL);
-    
+
     type->type = t;
-    
+
     return type;
 }
 
@@ -831,25 +829,25 @@ on_reply (connection_t *connection,
     nul_arg_t *args;
     nul_arg_t arg;
     char *err;
-    
+
     if (!info->callback)
 	return TRUE;
-    
+
     outputs = (nul_dbus_parameter_t **)&(info->method->parameters[info->method->n_inputs]);
-    
+
     args = nul_array_new (nul_arg_t);
-    
+
     if (!decode_message (&args, reply, n_outputs, outputs, &err))
         arg.v_pointer = err;
     else
         arg.v_pointer = NULL;
     args = nul_array_append (args, arg);       /* error */
-    
+
     arg.v_pointer = info->data;
     args = nul_array_append (args, arg);
-    
+
     nul_fun_def_invoke (info->method->reply_fun, (nul_function_t)info->callback, args);
-    
+
     nul_array_free (args);
 
     return TRUE;
@@ -867,19 +865,19 @@ decode_method_desc (const char *method_desc,
 		    char **method)
 {
     char *m;
-    
+
     g_return_val_if_fail (method_desc != NULL, FALSE);
     g_return_val_if_fail (strchr (method_desc, '/') != NULL, FALSE);
     g_return_val_if_fail (strchr (method_desc, '.') != NULL, FALSE);
-    
+
     m = strrchr (method_desc, '/');
     *object_path = g_strndup (method_desc, m - method_desc);
     method_desc = m + 1;
-    
+
     m = strrchr (method_desc, '.');
     *interface = g_strndup (method_desc, m - method_desc);
     method_desc = m;
-    
+
     *method = g_strdup (m + 1);
     return TRUE;
 }
@@ -888,15 +886,15 @@ static nul_dbus_object_t *
 find_object (nul_dbus_service_t *service, const char *name)
 {
     nul_dbus_object_t **obj;
-    
+
     for (obj = service->objects; *obj != NULL; ++obj)
     {
 	nul_dbus_object_t *object = *obj;
-        
+
 	if (strcmp (object->name, name) == 0)
 	    return object;
     }
-    
+
     return NULL;
 }
 
@@ -904,15 +902,15 @@ static nul_dbus_interface_t *
 find_interface (nul_dbus_object_t *object, const char *name)
 {
     nul_dbus_interface_t **itf;
-    
+
     for (itf = object->interfaces; *itf; ++itf)
     {
 	nul_dbus_interface_t *interface = *itf;
-        
+
 	if (strcmp (interface->name, name) == 0)
 	    return interface;
     }
-    
+
     return NULL;
 }
 
@@ -920,15 +918,15 @@ static nul_dbus_member_t *
 find_member (nul_dbus_interface_t *interface, const char *name)
 {
     nul_dbus_member_t **mem;
-    
+
     for (mem = interface->members; *mem; ++mem)
     {
 	nul_dbus_member_t *member = *mem;
-        
+
 	if (strcmp (member->name, name) == 0)
 	    return member;
     }
-    
+
     return NULL;
 }
 
@@ -949,77 +947,77 @@ nul_dbus_invoke (nul_dbus_service_t *service,
     va_list args;
     InvokeInfo *info;
     nul_dbus_parameter_t **p;
-    
+
     g_return_if_fail (service != NULL);
-    
+
     if (!decode_method_desc (method_desc, &object_str, &interface_str, &method_str))
 	return;
-    
+
     object = find_object (service, object_str);
-    
+
     if (!object)
     {
         g_critical ("Object '%s' not found", object_str);
         return;
     }
-    
+
     interface = find_interface (object, interface_str);
-    
+
     if (!interface)
     {
         g_critical ("Interface '%s' not found", interface_str);
         return;
     }
-    
+
     method = find_member (interface, method_str);
-    
+
     if (!method)
     {
         g_critical ("Method '%s' not found", method_str);
         return;
     }
-    
+
     message = dbus_message_new_method_call (
 	service->name, object->name, interface->name, method->name);
-    
+
     dbus_message_iter_init_append (message, &iter);
-    
+
     va_start (args, data);
-    
+
     for (p = method->parameters; *p; ++p)
     {
 	nul_dbus_parameter_t *parameter = *p;
 	int32_t i32;
 	uint32_t u32;
 	const char *s;
-        
+
 	if (parameter->out)
 	    continue;
-        
+
 	switch (parameter->type->type)
 	{
 	case INT32:
 	    i32 = va_arg (args, int32_t);
-            
+
 	    dbus_message_iter_append_basic (&iter, DBUS_TYPE_INT32, &i32);
 	    break;
-            
+
 	case UINT32:
 	    u32 = va_arg (args, uint32_t);
-            
+
 	    dbus_message_iter_append_basic (&iter, DBUS_TYPE_UINT32, &u32);
 	    break;
-            
+
 	case STRING:
 	    s = va_arg (args, const char *);
-            
+
 	    dbus_message_iter_append_basic (&iter, DBUS_TYPE_STRING, &s);
 	    break;
 	}
     }
-    
+
     va_end (args);
-    
+
     connection = service->connection;
 
     info = g_new0 (InvokeInfo, 1);
@@ -1027,16 +1025,16 @@ nul_dbus_invoke (nul_dbus_service_t *service,
     info->callback = callback;
     info->data = data;
     info->method = method;
-    
+
     if (!connection_send_with_reply (connection, message, on_reply, info))
     {
 	/* FIXME: generate an error and call the callback */
-        
+
 	/* Or alternatively, we should deal with getting disconnected,
 	 * though it's not clear what we should do with that
 	 */
     }
-    
+
     dbus_message_unref (message);
 }
 
@@ -1046,9 +1044,8 @@ nul_dbus_service_set_object_data (nul_dbus_service_t *service,
                                   gpointer data)
 {
     nul_dbus_object_t *object = find_object (service, obj_name);
-    
+
     g_return_if_fail (object != NULL);
-    
+
     object->data = data;
 }
-
diff --git a/hash.c b/hash.c
new file mode 100644
index 0000000..090552e
--- /dev/null
+++ b/hash.c
@@ -0,0 +1,310 @@
+#include "libnul.h"
+
+typedef struct hash_entry_t hash_entry_t;
+
+struct hash_entry_t
+{
+    nul_ptr_t	key;
+    nul_ptr_t	value;
+};
+
+
+enum
+{
+    FREE,
+    IN_USE,
+    DEAD
+};
+
+/* Expand the table when more than 1/HIGH_OCCUPATION is in use.
+ * Shrink the table when less than 1/LOW_OCCUPATION is in use
+ * When resizing the table, size it such that 1/DEFAULT_OCCUPATION is in use
+ */
+#define HIGH_OCCUPATION		2
+#define DEFAULT_OCCUPATION	4
+#define LOW_OCCUPATION		8
+#define MIN_SIZE		128
+
+struct nul_hash_t
+{
+    hash_entry_t *		entries;
+
+    nul_hash_func_t		hash_func;
+    nul_hash_equal_func_t	equal_func;
+
+    nul_free_func_t		value_free_func;
+    nul_free_func_t		key_free_func;
+
+    size_t			n_items;
+    size_t			mask;
+
+    nul_ptr_t free_marker;	/* entry->value has this value when it's not in use */
+    nul_ptr_t dead_marker;	/* entry->value has this value when it's a tombstone */
+};
+
+static nul_ptr_t
+random_pointer (void)
+{
+    size_t ptr = 0;
+    int i;
+
+    for (i = 0; i < sizeof (ptr) * 8; ++i)
+    {
+	uint32_t bit = g_random_boolean();
+
+	ptr |= (bit << i);
+    }
+
+    return (nul_ptr_t)ptr;
+}
+
+static inline void
+kill_entry (nul_hash_t *hash, hash_entry_t *entry)
+{
+    if (hash->key_free_func)
+	hash->key_free_func (entry->key);
+
+    if (hash->value_free_func)
+	hash->value_free_func (entry->value);
+
+    entry->value = hash->dead_marker;
+}
+
+static inline void
+insert_internal (nul_hash_t *hash, nul_ptr_t key, nul_ptr_t value)
+{
+    size_t index = hash->hash_func (key) & hash->mask;
+    hash_entry_t *entry;
+
+    entry = &(hash->entries[index]);
+
+    while (entry->value != hash->free_marker && entry->value != hash->dead_marker)
+    {
+	if (hash->equal_func (entry->key, key))
+	{
+	    kill_entry (hash, entry);
+	    break;
+	}
+
+	index = (index + 1) & hash->mask;
+
+	entry = &(hash->entries[index]);
+    }
+
+    entry->key = key;
+    entry->value = value;
+}
+
+static void
+rehash (nul_hash_t *hash)
+{
+    hash_entry_t *old_entries;
+    size_t new_size;
+    size_t t;
+
+    new_size = 1;
+    while (new_size < MAX (hash->n_items * DEFAULT_OCCUPATION, MIN_SIZE))
+	new_size *= 2;
+
+    old_entries = hash->entries;
+
+    hash->entries = nul_array_new (hash_entry_t);
+    hash->entries = nul_array_set_size (hash->entries, new_size);
+    hash->mask = new_size - 1;
+
+    for (t = 0; t < new_size; ++t)
+    {
+	hash_entry_t *entry = &(hash->entries[t]);
+
+	entry->key = NULL;
+	entry->value = hash->free_marker;
+    }
+
+    if (old_entries)
+    {
+	for (t = 0; t < nul_array_len (old_entries); ++t)
+	{
+	    hash_entry_t *entry = &(old_entries[t]);
+
+	    insert_internal (hash, entry->key, entry->value);
+	}
+
+	nul_array_free (old_entries);
+    }
+}
+
+nul_hash_t *
+nul_hash_new (nul_hash_func_t        hash_func,
+	      nul_hash_equal_func_t  equal_func,
+	      nul_free_func_t        key_free_func,
+	      nul_free_func_t        value_free_func)
+{
+    nul_hash_t *hash = g_new (nul_hash_t, 1);
+
+    hash->entries = NULL;
+    hash->hash_func = hash_func;
+    hash->equal_func = equal_func;
+    hash->key_free_func = key_free_func;
+    hash->value_free_func = value_free_func;
+    hash->free_marker = random_pointer();
+    hash->dead_marker = random_pointer();
+    hash->n_items = 0;
+
+    rehash (hash);
+
+    return hash;
+}
+
+static void
+regenerate_markers (nul_hash_t *hash, nul_ptr_t value)
+{
+    nul_ptr_t new_free_marker, old_free_marker;
+    nul_ptr_t new_dead_marker, old_dead_marker;
+    int i;
+
+    old_dead_marker = hash->dead_marker;
+    old_free_marker = hash->free_marker;
+
+retry:
+    new_free_marker = random_pointer();
+    new_dead_marker = random_pointer();
+
+    /* Check for collisions */
+    if (new_free_marker == value			||
+	new_free_marker == old_free_marker		||
+	new_free_marker == old_dead_marker		||
+	new_dead_marker == value			||
+	new_dead_marker == old_free_marker		||
+	new_dead_marker == old_dead_marker)
+    {
+	goto retry;
+    }
+
+    for (i = 0; i < nul_array_len (hash->entries); ++i)
+    {
+	hash_entry_t *entry = &(hash->entries[i]);
+
+	if (entry->value == new_free_marker	||
+	    entry->value == new_dead_marker)
+	{
+	    goto retry;
+	}
+    }
+
+    /* Update entries */
+    for (i = 0; i < nul_array_len (hash->entries); ++i)
+    {
+	hash_entry_t *entry = &(hash->entries[i]);
+
+	if (entry->value == old_free_marker)
+	    entry->value = new_free_marker;
+
+	if (entry->value == old_dead_marker)
+	    entry->value = new_dead_marker;
+    }
+
+    hash->dead_marker = new_dead_marker;
+    hash->free_marker = new_free_marker;
+}
+
+static inline nul_bool_t
+need_rehash (nul_hash_t *hash)
+{
+    int table_size = nul_array_len (hash->entries);
+    int n_items = hash->n_items;
+
+    return
+	n_items * HIGH_OCCUPATION > table_size	||
+	MAX (n_items * LOW_OCCUPATION, MIN_SIZE) < table_size;
+}
+
+void
+nul_hash_insert (nul_hash_t            *hash,
+		 nul_ptr_t              key,
+		 nul_ptr_t              value)
+{
+    if (value == hash->free_marker || value == hash->dead_marker)
+	regenerate_markers (hash, value);
+
+    insert_internal (hash, key, value);
+
+    if (need_rehash (hash))
+	rehash (hash);
+}
+
+static inline hash_entry_t *
+find_entry (nul_hash_t *hash, nul_ptr_t key)
+{
+    size_t index = hash->hash_func (key) & hash->mask;
+    hash_entry_t *entry;
+
+    entry = &(hash->entries[index]);
+
+    while (entry->value != hash->free_marker)
+    {
+	if (entry->value != hash->dead_marker && hash->equal_func (entry->key, key))
+	    return entry;
+
+	index = (index + 1) & hash->mask;
+	entry = &(hash->entries[index]);
+    }
+
+    return NULL;
+}
+
+
+nul_ptr_t
+nul_hash_lookup  (nul_hash_t            *hash,
+		  nul_ptr_t              key)
+{
+    hash_entry_t *entry = find_entry (hash, key);
+
+    if (entry)
+	return entry->value;
+
+    return NULL;
+}
+
+nul_bool_t
+nul_hash_remove (nul_hash_t *hash,
+		 nul_ptr_t key)
+{
+    hash_entry_t *entry = find_entry (hash, key);
+
+    if (entry)
+    {
+	kill_entry (hash, entry);
+
+	if (need_rehash (hash))
+	    rehash (hash);
+
+	return TRUE;
+    }
+
+    return FALSE;
+}
+
+nul_bool_t
+nul_hash_has_key (nul_hash_t            *hash,
+		  nul_ptr_t              key)
+{
+    return !!find_entry (hash, key);
+}
+
+void
+nul_hash_free (nul_hash_t *hash)
+{
+    size_t i;
+
+    for (i = 0; i < nul_array_len (hash->entries); ++i)
+    {
+	hash_entry_t *entry = &(hash->entries[i]);
+
+	if (entry->value != hash->free_marker && entry->value != hash->dead_marker)
+	    kill_entry (hash, entry);
+    }
+
+    nul_array_free (hash->entries);
+
+    g_free (hash);
+}
diff --git a/libnul.h b/libnul.h
index 5a27380..3f01a01 100644
--- a/libnul.h
+++ b/libnul.h
@@ -1,4 +1,4 @@
-/*  libnul 
+/*  libnul
  *  Copyright (C) 2002, 2008  Søren Sandmann (sandmann@daimi.au.dk)
  *
  *  This library is free software; you can redistribute it and/or modify
@@ -46,11 +46,12 @@
 
 #define NUL_COMPILE_TIME_ASSERT(condition,text)				\
     typedef char nul_error_##text[(condition)? 1 : -1]
-    
+
 #define NUL_UR G_GNUC_WARN_UNUSED_RESULT
 
 typedef void * nul_ptr_t;
 typedef void * const nul_const_ptr_t;
+typedef int nul_bool_t;
 
 /*
  * Generic array implementation
@@ -77,7 +78,7 @@ void       nul_garray_free        (nul_ptr_t array);
 #define nul_prefix_array_append(array,member,value)			\
     _nul_prefix_array_append_impl(array,member,value)
 #define nul_prefix_array_remove(array,member,value)			\
-    _nul_prefix_array_remove_impl(array,member,value)			
+    _nul_prefix_array_remove_impl(array,member,value)
 #define nul_prefix_array_remove_fast(array,member,value)		\
     _nul_prefix_array_remove_impl(array,member,value)
 #define nul_prefix_array_len(array,member)				\
@@ -95,7 +96,7 @@ typedef char nul_string_t;
 nul_string_t *nul_string_new              (void) NUL_UR;
 void          nul_string_free             (nul_string_t        *str);
 gsize         nul_string_len              (const nul_string_t  *str);
-gboolean      nul_string_empty            (const nul_string_t  *str);
+nul_bool_t      nul_string_empty            (const nul_string_t  *str);
 nul_string_t *nul_string_append_undefined (nul_string_t        *string,
 					   gsize                n_bytes,
 					   nul_string_t       **tail) NUL_UR;
@@ -121,9 +122,9 @@ typedef struct nul_buffer_t nul_buffer_t;
 
 nul_buffer_t *      nul_buffer_new           (void);
 char *              nul_buffer_free          (nul_buffer_t *queue,
-					      gboolean      free_data);
+					      nul_bool_t      free_data);
 gsize               nul_buffer_get_length    (nul_buffer_t *queue);
-gboolean            nul_buffer_is_empty      (nul_buffer_t *queue);
+nul_bool_t            nul_buffer_is_empty      (nul_buffer_t *queue);
 const nul_string_t *nul_buffer_peek          (nul_buffer_t *queue,
 					      gsize        *n_bytes);
 nul_string_t *      nul_buffer_steal         (nul_buffer_t *queue,
@@ -144,6 +145,35 @@ void                nul_buffer_delete_head   (nul_buffer_t *queue,
 void                nul_buffer_delete_tail   (nul_buffer_t *queue,
 					      gsize         size);
 
+/*
+ * Hash tables
+ */
+typedef struct nul_hash_t nul_hash_t;
+typedef nul_bool_t (* nul_hash_equal_func_t) (nul_const_ptr_t key1,
+					      nul_const_ptr_t key2);
+
+typedef uint32_t (* nul_hash_func_t) (nul_const_ptr_t key);
+
+typedef void (* nul_free_func_t) (nul_ptr_t data);
+
+nul_hash_t *nul_hash_new     (nul_hash_func_t        hash,
+			      nul_hash_equal_func_t  equal,
+			      nul_free_func_t        free_key,
+			      nul_free_func_t        free_value);
+void        nul_hash_insert  (nul_hash_t            *hash,
+			      nul_ptr_t              key,
+			      nul_ptr_t              value);
+nul_bool_t  nul_hash_remove  (nul_hash_t            *hash,
+			      nul_ptr_t              key);
+nul_ptr_t   nul_hash_lookup  (nul_hash_t            *hash,
+			      nul_ptr_t              key);
+nul_bool_t  nul_hash_has_key (nul_hash_t            *hash,
+			      nul_ptr_t              key);
+void        nul_hash_free    (nul_hash_t            *hash);
+
+/*
+ * Dynamic function calls
+ */
 typedef union
 {
     uint32_t		v_uint32;
@@ -152,7 +182,7 @@ typedef union
     int16_t		v_int16;
     uint8_t		v_uint8;
     int8_t		v_int8;
-    
+
     unsigned int	v_uint;
     int			v_int;
     unsigned short	v_ushort;
@@ -160,9 +190,9 @@ typedef union
     unsigned char	v_uchar;
     signed char		v_schar;
     char		v_char;
-    
+
     void *		v_pointer;
-    
+
     float		v_float;
     double		v_double;
 } nul_arg_t;
@@ -175,22 +205,22 @@ typedef enum
     NUL_TYPE_INT16,
     NUL_TYPE_UINT8,
     NUL_TYPE_INT8,
-    
+
     NUL_TYPE_UINT,
     NUL_TYPE_INT,
     NUL_TYPE_USHORT,
     NUL_TYPE_SHORT,
-    
+
     NUL_TYPE_UCHAR,
     NUL_TYPE_SCHAR,
     NUL_TYPE_CHAR,
-    
+
     NUL_TYPE_POINTER,
     NUL_TYPE_STRING,
-    
+
     NUL_TYPE_DOUBLE,
     NUL_TYPE_FLOAT,
-    
+
     NUL_TYPE_VOID
 } nul_type_t;
 
@@ -219,7 +249,7 @@ typedef enum
     NUL_POLL_HANGUP	= 1 << 2,
     NUL_POLL_ERROR	= 1 << 3,
     NUL_POLL_PRIORITY	= 1 << 4,
-    
+
     NUL_POLL_RESERVED	= 1 << 5	/* This and higher bits are reserved */
 } nul_poll_event_type_t;
 
@@ -238,7 +268,7 @@ void               nul_poll_remove_fd   (nul_poll_t            *epoll,
 					 int                    fd);
 gpointer           nul_poll_get_fd_data (nul_poll_t            *epoll,
 					 int                    fd);
-gboolean           nul_poll_has_fd      (nul_poll_t            *epoll,
+nul_bool_t         nul_poll_has_fd      (nul_poll_t            *epoll,
 					 int                    fd);
 void               nul_poll_reenable_fd (nul_poll_t            *epoll,
 					 int                    fd);
@@ -270,7 +300,7 @@ void     nul_fd_set_priority_callback (int           fd,
 void	 nul_fd_set_poll_handler      (int	     fd,
 				       WatchCallback poll_handler);
 void     nul_fd_remove_watch          (int           fd);
-gboolean nul_fd_is_watched            (int           fd);
+nul_bool_t nul_fd_is_watched            (int           fd);
 
 /*
  * File utilities
@@ -283,7 +313,7 @@ char *nul_canonicalize_filename (const char *filename);
 typedef void (* signal_func_t) (int signo, gpointer data);
 
 /* FIXME: error out is required */
-gboolean nul_signal_set_handler (int signo,
+nul_bool_t nul_signal_set_handler (int signo,
 				 signal_func_t handler,
 				 gpointer data,
 				 GError **err);
@@ -299,32 +329,33 @@ typedef struct nul_dbus_parameter_t nul_dbus_parameter_t;
 typedef struct nul_dbus_arg_t nul_dbus_arg_t;
 
 /* Return TRUE for handled, FALSE for not handled */
-typedef gboolean (* nul_dbus_function_t) ();
-
-nul_dbus_service_t *  nul_dbus_session_service (const char    *name,
-						nul_dbus_object_t     *object1,
-						...);
-nul_dbus_object_t *   nul_dbus_object          (const char    *name,
-						gpointer       data,
-						nul_dbus_interface_t  *interface1,
-						...);
-nul_dbus_interface_t *nul_dbus_interface       (const char    *name,
-						nul_dbus_member_t     *member1,
-						...);
-nul_dbus_member_t *   nul_dbus_method          (const char    *name,
-						nul_dbus_function_t    function,
-						nul_dbus_parameter_t  *parameter1,
-						...);
-nul_dbus_parameter_t *nul_dbus_parameter_in    (const char    *name,
-						const nul_dbus_type_t *type);
-nul_dbus_parameter_t *nul_dbus_parameter_out   (const char    *name,
-						const nul_dbus_type_t *type);
-gboolean              nul_dbus_service_start   (nul_dbus_service_t *service);
-void                  nul_dbus_service_stop    (nul_dbus_service_t *service);
-void                  nul_dbus_service_set_object_data (nul_dbus_service_t *service,
-							const char *obj_name,
-							gpointer data);
-    
+typedef nul_bool_t (* nul_dbus_function_t) ();
+
+nul_dbus_service_t *  nul_dbus_session_service         (const char            *name,
+							nul_dbus_object_t     *object1,
+							...);
+nul_dbus_object_t *   nul_dbus_object                  (const char            *name,
+							gpointer               data,
+							nul_dbus_interface_t  *interface1,
+							...);
+nul_dbus_interface_t *nul_dbus_interface               (const char            *name,
+							nul_dbus_member_t     *member1,
+							...);
+nul_dbus_member_t *   nul_dbus_method                  (const char            *name,
+							nul_dbus_function_t    function,
+							nul_dbus_parameter_t  *parameter1,
+							...);
+nul_dbus_parameter_t *nul_dbus_parameter_in            (const char            *name,
+							const nul_dbus_type_t *type);
+nul_dbus_parameter_t *nul_dbus_parameter_out           (const char            *name,
+							const nul_dbus_type_t *type);
+nul_bool_t            nul_dbus_service_start           (nul_dbus_service_t    *service);
+void                  nul_dbus_service_stop            (nul_dbus_service_t    *service);
+void                  nul_dbus_service_set_object_data (nul_dbus_service_t    *service,
+							const char            *obj_name,
+							gpointer               data);
+
+
 /* The returned values here are automatically freed at idle. You
  * must copy them if you want to keep them around
  */
@@ -380,8 +411,8 @@ void nul_dbus_invoke (nul_dbus_service_t *service,
 
 #define _nul_prefix_array_new_impl(type,member)				\
     ((type *)nul_garray_new_prefix(					\
-	 sizeof(((type *)NULL)->member[0]),				\
-	 NUL_STRUCT_OFFSET(type,member)))
+	sizeof(((type *)NULL)->member[0]),				\
+	NUL_STRUCT_OFFSET(type,member)))
 
 #define _nul_prefix_array_append_impl(array,member,value)		\
     ((typeof (array))							\