about summary refs log tree commit diff stats
path: root/tools/iso/kernel.soso/hashtable.c
blob: 8b5feca0cfbe327cd997ddf0f8dc12e03ad7a40d (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include "hashtable.h"
#include "alloc.h"

typedef struct DataItem {
   uint32 data;
   uint32 key;
   uint8 used;
} DataItem;

typedef struct HashTable {
   DataItem* items;
   uint32 capacity;
} HashTable;

static uint32 hashCode(HashTable* hashTable, uint32 key) {
   return key % hashTable->capacity;
}

HashTable* HashTable_create(uint32 capacity) {
    HashTable* hashTable = kmalloc(sizeof(HashTable));
    memset((uint8*)hashTable, 0, sizeof(HashTable));
    hashTable->capacity = capacity;
    hashTable->items = kmalloc(sizeof(DataItem) * capacity);

    return hashTable;
}

void HashTable_destroy(HashTable* hashTable) {
    kfree(hashTable->items);
    kfree(hashTable);
}

DataItem* HashTable_search_internal(HashTable* hashTable, uint32 key) {
   //get the hash
   uint32 hashIndex = hashCode(hashTable, key);

   uint32 counter = 0;
   while(counter < hashTable->capacity) {
      if(hashTable->items[hashIndex].key == key) {
          if(hashTable->items[hashIndex].used == TRUE) {
              return &(hashTable->items[hashIndex]);
          }
      }

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= hashTable->capacity;

      ++counter;
   }

   return NULL;
}

BOOL HashTable_search(HashTable* hashTable, uint32 key, uint32* value) {
    DataItem* existing = HashTable_search_internal(hashTable, key);

    if (existing) {
        *value = existing->data;

        return TRUE;
    }

    return FALSE;
}

BOOL HashTable_insert(HashTable* hashTable, uint32 key, uint32 data) {
    DataItem* existing = HashTable_search_internal(hashTable, key);

    if (existing) {
        existing->data = data;

        return TRUE;
    }

    //get the hash
    uint32 hashIndex = hashCode(hashTable, key);

    uint32 counter = 0;
    //move in array until an empty or deleted cell
    while(counter < hashTable->capacity) {
        if (hashTable->items[hashIndex].used == FALSE) {
            hashTable->items[hashIndex].key = key;
            hashTable->items[hashIndex].data = data;
            hashTable->items[hashIndex].used = TRUE;

            return TRUE;
        }


        //go to next cell
        ++hashIndex;

        //wrap around the table
        hashIndex %= hashTable->capacity;

        ++counter;
    }

    return FALSE;
}

BOOL HashTable_remove(HashTable* hashTable, uint32 key) {
    DataItem* existing = HashTable_search_internal(hashTable, key);

    if (existing) {
        existing->used = FALSE;

        return TRUE;
    }

    return FALSE;
}