From 7acfca905d76140f4cc0b09c9a12de237de364cd Mon Sep 17 00:00:00 2001 From: Nick Barnes Date: Wed, 31 Oct 2001 14:40:56 +0000 Subject: Branch imports for masters. Copied from Perforce Change: 23678 ServerID: perforce.ravenbrook.com --- mps/code/table.c | 279 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 279 insertions(+) create mode 100644 mps/code/table.c (limited to 'mps/code/table.c') diff --git a/mps/code/table.c b/mps/code/table.c new file mode 100644 index 00000000000..edc8fb884b4 --- /dev/null +++ b/mps/code/table.c @@ -0,0 +1,279 @@ +/* impl.h.table: A dictionary mapping a Word to a void* + * + * $HopeName$ + * Copyright (C) 1999 Harlequin Limited. All rights reserved. + * + * .note.good-hash: As is common in hash table implementations, we + * assume that the hash function is good. + */ + +#include "table.h" +#include "mpmtypes.h" + +#include +#include +#include +#include +#include "mpstd.h" +#ifdef MPS_OS_SU +#include "ossu.h" +#endif + + +typedef unsigned long ulong; + + +#define tableUNUSED ((Word)0x2AB7E040) +#define tableDELETED ((Word)0x2AB7EDE7) +#define tableACTIVE ((Word)0x2AB7EAC2) + + +typedef struct TableEntryStruct *TableEntry; +typedef struct TableEntryStruct { + Word status; + Word key; + void *value; +} TableEntryStruct; + + +typedef struct TableStruct { + size_t length; + size_t count; + size_t limit; + TableEntry array; +} TableStruct; + + + +/* sizeFloorLog2 -- logarithm base 2 */ + +static size_t sizeFloorLog2(size_t size) +{ + size_t l = 0; + + assert(size != 0); + while(size > 1) { + ++l; + size >>= 1; + } + return l; +} + + +/* TableHash -- table hashing function */ + +static ulong TableHash(Word key) +{ + /* Shift some randomness into the low bits. */ + return (key >> 10) + key; +} + + +/* TableFind -- finds the entry for this key, or NULL + * + * .worst: In the worst case, this looks at every slot before giving up, + * but that's what you have to do in a closed hash table, to make sure + * that all the items still fit in after growing the table. + */ + +static TableEntry TableFind(Table table, Word key, int skip_deleted) +{ + ulong hash; + size_t i, mask = table->length - 1; + + hash = TableHash(key) & mask; + i = hash; + do { + switch (table->array[i].status) { + case tableACTIVE: + if (table->array[i].key == key) + return &table->array[i]; + break; + case tableDELETED: + if (!skip_deleted) + return &table->array[i]; + break; + case tableUNUSED: + return &table->array[i]; + break; + } + i = (i + 1) & mask; + } while(i != hash); + + return NULL; +} + + +/* TableGrow -- doubles the size of the table */ + +static Res TableGrow(Table table) +{ + TableEntry oldArray, newArray; + size_t i, oldLength, newLength; + + oldLength = table->length; + oldArray = table->array; + newLength = oldLength * 2; + newArray = malloc(sizeof(TableEntryStruct) * newLength); + if(newArray == NULL) return ResMEMORY; + + for(i = 0; i < newLength; ++i) { + newArray[i].key = 0; + newArray[i].value = NULL; + newArray[i].status = tableUNUSED; + } + + table->length = newLength; + table->array = newArray; + table->limit *= 2; + + for(i = 0; i < oldLength; ++i) { + if (oldArray[i].status == tableACTIVE) { + TableEntry entry; + entry = TableFind(table, oldArray[i].key, 0 /* none deleted */); + assert(entry != NULL); + assert(entry->status == tableUNUSED); + entry->key = oldArray[i].key; + entry->value = oldArray[i].value; + entry->status = tableACTIVE; + } + } + free(oldArray); + + return ResOK; +} + + +/* TableCreate -- makes a new table */ + +extern Res TableCreate(Table *tableReturn, size_t length) +{ + Table table; + size_t i; + + assert(tableReturn != NULL); + + table = malloc(sizeof(TableStruct)); + if(table == NULL) goto failMallocTable; + if (length < 2) length = 2; + /* Table size is length rounded up to the next power of 2. */ + table->length = 1 << (sizeFloorLog2(length-1) + 1); + table->count = 0; + table->limit = (size_t)(.5 * length); + table->array = malloc(sizeof(TableEntryStruct) * length); + if(table->array == NULL) goto failMallocArray; + for(i = 0; i < length; ++i) { + table->array[i].key = 0; + table->array[i].value = NULL; + table->array[i].status = tableUNUSED; + } + + *tableReturn = table; + return ResOK; + +failMallocArray: + free(table); +failMallocTable: + return ResMEMORY; +} + + +/* TableDestroy -- destroy a table */ + +extern void TableDestroy(Table table) +{ + assert(table != NULL); + free(table->array); + free(table); +} + + +/* TableLookup -- look up */ + +extern Bool TableLookup(void **valueReturn, Table table, Word key) +{ + TableEntry entry = TableFind(table, key, 1 /* skip deleted */); + + if(entry == NULL || entry->status != tableACTIVE) + return FALSE; + *valueReturn = entry->value; + return TRUE; +} + + +/* TableDefine -- add a new mapping */ + +extern Res TableDefine(Table table, Word key, void *value) +{ + TableEntry entry; + + if (table->count >= table->limit) { + Res res = TableGrow(table); + if(res != ResOK) return res; + entry = TableFind(table, key, 0 /* no deletions yet */); + assert(entry != NULL); + if (entry->status == tableACTIVE) + return ResFAIL; + } else { + entry = TableFind(table, key, 1 /* skip deleted */); + if (entry != NULL && entry->status == tableACTIVE) + return ResFAIL; + /* Search again to find the best slot, deletions included. */ + entry = TableFind(table, key, 0 /* don't skip deleted */); + assert(entry != NULL); + } + + entry->status = tableACTIVE; + entry->key = key; + entry->value = value; + ++table->count; + + return ResOK; +} + + +/* TableRedefine -- redefine an existing mapping */ + +extern Res TableRedefine(Table table, Word key, void *value) +{ + TableEntry entry = TableFind(table, key, 1 /* skip deletions */); + + if (entry == NULL || entry->status != tableACTIVE) + return ResFAIL; + assert(entry->key == key); + entry->value = value; + return ResOK; +} + + +/* TableRemove -- remove a mapping */ + +extern Res TableRemove(Table table, Word key) +{ + TableEntry entry = TableFind(table, key, 1); + + if (entry == NULL || entry->status != tableACTIVE) + return ResFAIL; + entry->status = tableDELETED; + --table->count; + return ResOK; +} + + +/* TableMap -- apply a function to all the mappings */ + +extern void TableMap(Table table, void(*fun)(Word key, void*value)) +{ + size_t i; + for (i = 0; i < table->length; i++) + if (table->array[i].status == tableACTIVE) + (*fun)(table->array[i].key, table->array[i].value); +} + + +/* TableCount -- count the number of mappings in the table */ + +extern size_t TableCount(Table table) +{ + return table->count; +} -- cgit v1.2.1