summaryrefslogtreecommitdiff
path: root/iup/src/iup_table.c
diff options
context:
space:
mode:
Diffstat (limited to 'iup/src/iup_table.c')
-rwxr-xr-xiup/src/iup_table.c736
1 files changed, 736 insertions, 0 deletions
diff --git a/iup/src/iup_table.c b/iup/src/iup_table.c
new file mode 100755
index 0000000..9e97ff5
--- /dev/null
+++ b/iup/src/iup_table.c
@@ -0,0 +1,736 @@
+/** \file
+ * \brief iupTable functions.
+ * Implementation by Danny Reinhold and Antonio Scuri.
+ *
+ * See Copyright Notice in "iup.h"
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <memory.h>
+
+#include "iup_table.h"
+#include "iup_str.h"
+#include "iup_assert.h"
+
+/* #define DEBUGTABLE 1 */
+
+/* Adjust these parameters for optimal performance and memory usage */
+static const unsigned int itable_maxTableSizeIndex = 8;
+static const unsigned int itable_hashTableSize[] = { 31, 101, 401, 1601, 4001, 8009, 16001, 32003, 64007 };
+static const float itable_resizeLimit = 2;
+static const unsigned int itable_itemGrow = 5;
+
+/* Iteration context.
+ */
+typedef struct ItableContext
+{
+ unsigned int entryIndex; /* index at the Itable::entries array */
+ unsigned int itemIndex; /* index at the ItableEntry::items array */
+} ItableContext;
+
+/* A key of an item.
+ * To avoid lots of string comparisions we store
+ * a keyindex as an integer.
+ * To find a key in an item list we only have to
+ * do integer comparisions.
+ * Additionally the key itself is stored in
+ * keyStr. In a string indexed hashtable this is
+ * a duplicated string, in a pointer indexed hash table
+ * this is simply the pointer (in this case keyIndex
+ * and keyStr are equal).
+*/
+typedef struct ItableKey
+{
+ unsigned long keyIndex; /* the secondary hash number */
+ const char *keyStr;
+}
+ItableKey;
+
+/* An item in the hash table.
+ * Such an item is stored in the item list of
+ * an entry.
+ */
+typedef struct ItableItem
+{
+ Itable_Types itemType;
+ ItableKey key;
+ void *value;
+}
+ItableItem;
+
+/* An entry in the hash table.
+ * An entry is chosen by an index in the hash table
+ * and contains a list of items.
+ * The number of items in this list is stored
+ * in nextItemIndex.
+ * size is the current size of the items array.
+ */
+typedef struct ItableEntry
+{
+ unsigned int nextItemIndex;
+ unsigned int size;
+ ItableItem *items;
+}
+ItableEntry;
+
+
+/* A hash table.
+ * indexType is the type of the index.
+ * entries is an array of entries. Select an
+ * entry by its index.
+ * size is the number of entries in the hash table...
+ */
+struct Itable
+{
+ unsigned int size;
+ unsigned int numberOfEntries;
+ unsigned int tableSizeIndex; /* index into itable_hashTableSize array */
+ Itable_IndexTypes indexType;
+ ItableEntry *entries;
+ ItableContext context;
+};
+
+
+/* Prototypes of private functions */
+
+static void iTableFreeItemArray(Itable_IndexTypes indexType, unsigned int nextFreeIndex,
+ ItableItem *items);
+static unsigned int iTableGetEntryIndex(Itable *it, const char *key, unsigned long *keyIndex);
+static unsigned int iTableFindItem(Itable *it, const char *key, ItableEntry **entry,
+ unsigned int *itemIndex,
+ unsigned long *keyIndex);
+static unsigned int iTableResize(Itable *it);
+static void iTableAdd(Itable *it, ItableKey *key, void *value, Itable_Types itemType);
+static void iTableUpdateArraySize(ItableEntry *entry);
+
+#ifdef DEBUGTABLE
+static void iTableShowStatistics(Itable *it);
+static void iTableCheckDuplicated(ItableItem *item, unsigned int nextItemIndex,
+ const char *key,
+ unsigned long keyIndex);
+#endif
+
+
+Itable *iupTableCreate(Itable_IndexTypes indexType)
+{
+ return iupTableCreateSized(indexType, 1); /* 101 shows to be a better start for IUP */
+}
+
+
+Itable *iupTableCreateSized(Itable_IndexTypes indexType, unsigned int initialSizeIndex)
+{
+ Itable *it = (Itable *)malloc(sizeof(struct Itable));
+
+ iupASSERT(it!=NULL);
+ if (!it)
+ return 0;
+
+ if (initialSizeIndex > itable_maxTableSizeIndex)
+ initialSizeIndex = itable_maxTableSizeIndex;
+
+ it->size = itable_hashTableSize[initialSizeIndex];
+ it->tableSizeIndex = initialSizeIndex;
+ it->numberOfEntries = 0;
+ it->indexType = indexType;
+
+ it->entries = (ItableEntry *)malloc(it->size * sizeof(ItableEntry));
+ iupASSERT(it->entries!=NULL);
+ if (!it->entries)
+ {
+ free(it);
+ return 0;
+ }
+
+ memset(it->entries, 0, it->size * sizeof(ItableEntry));
+
+ it->context.entryIndex = (unsigned int)-1;
+ it->context.itemIndex = (unsigned int)-1;
+
+ return it;
+}
+
+void iupTableClear(Itable *it)
+{
+ unsigned int i;
+
+ if (!it)
+ return;
+
+ for (i = 0; i < it->size; i++)
+ {
+ ItableEntry *entry = &(it->entries[i]);
+ if (entry->items)
+ iTableFreeItemArray(it->indexType, entry->nextItemIndex, entry->items);
+ }
+
+ it->numberOfEntries = 0;
+
+ memset(it->entries, 0, it->size * sizeof(ItableEntry));
+
+ it->context.entryIndex = (unsigned int)-1;
+ it->context.itemIndex = (unsigned int)-1;
+}
+
+void iupTableDestroy(Itable *it)
+{
+ if (!it)
+ return;
+
+#ifdef DEBUGTABLE
+ iTableShowStatistics(it);
+#endif
+
+ iupTableClear(it);
+
+ if (it->entries)
+ free(it->entries);
+
+ free(it);
+}
+
+int iupTableCount(Itable *it)
+{
+ iupASSERT(it!=NULL);
+ if (!it)
+ return 0;
+ return it->numberOfEntries;
+}
+
+void iupTableSetFunc(Itable *it, const char *key, Ifunc func)
+{
+ iupTableSet(it, key, (void*)func, IUPTABLE_FUNCPOINTER); /* type cast from function pointer to void* */
+}
+
+void iupTableSet(Itable *it, const char *key, void *value, Itable_Types itemType)
+{
+ unsigned int itemIndex,
+ itemFound;
+ unsigned long keyIndex;
+ ItableEntry *entry;
+ ItableItem *item;
+ void *v;
+
+ iupASSERT(it!=NULL);
+ iupASSERT(key!=NULL);
+ if (!it || !key || !value)
+ return;
+
+ itemFound = iTableFindItem(it, key, &entry, &itemIndex, &keyIndex);
+
+#ifdef DEBUGTABLE
+ if (it->indexType == IUPTABLE_STRINGINDEXED)
+ iTableCheckDuplicated(&(entry->items[0]), entry->nextItemIndex, key, keyIndex);
+#endif
+
+ if (!itemFound)
+ {
+ /* create a new item */
+
+ /* first check if the hash table has to be reorganized */
+ if (iTableResize(it))
+ {
+ /* We have to search for the entry again, since it may
+ * have been moved by iTableResize. */
+ iTableFindItem(it, key, &entry, &itemIndex, &keyIndex);
+ }
+
+ iTableUpdateArraySize(entry);
+
+ /* add the item at the end of the item array */
+ if (itemType == IUPTABLE_STRING)
+ v = iupStrDup(value);
+ else
+ v = value;
+
+ item = &(entry->items[entry->nextItemIndex]);
+
+ item->itemType = itemType;
+ item->key.keyIndex = keyIndex;
+ item->key.keyStr = it->indexType == IUPTABLE_STRINGINDEXED? iupStrDup(key) : key;
+ item->value = v;
+
+ entry->nextItemIndex++;
+ it->numberOfEntries++;
+ }
+ else
+ {
+ /* change an existing item */
+ void *v;
+ item = &(entry->items[itemIndex]);
+
+ if (itemType == IUPTABLE_STRING && item->itemType == IUPTABLE_STRING)
+ {
+ /* this will avoid to free + alloc of a new pointer */
+ if (iupStrEqual((char*)item->value, (char*)value))
+ return;
+ }
+
+ if (itemType == IUPTABLE_STRING)
+ v = iupStrDup(value);
+ else
+ v = value;
+
+ if (item->itemType == IUPTABLE_STRING)
+ free(item->value);
+
+ item->value = v;
+ item->itemType = itemType;
+ }
+}
+
+static void iTableRemoveItem(Itable *it, ItableEntry *entry, unsigned int itemIndex)
+{
+ ItableItem *item;
+ unsigned int i;
+
+ item = &(entry->items[itemIndex]);
+
+ if (it->indexType == IUPTABLE_STRINGINDEXED)
+ free((void *)item->key.keyStr);
+
+ if (item->itemType == IUPTABLE_STRING)
+ free(item->value);
+
+ /* order the remaining items */
+ for (i = itemIndex; i < entry->nextItemIndex-1; i++)
+ entry->items[i] = entry->items[i+1];
+
+ /* clear the non used item */
+ memset(entry->items + entry->nextItemIndex, 0, sizeof (ItableItem));
+
+ entry->nextItemIndex--;
+ it->numberOfEntries--;
+}
+
+void iupTableRemove(Itable *it, const char *key)
+{
+ unsigned int itemFound,
+ itemIndex;
+ unsigned long keyIndex;
+ ItableEntry *entry;
+
+ iupASSERT(it!=NULL);
+ iupASSERT(key!=NULL);
+ if (!it || !key)
+ return;
+
+ itemFound = iTableFindItem(it, key, &entry, &itemIndex, &keyIndex);
+ if (itemFound)
+ iTableRemoveItem(it, entry, itemIndex);
+}
+
+void *iupTableGet(Itable *it, const char *key)
+{
+ unsigned int itemFound,
+ itemIndex;
+ unsigned long keyIndex;
+ ItableEntry *entry;
+ void *value = 0;
+
+ iupASSERT(it!=NULL);
+ iupASSERT(key!=NULL);
+ if (!it || !key)
+ return 0;
+
+ itemFound = iTableFindItem(it, key, &entry, &itemIndex, &keyIndex);
+ if (itemFound)
+ value = entry->items[itemIndex].value;
+
+ return value;
+}
+
+Ifunc iupTableGetFunc(Itable *it, const char *key, void **value)
+{
+ Itable_Types itemType = IUPTABLE_POINTER;
+ *value = iupTableGetTyped(it, key, &itemType);
+ if (itemType == IUPTABLE_FUNCPOINTER)
+ return (Ifunc)(*value); /* type cast from void* to function pointer */
+ else
+ return (Ifunc)0;
+}
+
+void *iupTableGetTyped(Itable *it, const char *key, Itable_Types *itemType)
+{
+ unsigned int itemFound,
+ itemIndex;
+ unsigned long keyIndex;
+ ItableEntry *entry;
+ void *value = 0;
+
+ iupASSERT(it!=NULL);
+ iupASSERT(key!=NULL);
+ if (!it || !key)
+ return 0;
+
+ itemFound = iTableFindItem(it, key, &entry, &itemIndex, &keyIndex);
+ if (itemFound)
+ {
+ value = entry->items[itemIndex].value;
+ if (itemType)
+ *itemType = entry->items[itemIndex].itemType;
+ }
+
+ return value;
+}
+
+void *iupTableGetCurr(Itable *it)
+{
+ iupASSERT(it!=NULL);
+ if (!it || it->context.entryIndex == (unsigned int)-1
+ || it->context.itemIndex == (unsigned int)-1)
+ return 0;
+
+ return it->entries[it->context.entryIndex].items[it->context.itemIndex].value;
+}
+
+
+char *iupTableFirst(Itable *it)
+{
+ unsigned int entryIndex;
+
+ iupASSERT(it!=NULL);
+ if (!it)
+ return 0;
+
+ it->context.entryIndex = (unsigned int)-1;
+ it->context.itemIndex = (unsigned int)-1;
+
+ /* find the first used entry */
+ for (entryIndex = 0; entryIndex < it->size; entryIndex++)
+ {
+ if (it->entries[entryIndex].nextItemIndex > 0)
+ {
+ it->context.entryIndex = entryIndex;
+ it->context.itemIndex = 0;
+ return (char*)it->entries[entryIndex].items[0].key.keyStr;
+ }
+ }
+
+ return 0;
+}
+
+
+char *iupTableNext(Itable *it)
+{
+ unsigned int entryIndex;
+
+ iupASSERT(it!=NULL);
+ if (!it || it->context.entryIndex == (unsigned int)-1
+ || it->context.itemIndex == (unsigned int)-1)
+ return 0;
+
+ if (it->context.itemIndex + 1 < it->entries[it->context.entryIndex].nextItemIndex)
+ {
+ /* key in the current entry */
+ it->context.itemIndex++;
+ return (char*)it->entries[it->context.entryIndex].items[it->context.itemIndex].key.keyStr;
+ }
+ else
+ {
+ /* find the next used entry */
+ for (entryIndex = it->context.entryIndex+1; entryIndex < it->size; entryIndex++)
+ {
+ if (it->entries[entryIndex].nextItemIndex > 0)
+ {
+ it->context.entryIndex = entryIndex;
+ it->context.itemIndex = 0;
+ return (char*)it->entries[entryIndex].items[0].key.keyStr;
+ }
+ }
+ }
+
+ return 0;
+}
+
+char *iupTableRemoveCurr(Itable *it)
+{
+ char* key;
+ unsigned int entryIndex;
+ ItableEntry *entry;
+ unsigned int itemIndex;
+
+ iupASSERT(it!=NULL);
+ if (!it || it->context.entryIndex == (unsigned int)-1
+ || it->context.itemIndex == (unsigned int)-1)
+ return 0;
+
+ entry = &it->entries[it->context.entryIndex];
+ itemIndex = it->context.itemIndex;
+
+ if (it->context.itemIndex + 1 < it->entries[it->context.entryIndex].nextItemIndex)
+ {
+ /* key in the current entry */
+ it->context.itemIndex++;
+ key = (char*)it->entries[it->context.entryIndex].items[it->context.itemIndex].key.keyStr;
+
+ iTableRemoveItem(it, entry, itemIndex);
+ return key;
+ }
+ else
+ {
+ /* find the next used entry */
+ for (entryIndex = it->context.entryIndex+1; entryIndex < it->size; entryIndex++)
+ {
+ if (it->entries[entryIndex].nextItemIndex > 0)
+ {
+ it->context.entryIndex = entryIndex;
+ it->context.itemIndex = 0;
+ key = (char*)it->entries[entryIndex].items[0].key.keyStr;
+
+ iTableRemoveItem(it, entry, itemIndex);
+ return key;
+ }
+ }
+ }
+
+ return 0;
+}
+
+
+/********************************************/
+/* Private functions */
+/********************************************/
+
+
+static void iTableFreeItemArray(Itable_IndexTypes indexType, unsigned int nextFreeIndex, ItableItem *items)
+{
+ unsigned int i;
+
+ iupASSERT(items!=NULL);
+ if (!items)
+ return;
+
+ if (indexType == IUPTABLE_STRINGINDEXED)
+ {
+ for (i = 0; i < nextFreeIndex; i++)
+ free((void *)(items[i].key.keyStr));
+ }
+
+ for (i = 0; i < nextFreeIndex; i++)
+ {
+ if (items[i].itemType == IUPTABLE_STRING)
+ free(items[i].value);
+ }
+
+ free(items);
+}
+
+
+static unsigned int iTableGetEntryIndex(Itable *it, const char *key, unsigned long *keyIndex)
+{
+ if (it->indexType == IUPTABLE_STRINGINDEXED)
+ {
+ register unsigned int checksum = 0;
+
+/* Orignal version
+ unsigned int i;
+ for (i = 0; key[i]; i++)
+ checksum = checksum*31 + key[i];
+*/
+
+ while (*key)
+ {
+ checksum *= 31;
+ checksum += *key;
+ key++;
+ }
+
+ *keyIndex = checksum; /* this could NOT be dependent from table size */
+ }
+ else
+ {
+ /* Pointer indexed */
+ *keyIndex = (unsigned long)key; /* this could NOT be dependent from table size */
+ }
+
+ return (unsigned int)((*keyIndex) % it->size);
+}
+
+#ifdef DEBUGTABLE
+static void iTableCheckDuplicated(ItableItem *item, unsigned int nextItemIndex, const char *key,
+ unsigned long keyIndex)
+{
+ unsigned int i;
+ for (i = 0; i < nextItemIndex; i++, item++)
+ {
+ if (!iupStrEqual((char*)item->key.keyStr, (char*)key) &&
+ item->key.keyIndex == keyIndex)
+ {
+ fprintf(stderr, "#ERROR# Duplicated key index (%ld): %s %s \n", keyIndex,
+ (char*)item->key.keyStr,
+ (char*)key);
+ }
+ }
+}
+#endif
+
+static unsigned int iTableFindItem(Itable *it, const char *key, ItableEntry **entry,
+ unsigned int *itemIndex,
+ unsigned long *keyIndex)
+{
+ unsigned int entryIndex,
+ itemFound,
+ i;
+ ItableItem *item;
+
+ entryIndex = iTableGetEntryIndex(it, key, keyIndex);
+
+ *entry = &(it->entries[entryIndex]);
+
+ item = &((*entry)->items[0]);
+ for (i = 0; i < (*entry)->nextItemIndex; i++, item++)
+ {
+ if (it->indexType == IUPTABLE_STRINGINDEXED)
+ itemFound = item->key.keyIndex == *keyIndex;
+/* itemFound = iupStrEqual(item->key.keyStr, key); This is the original safe version */
+ else
+ itemFound = item->key.keyStr == key;
+
+ if (itemFound)
+ {
+ *itemIndex = i;
+ return 1;
+ }
+ }
+
+ /* if not found "entry", "itemIndex" and "keyIndex" will have the new insert position. */
+
+ *itemIndex = i;
+ return 0;
+}
+
+static void iTableUpdateArraySize(ItableEntry *entry)
+{
+ if (entry->nextItemIndex >= entry->size)
+ {
+ /* we have to expand the item array */
+ unsigned int newSize;
+
+ newSize = entry->size + itable_itemGrow;
+
+ entry->items = (ItableItem *)realloc(entry->items, newSize * sizeof(ItableItem));
+ iupASSERT(entry->items!=NULL);
+ if (!entry->items)
+ return;
+
+ memset(entry->items + entry->size, 0, itable_itemGrow * sizeof(ItableItem));
+
+ entry->size = newSize;
+ }
+}
+
+
+static void iTableAdd(Itable *it, ItableKey *key, void *value, Itable_Types itemType)
+{
+ unsigned int entryIndex;
+ unsigned long keyIndex;
+ ItableEntry *entry;
+ ItableItem* item;
+
+ entryIndex = iTableGetEntryIndex(it, key->keyStr, &keyIndex);
+
+ entry = &(it->entries[entryIndex]);
+ iTableUpdateArraySize(entry);
+
+ /* add a new item at the end of the item array without duplicating memory. */
+ item = &(entry->items[entry->nextItemIndex]);
+ item->itemType = itemType;
+ item->key.keyIndex = keyIndex;
+ item->key.keyStr = key->keyStr;
+ item->value = value;
+
+ entry->nextItemIndex++;
+ it->numberOfEntries++;
+}
+
+static unsigned int iTableResize(Itable *it)
+{
+ unsigned int newSizeIndex,
+ entryIndex,
+ i;
+ Itable *newTable;
+ ItableEntry *entry;
+ ItableItem *item;
+
+ /* check if we do not need to resize the hash table */
+ if (it->numberOfEntries == 0 ||
+ it->tableSizeIndex >= itable_maxTableSizeIndex ||
+ it->size / it->numberOfEntries >= itable_resizeLimit)
+ return 0;
+
+ /* create a new hash table and copy the contents of
+ * the current table into the new one
+ */
+ newSizeIndex = it->tableSizeIndex + 1;
+ newTable = iupTableCreateSized(it->indexType, newSizeIndex);
+
+ for (entryIndex = 0; entryIndex < it->size; entryIndex++)
+ {
+ entry = &(it->entries[entryIndex]);
+
+ if (entry->items)
+ {
+ item = &(entry->items[0]);
+
+ for (i = 0; i < entry->nextItemIndex; i++, item++)
+ {
+ iTableAdd(newTable, &(item->key), item->value, item->itemType);
+ }
+
+ free(entry->items);
+ }
+ }
+
+ free(it->entries);
+
+ it->size = newTable->size;
+ it->tableSizeIndex = newTable->tableSizeIndex;
+ it->numberOfEntries = newTable->numberOfEntries;
+ it->entries = newTable->entries;
+
+ free(newTable);
+
+ return 1;
+}
+
+#ifdef DEBUGTABLE
+static void iTableShowStatistics(Itable *it)
+{
+ unsigned int nofSlots = 0;
+ unsigned int nofKeys = 0;
+ double optimalNofKeysPerSlot = 0.0;
+ unsigned int nofSlotsWithMoreKeys = 0;
+ unsigned int nofSlotsWithLessKeys = 0;
+
+ unsigned int entryIndex;
+ fprintf(stderr, "\n--- HASH TABLE STATISTICS ---\n");
+ if (!it)
+ {
+ fprintf(stderr, "no hash table...\n");
+ return;
+ }
+
+ nofSlots = it->size;
+ nofKeys = it->numberOfEntries;
+ optimalNofKeysPerSlot = (double)nofKeys / (double)nofSlots;
+
+ for (entryIndex = 0; entryIndex < it->size; entryIndex++)
+ {
+ ItableEntry *entry = &(it->entries[entryIndex]);
+
+ if (entry->nextItemIndex > optimalNofKeysPerSlot + 3)
+ nofSlotsWithMoreKeys++;
+ else if (entry->nextItemIndex < optimalNofKeysPerSlot - 3)
+ nofSlotsWithLessKeys++;
+ }
+
+ fprintf(stderr, "Number of slots: %d\n", nofSlots);
+ fprintf(stderr, "Number of keys: %d\n", nofKeys);
+ fprintf(stderr, "Optimal number of keys per slot: %f\n", optimalNofKeysPerSlot);
+ fprintf(stderr, "Number of slots with much more keys: %d\n", nofSlotsWithMoreKeys);
+ fprintf(stderr, "Number of slots with far less keys: %d\n", nofSlotsWithLessKeys);
+ fprintf(stderr, "\n");
+}
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 01:39:24 +0000