On 19:07, Sun 09 Mar 08, Martin Nordholts wrote:
> Hi Jan
>
> We're absolutely interested in your contributions! Eagerly awaiting the
> patch :)
>
> Best regards,
> Martin Nordholts
>
Glad to hear it :) So here is the patch. Essentially, it
implements coalesced hashing as BablHashTable structure and
uses it as the babl database data structure. The code is not
long and is quite self-explanatory I believe, although I
wouldn't mind adding a few comments if needed.
Regards,
Jan
Index: babl/babl-util.c
===================================================================
--- babl/babl-util.c (revision 290)
+++ babl/babl-util.c (working copy)
@@ -22,6 +22,287 @@
#include <math.h>
#include "babl-memory.h"
#include "babl-internal.h"
+#include "babl-util.h"
+
+#define UTIL_INITIAL_LIST_SIZE 0x7F
+#define UTIL_INITIAL_HT_MASK 0x7F
+
+/* static functions declarations */
+static inline int
+hash_by_name (BablHashTable *htab,
+ const char *str);
+
+static inline int
+hash_by_id (BablHashTable *htab,
+ int id);
+
+static inline int
+hash_insert (BablHashTable *htab,
+ Babl *item);
+
+static void
+hash_rehash (BablHashTable *htab);
+
+/* BablList functions */
+
+BablList *
+babl_list_init (void)
+{
+ BablList *list = babl_calloc (sizeof (BablList), 1);
+
+ list->size = UTIL_INITIAL_LIST_SIZE;
+ list->count = 0;
+ list->items = NULL;
+ if (list->size)
+ {
+ list->items = babl_calloc (sizeof (BablInstance *), list->size);
+ }
+
+ return list;
+}
+
+void
+babl_list_destroy (BablList *list)
+{
+ babl_assert(list);
+
+ babl_free (list->items);
+ babl_free (list);
+}
+
+void
+babl_list_insert (BablList *list,
+ Babl *item)
+{
+ babl_assert(list);
+ babl_assert(BABL_IS_BABL(item));
+
+ if (list->size < list->count + 1)
+ {
+ Babl **new_items;
+
+ new_items = babl_realloc (list->items, (list->size * 2) * sizeof (BablInstance *));
+ babl_assert (new_items);
+ list->items = new_items;
+ memset (list->items + list->size, 0, list->size * sizeof (BablInstance *));
+ list->size *= 2;
+ }
+ list->items[list->count++] = item;
+}
+
+void
+babl_list_each_NEW (BablList *list,
+ BablEachFunction each_fun,
+ void *user_data)
+{
+ int i;
+
+ babl_assert(list);
+ babl_assert(each_fun);
+
+ for (i = 0; i < list->count; i++)
+ {
+ if (list->items[i])
+ {
+ if (each_fun ((Babl *) list->items[i], user_data))
+ break;
+ }
+ }
+}
+
+/* BablHashTable functions */
+
+
+inline int
+babl_hash_by_str (BablHashTable *htab,
+ const char *str)
+{
+ int hash = 0;
+
+ while (*str)
+ {
+ hash += *str++;
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+
+ return (hash & htab->mask);
+}
+
+inline int
+babl_hash_by_int (BablHashTable *htab,
+ int id)
+{
+ int hash = 0;
+ int i;
+
+ for (i = 0; i < sizeof (int); i++)
+ {
+ hash += id & 0xFF;
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ id >>= 8;
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+
+ return (hash & htab->mask);
+}
+
+static inline int
+hash_insert (BablHashTable *htab,
+ Babl *item)
+{
+ int hash = htab->hash_func(htab, item);
+
+ if (htab->data_table[hash] == NULL)
+ {
+ /* create new chain */
+ htab->data_table[hash] = item;
+ }
+ else
+ {
+ int it, oit, cursor = 0;
+
+ while ((cursor < (htab->mask + 1)) && (htab->data_table[cursor] != NULL))
+ ++cursor;
+
+ htab->data_table[cursor] = item;
+
+ for (oit = hash, it = htab->chain_table[oit]; it != -1; oit = it, it = htab->chain_table[oit])
+ ;
+ htab->chain_table[oit] = cursor;
+ }
+
+ htab->count++;
+ return 0;
+}
+
+static void
+hash_rehash (BablHashTable *htab)
+{
+ Babl *item;
+ int i;
+ BablHashTable *nhtab = babl_calloc (sizeof (BablHashTable), 1);
+
+ nhtab->data_table = NULL;
+ nhtab->chain_table = NULL;
+ nhtab->mask = (htab->mask << 1) + 1;
+ nhtab->count = 0;
+ nhtab->hash_func = htab->hash_func;
+ nhtab->find_func = htab->find_func;
+ if (nhtab->mask)
+ {
+ nhtab->data_table = babl_calloc (sizeof (BablInstance *), babl_hash_size(nhtab));
+ nhtab->chain_table = babl_malloc (sizeof (int *) * babl_hash_size(nhtab));
+ memset (nhtab->chain_table, -1, sizeof (int) * babl_hash_size(nhtab));
+ }
+
+ for (i = 0; i < babl_hash_size (htab); i++)
+ {
+ item = htab->data_table[i];
+ babl_hash_insert (nhtab, item);
+ }
+
+ htab->mask = nhtab->mask;
+ babl_free (htab->data_table);
+ babl_free (htab->chain_table);
+ htab->data_table = nhtab->data_table;
+ htab->chain_table = nhtab->chain_table;
+ babl_free (nhtab);
+}
+
+inline int
+babl_hash_size (BablHashTable *htab)
+{
+ return htab->mask + 1;
+}
+
+BablHashTable *
+babl_hash_init (BablHashValFunction hfunc,
+ BablHashFindFunction ffunc)
+{
+ BablHashTable *htab;
+
+ babl_assert(hfunc);
+ babl_assert(ffunc);
+
+ htab = babl_calloc (sizeof (BablHashTable), 1);
+ babl_assert (htab);
+
+ htab->data_table = NULL;
+ htab->chain_table = NULL;
+ htab->mask = UTIL_INITIAL_HT_MASK;
+ htab->count = 0;
+ htab->hash_func = hfunc;
+ htab->find_func = ffunc;
+ if (htab->mask)
+ {
+ htab->data_table = babl_calloc (sizeof (BablInstance *), babl_hash_size(htab));
+ htab->chain_table = babl_malloc (sizeof (int *) * babl_hash_size(htab));
+ memset (htab->chain_table, -1, sizeof (int) * babl_hash_size(htab));
+ }
+
+ return htab;
+}
+
+void
+babl_hash_destroy (BablHashTable *htab)
+{
+ babl_assert (htab);
+
+ babl_free (htab->data_table);
+ babl_free (htab->chain_table);
+ babl_free (htab);
+}
+
+int
+babl_hash_insert (BablHashTable *htab,
+ Babl *item)
+{
+ babl_assert (htab);
+ babl_assert (BABL_IS_BABL(item));
+
+ if (babl_hash_size (htab) < htab->count + 1)
+ hash_rehash (htab);
+ return hash_insert (htab, item);
+}
+
+Babl *
+babl_hash_find (BablHashTable *htab,
+ int hash,
+ void *data)
+{
+ int it;
+ Babl *item;
+
+ babl_assert (htab);
+
+ it = hash;
+ item = htab->data_table[it];
+
+ if (!item)
+ return NULL;
+
+ for (;;)
+ {
+ if (htab->find_func (item, data))
+ return item;
+ it = htab->chain_table[it];
+ if (it == -1)
+ break;
+ item = htab->data_table[it];
+ }
+
+ return NULL;
+}
+
+
+/* Utils */
static int list_length (void **list)
{
Index: babl/babl-util.h
===================================================================
--- babl/babl-util.h (revision 290)
+++ babl/babl-util.h (working copy)
@@ -21,13 +21,89 @@
#include <math.h>
-void babl_add_ptr_to_list (void ***list,
- void *new);
+typedef struct _BablHashTable BablHashTable;
+typedef struct _BablList BablList;
+
+typedef int (*BablHashValFunction) (BablHashTable *htab, Babl *item);
+typedef int (*BablHashFindFunction) (Babl *item, void *data);
+
+typedef struct _BablList
+{
+ int count;
+ int size;
+ Babl **items;
+} _BablList;
+
+typedef struct _BablHashTable
+{
+ Babl **data_table;
+ int *chain_table;
+ int mask;
+ int count;
+ BablHashValFunction hash_func;
+ BablHashFindFunction find_func;
+} _BablHashTable;
+
+
+/* BablList functions */
+
+BablList *
+babl_list_init (void);
+
+void
+babl_list_destroy (BablList *list);
+
+void
+babl_list_insert (BablList *list,
+ Babl *item);
+
+void
+babl_list_each_NEW (BablList *list,
+ BablEachFunction each_fun,
+ void *user_data);
void
babl_list_each (void **list,
- BablEachFunction each_fun,
- void *user_data);
+ BablEachFunction each_fun,
+ void *user_data);
+
+void
+babl_add_ptr_to_list (void ***list,
+ void *new);
+
+
+
+/* BablHashTable functions */
+
+BablHashTable *
+babl_hash_init (BablHashValFunction hfunc,
+ BablHashFindFunction ffunc);
+
+inline int
+babl_hash_by_str (BablHashTable *htab,
+ const char *str);
+
+inline int
+babl_hash_by_int (BablHashTable *htab,
+ int id);
+
+inline int
+babl_hash_size (BablHashTable *htab);
+
+int
+babl_hash_insert (BablHashTable *htab,
+ Babl *item);
+
+Babl *
+babl_hash_find (BablHashTable *htab,
+ int hash,
+ void *data);
+
+void
+babl_hash_destroy (BablHashTable *htab);
+
+
+/* Utils */
long
babl_ticks (void);
Index: babl/babl-db.c
===================================================================
--- babl/babl-db.c (revision 290)
+++ babl/babl-db.c (working copy)
@@ -21,106 +21,90 @@
#include <string.h>
#include "babl-internal.h"
-#define DB_INITIAL_SIZE 16
-#define DB_INCREMENT_SIZE 16
-
-static inline int hash (const char *str)
+static int
+db_find_by_name (Babl *item, void *data)
{
- int ret = 0;
- int i = 1;
-
- while (*str)
- ret = (ret + (i++ * (*str++ & 31))) % (HASH_TABLE_SIZE - 1);
- return ret;
+ if (!strcmp (item->instance.name, (char *) data))
+ return 1;
+ return 0;
}
-
-Babl *
-babl_db_find (BablDb *db,
- const char *name)
+static int
+db_find_by_id (Babl *item, void *data)
{
- Babl *ret = babl_db_exist (db, 0, name);
+ if (item->instance.id == *((int *) data))
+ return 1;
+ return 0;
+}
- if (!ret)
- {
- const char *sample_type = "unknwon";
-
- if (db->items[0])
- sample_type = babl_class_name (db->items[0]->class_type);
- babl_log ("failed (query performed on a %s database)", sample_type);
- }
- return ret;
+static int
+db_hash_by_name (BablHashTable *htab, Babl *item)
+{
+ return babl_hash_by_str (htab, item->instance.name);
}
+static int
+db_hash_by_id (BablHashTable *htab, Babl *item)
+{
+ return babl_hash_by_int (htab, item->instance.id);
+}
BablDb *
babl_db_init (void)
{
BablDb *db = babl_calloc (sizeof (BablDb), 1);
- db->size = DB_INITIAL_SIZE;
- db->count = 0;
- db->items = NULL;
- if (db->size)
- {
- db->items = babl_calloc (sizeof (BablInstance *), db->size);
- }
- return db;
-}
+ db->name_hash = babl_hash_init (db_hash_by_name, db_find_by_name);
+ db->id_hash = babl_hash_init (db_hash_by_id, db_find_by_id);
+ db->babl_list = babl_list_init ();
-
-int
-babl_db_count (BablDb *db)
-{
- return db->count;
+ return db;
}
void
babl_db_destroy (BablDb *db)
{
- babl_free (db->items);
+ babl_assert (db);
+
+ babl_hash_destroy (db->name_hash);
+ babl_hash_destroy (db->id_hash);
+ babl_list_destroy (db->babl_list);
babl_free (db);
}
Babl *
-babl_db_insert (BablDb *db,
- Babl *item)
+babl_db_find (BablDb *db,
+ const char *name)
{
- Babl *collision;
-
- babl_assert (db && item);
- babl_assert (item->instance.name);
-
- collision = babl_db_exist (db, item->instance.id, item->instance.name);
-
- if (collision)
- return collision;
+ return babl_hash_find (db->name_hash, babl_hash_by_str (db->name_hash, name), (void *) name);
+}
- if (db->count + 1 > db->size) /* must reallocate storage */
- {
- Babl **new_items;
+int
+babl_db_count (BablDb *db)
+{
+ return db->babl_list->count;
+}
- new_items = babl_realloc (db->items, (db->size + DB_INCREMENT_SIZE) * sizeof (BablInstance *));
- babl_assert (new_items);
+Babl *
+babl_db_insert (BablDb *db,
+ Babl *item)
+{
- db->items = new_items;
+ Babl *found = babl_db_exist (db, item->instance.id, item->instance.name);
- /* null out the currently unused portions of memory */
- memset (db->items + db->size, 0, DB_INCREMENT_SIZE * sizeof (Babl *));
- db->size += DB_INCREMENT_SIZE;
- }
+ if (found)
+ return found;
- {
- int key = hash (item->instance.name);
- if (db->hash[key] == NULL)
- db->hash[key] = item;
- }
- db->items[db->count++] = item;
+ if (item->instance.id)
+ babl_hash_insert (db->id_hash, item);
+ babl_hash_insert (db->name_hash, item);
+ babl_list_insert (db->babl_list, item);
/* this point all registered items pass through, a nice
* place to brand them with where the item came from. */
item->instance.creator = babl_extender ();
return item;
+
}
void
@@ -128,84 +112,31 @@ babl_db_each (BablDb *db,
BablEachFunction each_fun,
void *user_data)
{
- int i;
-
- for (i = 0; i < db->count; i++)
- {
- if (db->items[i])
- {
- if (each_fun ((Babl *) db->items[i], user_data))
- break;
- }
- }
-}
-
-static inline void
-babl_db_each_inline (BablDb *db,
- BablEachFunction each_fun,
- void *user_data)
-{
- int i;
-
- for (i = 0; i < db->count; i++)
- {
- if (db->items[i])
- {
- if (each_fun ((Babl *) db->items[i], user_data))
- break;
- }
- }
-}
-
-typedef struct BablDbExistData
-{
- int id;
- const char *name;
- Babl *ret;
-} BablDbExistData;
-
-static int
-babl_db_each_exist (Babl *babl,
- void *void_data)
-{
- BablDbExistData *data = void_data;
-
- if (data->id && data->id == babl->instance.id)
- {
- data->ret = babl;
- return 1; /* stop iterating */
- }
- else if (data->name && !strcmp (babl->instance.name, data->name))
- {
- data->ret = babl;
- return 1; /* stop iterating */
- }
- return 0; /* continue iterating */
+ babl_list_each_NEW (db->babl_list, each_fun, user_data);
}
+
Babl *
babl_db_exist (BablDb *db,
int id,
const char *name)
{
- Babl *ret = NULL;
-
- if (name)
- ret = db->hash[hash (name)];
- if (ret &&
- name[0] == ret->instance.name[0] &&
- !strcmp (name, ret->instance.name))
- return ret;
-
- {
- BablDbExistData data;
-
- data.id = id;
- data.name = name;
- data.ret = NULL;
+ if (id)
+ return babl_hash_find (db->id_hash, babl_hash_by_int (db->id_hash, id), &id);
+ return babl_hash_find (db->name_hash, babl_hash_by_str (db->name_hash, name), (void *) name);
+}
- babl_db_each_inline (db, babl_db_each_exist, &data);
+Babl *
+babl_db_exist_by_id (BablDb *db,
+ int id)
+{
+ return babl_hash_find (db->id_hash, babl_hash_by_int (db->id_hash, id), &id);
+}
- return data.ret;
- }
+Babl *
+babl_db_exist_by_name (BablDb *db,
+ const char *name)
+{
+ return babl_hash_find (db->name_hash, babl_hash_by_str (db->name_hash, name), name);
}
+
Index: babl/babl-fish.c
===================================================================
--- babl/babl-fish.c (revision 290)
+++ babl/babl-fish.c (working copy)
@@ -62,9 +62,9 @@ go_fishing (const Babl *source,
BablDb *db = babl_fish_db ();
int i;
- for (i=0; i<db->count; i++)
+ for (i=0; i<db->babl_list->count; i++)
{
- Babl *item = db->items[i];
+ Babl *item = db->babl_list->items[i];
if ((void *) source == (void *) item->fish.source &&
(void *) destination == (void *) item->fish.destination &&
(item->class_type == BABL_FISH_PATH || /* accept only paths */
Index: babl/babl-db.h
===================================================================
--- babl/babl-db.h (revision 290)
+++ babl/babl-db.h (working copy)
@@ -19,20 +19,20 @@
#ifndef _DB_H
#define _DB_H
+#include "babl-util.h"
+
#ifndef _BABL_INTERNAL_H
#error babl-db.h is only to be included after babl-internal.h
#endif
-typedef struct _BablDb BablDb;
-#define HASH_TABLE_SIZE 128
-typedef struct _BablDb
+typedef struct BablDb
{
- Babl *hash [HASH_TABLE_SIZE];
- int size;
- int count;
- Babl **items;
-} _BablDb;
+ BablHashTable *name_hash;
+ BablHashTable *id_hash;
+ BablList *babl_list;
+} BablDb;
+
BablDb * babl_db_init (void);
void babl_db_destroy (BablDb *db);
@@ -48,4 +48,12 @@ Babl * babl_db_exist (BablDb
Babl * babl_db_find (BablDb *db,
const char *name);
+Babl *
+babl_db_exist_by_id (BablDb *db,
+ int id);
+
+Babl *
+babl_db_exist_by_name (BablDb *db,
+ const char *name);
+
#endif
_______________________________________________
Gegl-developer mailing list
Gegl-developer@xxxxxxxxxxxxxxxxxxxxxx
https://lists.XCF.Berkeley.EDU/mailman/listinfo/gegl-developer
