From 3371554acc917c4c13510eab9ebcaeadd6592762 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?=C3=98yvind=20Kol=C3=A5s?= Date: Thu, 1 Sep 2005 07:49:43 +0000 Subject: implemented hashing for object lists --- ChangeLog | 20 +++++ babl/Makefile.am | 1 + babl/babl-component.c | 2 +- babl/babl-conversion.c | 2 +- babl/babl-core.c | 4 +- babl/babl-db.c | 194 +++++++++++++++++++++++++++++++++++++++++++++++++ babl/babl-db.h | 181 +++------------------------------------------ babl/babl-extension.c | 8 +- babl/babl-fish.c | 2 +- babl/babl-format.c | 2 +- babl/babl-ids.h | 1 + babl/babl-internal.c | 8 +- babl/babl-internal.h | 24 ++++-- babl/babl-model.c | 2 +- babl/babl-sampling.c | 26 +++---- babl/babl-type.c | 2 +- babl/babl.c | 2 + 17 files changed, 278 insertions(+), 203 deletions(-) create mode 100644 babl/babl-db.c diff --git a/ChangeLog b/ChangeLog index 8e74cf3..a64f0ab 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,23 @@ +2005-09-01 Øyvind Kolås + + Added a 128 item hashtable to each object list. + + * babl/Makefile.am: added new file 'babl-db.c' + * babl/babl-db.h: moved static function ... + * babl/babl-db.c: ... here in a new file, also implemented a hashing + optimization based on the strings of names. + * babl/babl-internal.h: changed API in base class templates. + * babl/babl-component.c, + * babl/babl-extension.c, + * babl/babl-fish.c, + * babl/babl-format.c, + * babl/babl-image.c, + * babl/babl-model.c, + * babl/babl-sampling.c, + * babl/babl-type.c: changed db_insert(..) to babl_db_insert(db, ...) + + * babl/babl.c: added babl_fish_init () + 2005-08-31 Øyvind Kolås * docs/index-static.html.in: Changed ChangeLog link in NEWS section. diff --git a/babl/Makefile.am b/babl/Makefile.am index 630a672..469a4a3 100644 --- a/babl/Makefile.am +++ b/babl/Makefile.am @@ -5,6 +5,7 @@ SUBDIRS = base c_sources = \ babl.c \ babl-core.c \ + babl-db.c \ babl-component.c \ babl-conversion.c \ babl-extension.c \ diff --git a/babl/babl-component.c b/babl/babl-component.c index 46855ca..1d5b0d8 100644 --- a/babl/babl-component.c +++ b/babl/babl-component.c @@ -117,7 +117,7 @@ babl_component_new (void *first_arg, babl = component_new (first_arg, id, luma, chroma, alpha); { - Babl *ret = db_insert (babl); + Babl *ret = babl_db_insert (db, babl); if (ret!=babl) babl_free (babl); return ret; diff --git a/babl/babl-conversion.c b/babl/babl-conversion.c index 38859d0..4e85b9d 100644 --- a/babl/babl-conversion.c +++ b/babl/babl-conversion.c @@ -231,7 +231,7 @@ babl_conversion_new (void *first_arg, planar, planar_bit); { - Babl *ret = db_insert (babl); + Babl *ret = babl_db_insert (db, babl); if (ret!=babl) babl_free (babl); return ret; diff --git a/babl/babl-core.c b/babl/babl-core.c index d5fff5e..c1b0684 100644 --- a/babl/babl-core.c +++ b/babl/babl-core.c @@ -1,6 +1,5 @@ /* babl - dynamically extendable universal pixel conversion library. - * Copyright (C) 2005, Øyvind Kolås. - * + * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either @@ -45,7 +44,6 @@ convert_double_double (void *src, return n; } - static long copy_strip_1 (int src_bands, void **src, diff --git a/babl/babl-db.c b/babl/babl-db.c new file mode 100644 index 0000000..1294e1a --- /dev/null +++ b/babl/babl-db.c @@ -0,0 +1,194 @@ +/* babl - dynamically extendable universal pixel conversion library. + * Copyright (C) 2005, Øyvind Kolås. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General + * Public License along with this library; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place, Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#define _BABL_DB_C + +#include +#include "babl-internal.h" + +#define HASH_TABLE_SIZE 128 +#define DB_INITIAL_SIZE 16 +#define DB_INCREMENT_SIZE 16 + +static inline int hash (const char *str) +{ + int ret = 0; + int i = 1; + + while (*str) + ret = (ret + ( i++ * (*str ++ & 31 ))) % (HASH_TABLE_SIZE-1); + return ret; +} + +typedef struct _BablDb { + Babl *hash [HASH_TABLE_SIZE]; + int size; + int count; + Babl **items; +} _BablDb; + +Babl * +babl_db_find (BablDb *db, + const char *name) +{ + Babl *ret = babl_db_exist (db, 0, name); + + 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; +} + + +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; +} + +void +babl_db_destroy (BablDb *db) +{ + babl_free (db->items); + babl_free (db); +} + +Babl * +babl_db_insert (BablDb *db, + Babl *item) +{ + 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; + + if (db->count + 1 > db->size) /* must reallocate storage */ + { + Babl **new_items; + + new_items = babl_realloc (db->items, (db->size + DB_INCREMENT_SIZE) * sizeof (BablInstance*)); + babl_assert (new_items); + + db->items = new_items; + + /* null out the currently unused portions of memory */ + memset (db->items + db->size, 0, DB_INCREMENT_SIZE * sizeof (Babl*)); + db->size += DB_INCREMENT_SIZE; + } + + { + int key = hash (item->instance.name); + if (db->hash[key] == NULL) + db->hash[key] = item; + } + db->items[db->count++]=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 +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; + } + } +} + +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 * +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; + + babl_db_each (db, babl_db_each_exist, &data); + + return data.ret; + } +} diff --git a/babl/babl-db.h b/babl/babl-db.h index 883f81a..caa6866 100644 --- a/babl/babl-db.h +++ b/babl/babl-db.h @@ -17,7 +17,6 @@ * Boston, MA 02111-1307, USA. */ - #ifndef _DB_H #define _DB_H @@ -25,175 +24,19 @@ #error babl-db.h is only to be included after babl-internal.h #endif -#include - -#define DB_DEF static inline - -#ifndef DB_INITIAL_SIZE -#define DB_INITIAL_SIZE 16 -#endif -#ifndef DB_INCREMENT_SIZE -#define DB_INCREMENT_SIZE 16 -#endif - -static inline int hash (char *str) -{ - int ret = 0; - int i = 1; - - while (*str) - ret = (ret + ( i++ * (*str ++ & 31 ))) % 199; - return ret; -} - -/* file scope variables, for this .c file's database */ -static int db_size = 0; -static int db_entries = 0; -static Babl **db; +typedef struct _BablDb BablDb; -DB_DEF void db_init (void); -DB_DEF void db_destroy (void); -DB_DEF void db_each (BablEachFunction each_fun, +BablDb * babl_db_init (void); +void babl_db_destroy (BablDb *db); +void babl_db_each (BablDb *db, + BablEachFunction each_fun, void *user_data); -DB_DEF Babl * db_insert (Babl *entry); -DB_DEF Babl * db_exist (int id, - const char *name); - -DB_DEF Babl * db_find (const char *name) -{ - Babl *ret = db_exist (0, name); - - if (!ret) - { - const char *sample_type = "unknwon"; - - if (db[0]) - sample_type = babl_class_name (db[0]->class_type); - babl_log ("failed (query performed on a %s database)", sample_type); - } - return ret; -} - - -DB_DEF void -db_init(void) -{ - if (0==db_size) - { - db_size = DB_INITIAL_SIZE; - db = NULL; - if (db_size) - { - db = babl_calloc (sizeof (BablInstance*), db_size); - } - } -} - - -DB_DEF void -db_destroy (void) -{ - babl_free (db); - db_size = 0; - db_entries = 0; - db = NULL; -} - -DB_DEF Babl * -db_insert (Babl *babl) -{ - Babl *collision; - - if (!babl) - { - babl_log ("%s(babl=%p)", __FUNCTION__, babl); - return NULL; - } - - collision = db_exist (babl->instance.id, babl->instance.name); - - if (collision) - return collision; - - if (db_entries + 1 > db_size) /* must reallocate storage */ - { - Babl **new_db; - - new_db = babl_realloc (db, (db_size + DB_INCREMENT_SIZE) * sizeof (BablInstance*)); - if (!new_db) - { - babl_log ("unable to reallocate memory, element (%i:'%s') not inserted", - babl->instance.id, babl->instance.name); - return NULL; - } - db = new_db; - - /* null out the currently unused portions of memory */ - memset (db + db_size, 0, DB_INCREMENT_SIZE * sizeof (Babl*)); - db_size += DB_INCREMENT_SIZE; - } - babl->instance.creator = babl_extender (); - db[db_entries++]=babl; - return babl; -} - - -DB_DEF void -db_each (BablEachFunction each_fun, - void *user_data) -{ - int i; - - for (i=0; i< db_entries; i++) - { - if (db[i]) - { - if (each_fun ((Babl*) db[i], user_data)) - break; - } - } -} - -typedef struct BablDbExistData -{ - unsigned int type; - int id; - const char *name; - Babl *ret; -} BablDbExistData; - -DB_DEF int -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 */ -} - -DB_DEF Babl * -db_exist (int id, - const char *name) -{ - BablDbExistData data; - - data.id = id; - data.name = name; - data.ret = NULL; - - db_each (db_each_exist, &data); - - return data.ret; -} +Babl * babl_db_insert (BablDb *db, + Babl *entry); +Babl * babl_db_exist (BablDb *db, + int id, + const char *name); +Babl * babl_db_find (BablDb *db, + const char *name); #endif diff --git a/babl/babl-extension.c b/babl/babl-extension.c index 26ca1f8..30164a0 100644 --- a/babl/babl-extension.c +++ b/babl/babl-extension.c @@ -89,7 +89,6 @@ babl_extension_quiet_log (void) if (babl_quiet) return babl_quiet; babl_quiet = extension_new ("", NULL, NULL); - db_insert (babl_quiet); return babl_quiet; } @@ -100,13 +99,15 @@ babl_extension_base (void) void *dl_handle = NULL; void (*destroy) (void) = NULL; + if (!db) + db = babl_db_init (); babl = extension_new ("BablBase", dl_handle, destroy); babl_set_extender (babl); { - Babl *ret = db_insert (babl); + Babl *ret = babl_db_insert (db, babl); if (ret!=babl) babl_free (babl); else @@ -127,6 +128,7 @@ init_hook (void) static void destroy_hook (void) { + babl_free (babl_quiet); babl_quiet=NULL; } @@ -188,7 +190,7 @@ babl_extension_load (const char *path) return load_failed (babl); } - if (db_insert (babl) == babl) + if (babl_db_insert (db, babl) == babl) { babl_set_extender (NULL); return babl; diff --git a/babl/babl-fish.c b/babl/babl-fish.c index bdc87d8..2ba562b 100644 --- a/babl/babl-fish.c +++ b/babl/babl-fish.c @@ -101,7 +101,7 @@ babl_fish_reference_new (Babl *source, babl->fish.pixels = 0; { - Babl *ret = db_insert (babl); + Babl *ret = babl_db_insert (db, babl); if (ret!=babl) babl_free (babl); return ret; diff --git a/babl/babl-format.c b/babl/babl-format.c index d095701..cfd0056 100644 --- a/babl/babl-format.c +++ b/babl/babl-format.c @@ -249,7 +249,7 @@ babl_format_new (void *first_arg, component, sampling, type); { - Babl *ret = db_insert (babl); + Babl *ret = babl_db_insert (db, babl); if (ret!=babl) babl_free (babl); return ret; diff --git a/babl/babl-ids.h b/babl/babl-ids.h index c0fc313..9b54642 100644 --- a/babl/babl-ids.h +++ b/babl/babl-ids.h @@ -25,6 +25,7 @@ enum { BABL_TYPE_BASE = 100, BABL_U8, BABL_U16, + BABL_U32, BABL_FLOAT, BABL_DOUBLE, BABL_HALF_FLOAT, diff --git a/babl/babl-internal.c b/babl/babl-internal.c index 9ca17e8..274d87b 100644 --- a/babl/babl-internal.c +++ b/babl/babl-internal.c @@ -58,13 +58,19 @@ int babl_hmpf_on_name_lookups = 0; #include void -babl_die (void) +babl_backtrack (void) { char buf[512]; sprintf (buf,"echo bt>/tmp/babl.gdb;" "gdb -q --batch -x /tmp/babl.gdb --pid=%i 2>/dev/null", getpid()); system (buf); +} + +void +babl_die (void) +{ + babl_backtrack (); exit (-1); } diff --git a/babl/babl-internal.h b/babl/babl-internal.h index 21599a3..df05e52 100644 --- a/babl/babl-internal.h +++ b/babl/babl-internal.h @@ -37,6 +37,7 @@ #define _BABL_INTERNAL_H +#include "babl-db.h" #include "babl-ids.h" #include "babl-util.h" #include "babl-memory.h" @@ -67,6 +68,8 @@ void babl_core_init (void); /**** LOGGER ****/ #include +void babl_backtrack (void); + static inline void real_babl_log (const char *file, int line, @@ -125,13 +128,14 @@ const char *babl_class_name (BablClassType klass); void babl_internal_init (void); void babl_internal_destroy (void); +extern BablDb *db; #define BABL_DEFINE_EACH(type_name) \ void \ babl_##type_name##_each (BablEachFunction each_fun, \ - void *user_data) \ + void *user_data) \ { \ - db_each (each_fun, user_data); \ + babl_db_each (db, each_fun, user_data); \ } \ #define BABL_DEFINE_LOOKUP_BY_ID(type_name) \ @@ -139,10 +143,10 @@ Babl * \ babl_##type_name##_id (int id) \ { \ Babl *babl; \ - babl = db_exist (id, NULL); \ + babl = babl_db_exist (db, id, NULL); \ if (!babl) \ { \ - babl_log ("%s(%i): not found", __FUNCTION__, id); \ + babl_log ("%s(%i): not found", __FUNCTION__, id); \ } \ return babl; \ } @@ -157,7 +161,7 @@ babl_##type_name (const char *name) \ { \ babl_log ("%s(\"%s\"): hmpf!", __FUNCTION__, name); \ } \ - babl = db_exist (0, name); \ + babl = babl_db_exist (db, 0, name); \ \ if (!babl) \ { \ @@ -180,11 +184,15 @@ babl_##type_name (const char *name) \ #endif #define BABL_DEFINE_INIT(type_name) \ + \ +static BablDb *db=NULL; \ + \ void \ babl_##type_name##_init (void) \ { \ BABL_PRE_INIT_HOOK; \ - db_init (); \ + if (!db) \ + db=babl_db_init (); \ BABL_INIT_HOOK; \ } @@ -193,8 +201,8 @@ void \ babl_##type_name##_destroy (void) \ { \ BABL_DESTROY_PRE_HOOK; \ - db_each (each_babl_##type_name##_destroy, NULL); \ - db_destroy (); \ + babl_db_each (db,each_babl_##type_name##_destroy, NULL); \ + babl_db_destroy (db); \ BABL_DESTROY_HOOK; \ } diff --git a/babl/babl-model.c b/babl/babl-model.c index a876cc2..e43d23e 100644 --- a/babl/babl-model.c +++ b/babl/babl-model.c @@ -161,7 +161,7 @@ babl_model_new (void *first_argument, babl = model_new (create_name (name, components, component), id, components, component); { - Babl *ret = db_insert (babl); + Babl *ret = babl_db_insert (db, babl); if (ret!=babl) babl_free (babl); return ret; diff --git a/babl/babl-sampling.c b/babl/babl-sampling.c index 8d786db..13832df 100644 --- a/babl/babl-sampling.c +++ b/babl/babl-sampling.c @@ -24,8 +24,8 @@ #include "babl-internal.h" -static BablSampling db[(HORIZONTAL_MAX-HORIZONTAL_MIN+1)* - (VERTICAL_MAX-VERTICAL_MIN+1)]; +static BablSampling sampling_db[(HORIZONTAL_MAX-HORIZONTAL_MIN+1)* + (VERTICAL_MAX-VERTICAL_MIN+1)]; Babl * babl_sampling (int horizontal, @@ -35,7 +35,7 @@ babl_sampling (int horizontal, vertical<=4 && horizontal>=1 && horizontal<=4) - return (Babl*)&db [ (vertical-1) * 4 + (horizontal-1)]; + return (Babl*)&sampling_db [ (vertical-1) * 4 + (horizontal-1)]; else babl_log ("babl_samping(%i,%i): arguments out of bounds", horizontal, vertical); @@ -63,7 +63,7 @@ babl_sampling_each (BablEachFunction each_fun, for (vertical=VERTICAL_MIN; vertical<=VERTICAL_MAX; vertical++) { int index= (vertical-VERTICAL_MIN) * VERTICAL_MAX + (horizontal - HORIZONTAL_MIN); - if (each_fun (BABL (&db[index]), user_data)) + if (each_fun (BABL (&sampling_db[index]), user_data)) return; } } @@ -85,14 +85,14 @@ babl_sampling_init (void) for (vertical=VERTICAL_MIN; vertical<=VERTICAL_MAX; vertical++) { int index= (vertical-VERTICAL_MIN) * VERTICAL_MAX + (horizontal - HORIZONTAL_MIN); - db[index].instance.class_type = BABL_SAMPLING; - db[index].instance.id = 0; - db[index].horizontal = horizontal; - db[index].vertical = vertical; - db[index].instance.name = db[index].name; - db[index].name[0]='0'+horizontal; - db[index].name[1]=':'; - db[index].name[2]='0'+vertical; - db[index].name[3]='\0'; + sampling_db[index].instance.class_type = BABL_SAMPLING; + sampling_db[index].instance.id = 0; + sampling_db[index].horizontal = horizontal; + sampling_db[index].vertical = vertical; + sampling_db[index].instance.name = sampling_db[index].name; + sampling_db[index].name[0]='0'+horizontal; + sampling_db[index].name[1]=':'; + sampling_db[index].name[2]='0'+vertical; + sampling_db[index].name[3]='\0'; } } diff --git a/babl/babl-type.c b/babl/babl-type.c index 49534cc..d08a4f3 100644 --- a/babl/babl-type.c +++ b/babl/babl-type.c @@ -133,7 +133,7 @@ babl_type_new (void *first_arg, babl = type_new (first_arg, id, bits); { - Babl *ret = db_insert (babl); + Babl *ret = babl_db_insert (db, babl); if (ret!=babl) babl_free (babl); return ret; diff --git a/babl/babl.c b/babl/babl.c index 1388442..ea838ae 100644 --- a/babl/babl.c +++ b/babl/babl.c @@ -39,6 +39,8 @@ babl_init (void) babl_sanity (); babl_extension_init (); babl_sanity (); + babl_fish_init (); + babl_sanity (); } } -- cgit v1.2.3