sm64

A Super Mario 64 decompilation
Log | Files | Refs | README | LICENSE

hashtable.c (1784B)


      1 #include <stdint.h>
      2 #include <stdlib.h>
      3 #include <string.h>
      4 #include <stdio.h>
      5 
      6 #include "hashtable.h"
      7 
      8 struct HashNode
      9 {
     10     struct HashNode *next;
     11     uint8_t value[];
     12 };
     13 
     14 struct HashTable
     15 {
     16     HashFunc func;
     17     HashValueCmpFunc cmp;
     18     int size;
     19     int elemSize;
     20     struct HashNode *table[];
     21 };
     22 
     23 struct HashTable *hashtable_new(HashFunc func, HashValueCmpFunc cmp, int size,
     24     int elemSize)
     25 {
     26     struct HashTable *ht = malloc(sizeof(*ht) + size * sizeof(ht->table[0]));
     27 
     28     ht->func = func;
     29     ht->cmp = cmp;
     30     ht->size = size;
     31     ht->elemSize = elemSize;
     32     memset(ht->table, 0, ht->size * sizeof(ht->table[0]));
     33     return ht;
     34 }
     35 
     36 void hashtable_free(struct HashTable *ht)
     37 {
     38     int i;
     39 
     40     for (i = 0; i < ht->size; i++)
     41     {
     42         struct HashNode *node = ht->table[i];
     43 
     44         while (node != NULL)
     45         {
     46             struct HashNode *next = node->next;
     47 
     48             free(node);
     49             node = next;
     50         }
     51     }
     52     free(ht);
     53 }
     54 
     55 void hashtable_insert(struct HashTable *ht, const void *value)
     56 {
     57     unsigned int key = ht->func(value) % ht->size;
     58     struct HashNode *node = malloc(sizeof(*node) + ht->elemSize);
     59 
     60     node->next = NULL;
     61     memcpy(node->value, value, ht->elemSize);
     62 
     63     if (ht->table[key] == NULL)
     64     {
     65         ht->table[key] = node;
     66     }
     67     else
     68     {
     69         struct HashNode *parent = ht->table[key];
     70 
     71         while (parent->next != NULL)
     72             parent = parent->next;
     73         parent->next = node;
     74     }
     75 }
     76 
     77 void *hashtable_query(struct HashTable *ht, const void *value)
     78 {
     79     unsigned int key = ht->func(value) % ht->size;
     80     struct HashNode *node = ht->table[key];
     81 
     82     while (node != NULL)
     83     {
     84         if (ht->cmp(node->value, value))
     85             return node->value;
     86         node = node->next;
     87     }
     88     return NULL;
     89 }