repos / gbc

hashTable.bx

  1// Commands:
  2// s <key> <value>   - Store a key-value pair
  3// g <key>           - Get and print the value for a key
  4// p                 - Print the entire table
  5// q                 - Quit
  6//
  7
  8extrn putchar, getchar, printf, scanf, strlen, strcpy, strcmp, malloc;
  9
 10int TABLE_SIZE = 101;
 11
 12type struct Entry {
 13    key   byte*;
 14    value byte*;
 15    next  Entry*;
 16};
 17
 18Entry* table[TABLE_SIZE];
 19
 20int hash(key byte*) {
 21    result := 0;
 22    i := 0;
 23    while (key[i] != 0) {
 24        result = (31 * result + key[i]);
 25        i = i + 1;
 26    }
 27    return ((result % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE);
 28}
 29
 30void set(key, value byte*) {
 31    index := hash(key);
 32    entry := table[index];
 33
 34    while (entry != 0) {
 35        if (strcmp(entry.key, key) == 0) {
 36            strcpy(entry.value, value);
 37            return;
 38        }
 39        entry = entry.next;
 40    }
 41
 42    new_entry := malloc(sizeof(Entry));
 43    key_copy := malloc(strlen(key) + 1);
 44    strcpy(key_copy, key);
 45
 46    value_copy := malloc(strlen(value) + 1);
 47    strcpy(value_copy, value);
 48
 49    new_entry.key = key_copy;
 50    new_entry.value = value_copy;
 51    new_entry.next = table[index];
 52
 53    table[index] = new_entry;
 54}
 55
 56byte* get(key byte*) {
 57    index := hash(key);
 58    entry := table[index];
 59
 60    while (entry != 0) {
 61        if (strcmp(entry.key, key) == 0) {
 62            return (entry.value);
 63        }
 64        entry = (entry.next);
 65    }
 66
 67    return (0);
 68}
 69
 70void print_table() {
 71    i := 0;
 72    while (i < TABLE_SIZE) {
 73        entry := table[i];
 74        while (entry != 0) {
 75            // Not nil
 76            if (entry.key != 0 && entry.value != 0) {
 77                printf("Key: %s, Value: %s\n", entry.key, entry.value);
 78            }
 79            entry = entry.next;
 80        }
 81        i = i + 1;
 82    }
 83}
 84
 85void main() {
 86    printf("Simple K-V Store. (s key val, g key, p, q)\n");
 87    byte cmd[128];
 88    byte key[128];
 89    byte val[128];
 90
 91    while (1) {
 92        n := scanf("%s", cmd);
 93        if (n != 1) break;
 94
 95        if (strcmp(cmd, "s") == 0) {
 96            scanf("%s %s", key, val);
 97            set(key, val);
 98        } else if (strcmp(cmd, "g") == 0) {
 99            scanf("%s", key);
100            res := get(key);
101            if (res != 0) {
102                printf("=> %s\n", res);
103            } else {
104                printf("Key not found.\n");
105            }
106        } else if (strcmp(cmd, "p") == 0) {
107            print_table();
108        } else if (strcmp(cmd, "q") == 0) {
109            break;
110        }
111    }
112}