diff options
| -rw-r--r-- | include/darray.h | 17 | ||||
| -rw-r--r-- | include/hashtable.h | 35 | ||||
| -rw-r--r-- | src/hashtable.c | 85 |
3 files changed, 66 insertions, 71 deletions
diff --git a/include/darray.h b/include/darray.h index a5fff87..f20cb82 100644 --- a/include/darray.h +++ b/include/darray.h @@ -5,19 +5,18 @@ extern "C" {
#endif
-// size is at least 0x18 bytes
-typedef struct unkStruct2 {
- s32 unk0; // TODO: number of elements in array
+typedef struct DArray {
+ s32 size;
s32 unk4;
- u32 unk8; // TODO: size of each element
+ u32 elementSz;
s32 unkC;
s32 unk10;
- char *unk14; // TODO: pointer to start of array
-} unkStruct2;
+ char *buf;
+} DArray;
-
-void *ArrayNth(unkStruct2 *p1, s32 p2);
-void *ArrayMapBackwards2(unkStruct2 *p1, s32 p2, s32 p3);
+void *ArrayNew(s32 p1, s32 p3, s32 p6);
+void *ArrayNth(DArray *p1, s32 p2);
+void *ArrayMapBackwards2(DArray *p1, s32 p2, s32 p3);
#ifdef __cplusplus
}
diff --git a/include/hashtable.h b/include/hashtable.h index 93d27cd..0502273 100644 --- a/include/hashtable.h +++ b/include/hashtable.h @@ -9,25 +9,24 @@ extern "C" { typedef s32 (*HashFunction)(void *, s32);
-// size 0x14
-// hashtable
-typedef struct unkStruct {
- unkStruct2 **unk0;
- s32 unk4; // TODO: number of elements in unk0
+
+typedef struct HashTable {
+ DArray **chains;
+ s32 size;
s32 unk8;
- HashFunction unkC; // TODO: callback to hashing function
- s32 unk10;
-} unkStruct;
-
-unkStruct *TableNew(s32 p1, s32 p2, HashFunction p3, s32 p4, s32 p5);
-unkStruct *TableNew2(s32 p1, s32 p2, s32 p3, HashFunction p4, s32 p5, s32 p6);
-void TableFree(unkStruct *p1);
-s32 TableCount(unkStruct *p1);
-void TableEnter(unkStruct *p1, void *p2);
-BOOL TableRemove(unkStruct *p1, void *p2);
-void *TableLookup(unkStruct *p1, void *p2);
-void TableMapSafe(unkStruct *p1, s32 p2, s32 p3);
-void *TableMapSafe2(unkStruct *p1, s32 p2, s32 p3);
+ HashFunction hashFunc;
+ s32 unk10; // comparison callback?
+} HashTable;
+
+HashTable *TableNew(s32 p1, s32 p2, HashFunction hf, s32 p4, s32 p5);
+HashTable *TableNew2(s32 p1, s32 size, s32 p3, HashFunction hf, s32 p5, s32 p6);
+void TableFree(HashTable *table);
+s32 TableCount(HashTable *table);
+void TableEnter(HashTable *table, void *elem);
+BOOL TableRemove(HashTable *table, void *elem);
+void *TableLookup(HashTable *table, void *elem);
+void TableMapSafe(HashTable *table, s32 p2, s32 p3);
+void *TableMapSafe2(HashTable *table, s32 p2, s32 p3);
#ifdef __cplusplus
}
diff --git a/src/hashtable.c b/src/hashtable.c index 4c60efd..8612f47 100644 --- a/src/hashtable.c +++ b/src/hashtable.c @@ -1,105 +1,102 @@ #include "types.h"
#include "hashtable.h"
-unkStruct *TableNew(s32 p1, s32 p2, HashFunction p3, s32 p4, s32 p5)
+HashTable *TableNew(s32 p1, s32 p2, HashFunction hf, s32 p4, s32 p5)
{
- return TableNew2(p1, p2, 4, p3, p4, p5);
+ return TableNew2(p1, p2, 4, hf, p4, p5);
}
-unkStruct *TableNew2(s32 p1, s32 p2, s32 p3, HashFunction p4, s32 p5, s32 p6)
+HashTable *TableNew2(s32 p1, s32 size, s32 p3, HashFunction hf, s32 p5, s32 p6)
{
- unkStruct *r30 = (unkStruct *)gsimalloc(sizeof(unkStruct));
- r30->unk0 = (unkStruct2 **)gsimalloc(p2 * sizeof(unkStruct2 *));
- for (s32 i = 0; i < p2; i++) {
- r30->unk0[i] = (unkStruct2 *)ArrayNew(p1, p3, p6);
+ HashTable *r30 = (HashTable *)gsimalloc(sizeof(HashTable));
+ r30->chains = (DArray **)gsimalloc(size * sizeof(DArray *));
+ for (s32 i = 0; i < size; i++) {
+ r30->chains[i] = (DArray *)ArrayNew(p1, p3, p6);
}
- r30->unk4 = p2;
+ r30->size = size;
r30->unk8 = p6;
r30->unk10 = p5;
- r30->unkC = p4;
+ r30->hashFunc = hf;
return r30;
}
-void TableFree(unkStruct *p1)
+void TableFree(HashTable *table)
{
- if (p1) {
- for (s32 i = 0; i < p1->unk4; i++) {
- ArrayFree(p1->unk0[i]);
+ if (table) {
+ for (s32 i = 0; i < table->size; i++) {
+ ArrayFree(table->chains[i]);
}
- gsifree(p1->unk0);
- gsifree(p1);
+ gsifree(table->chains);
+ gsifree(table);
}
}
-// r29: totalSize
-// r30: i
-s32 TableCount(unkStruct *p1)
+s32 TableCount(HashTable *table)
{
s32 i, totalSize = 0;
- if (!p1)
+ if (!table)
return 0;
- for (i = 0; i < p1->unk4; i++) {
- totalSize += ArrayLength(p1->unk0[i]);
+ for (i = 0; i < table->size; i++) {
+ totalSize += ArrayLength(table->chains[i]);
}
return totalSize;
}
-// TODO: p2 is element to be added
-void TableEnter(unkStruct *p1, void *p2)
+void TableEnter(HashTable *table, void *elem)
{
- if (p1) {
- s32 i = p1->unkC(p2, p1->unk4); // r31
- s32 result = ArraySearch(p1->unk0[i], p2, p1->unk10, 0, 0);
+ if (table) {
+ s32 i = table->hashFunc(elem, table->size);
+ s32 result = ArraySearch(table->chains[i], elem, table->unk10, 0, 0);
if (result == -1) {
- ArrayAppend(p1->unk0[i], p2);
+ ArrayAppend(table->chains[i], elem);
} else {
- ArrayReplaceAt(p1->unk0[i], p2, result);
+ ArrayReplaceAt(table->chains[i], elem, result);
}
}
}
-BOOL TableRemove(unkStruct *p1, void *p2)
+BOOL TableRemove(HashTable *table, void *elem)
{
- if (!p1)
+ if (!table)
return FALSE;
- s32 i = p1->unkC(p2, p1->unk4); // r31
- s32 result = ArraySearch(p1->unk0[i], p2, p1->unk10, 0, 0);
+ s32 i = table->hashFunc(elem, table->size);
+ s32 result = ArraySearch(table->chains[i], elem, table->unk10, 0, 0);
if (result == -1) {
return FALSE;
} else {
- ArrayDeleteAt(p1->unk0[i], result);
+ ArrayDeleteAt(table->chains[i], result);
return TRUE;
}
}
// TODO: array seems to be generic. Confirm that void* is the
// correct return type
-void *TableLookup(unkStruct *p1, void *p2)
+void *TableLookup(HashTable *table, void *elem)
{
- if (!p1)
+ if (!table)
return NULL;
- s32 i = p1->unkC(p2, p1->unk4);
- s32 result = ArraySearch(p1->unk0[i], p2, p1->unk10, 0, 0);
+ s32 i = table->hashFunc(elem, table->size);
+ s32 result = ArraySearch(table->chains[i], elem, table->unk10, 0, 0);
if (result == -1) {
return NULL;
} else {
- return ArrayNth(p1->unk0[i], result);
+ return ArrayNth(table->chains[i], result);
}
}
-void TableMapSafe(unkStruct *p1, s32 p2, s32 p3)
+void TableMapSafe(HashTable *table, s32 p2, s32 p3)
{
- for (s32 i = 0; i < p1->unk4; i++) {
- ArrayMapBackwards(p1->unk0[i], p2, p3);
+ for (s32 i = 0; i < table->size; i++) {
+ ArrayMapBackwards(table->chains[i], p2, p3);
}
}
-void *TableMapSafe2(unkStruct *p1, s32 p2, s32 p3)
+void *TableMapSafe2(HashTable *table, s32 p2, s32 p3)
{
s32 i;
void *result;
- for (i = 0; i < p1->unk4; i++) {
- if ((result = ArrayMapBackwards2(p1->unk0[i], p2, p3)) != NULL) {
+ for (i = 0; i < table->size; i++) {
+ if ((result = ArrayMapBackwards2(table->chains[i], p2, p3)) != NULL) {
return result;
}
}
|