← Back to branch summary

~jason2605/dictu/trunk

« back to all changes in this revision

Viewing changes to src/vm/table.c

  • Committer: GitHub
  • Author(s): Jason_000
  • Date: 2020-11-30 23:26:50 UTC
  • mfrom: (30.1.263)
  • Revision ID: git-v1:4923d4401e1b291604b053289ab9f435b10ee14d
Tags: v0.14.0
Merge pull request #340 from dictu-lang/develop

Release 0.14.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/vm/table.c
 
1
#include <string.h>
 
2
 
 
3
#include "memory.h"
 
4
#include "table.h"
 
5
#include "value.h"
 
6
 
 
7
#define TABLE_MAX_LOAD 0.75
 
8
 
 
9
void initTable(Table *table) {
 
10
    table->count = 0;
 
11
    table->capacityMask = -1;
 
12
    table->entries = NULL;
 
13
}
 
14
 
 
15
void freeTable(DictuVM *vm, Table *table) {
 
16
    FREE_ARRAY(vm, Entry, table->entries, table->capacityMask + 1);
 
17
    initTable(table);
 
18
}
 
19
 
 
20
bool tableGet(Table *table, ObjString *key, Value *value) {
 
21
    if (table->count == 0) return false;
 
22
 
 
23
    Entry *entry;
 
24
    uint32_t index = key->hash & table->capacityMask;
 
25
    uint32_t psl = 0;
 
26
 
 
27
    for (;;) {
 
28
        entry = &table->entries[index];
 
29
 
 
30
        if (entry->key == NULL || psl > entry->psl) {
 
31
            return false;
 
32
        }
 
33
 
 
34
        if (entry->key == key) {
 
35
            break;
 
36
        }
 
37
 
 
38
        index = (index + 1) & table->capacityMask;
 
39
        psl++;
 
40
    }
 
41
 
 
42
    *value = entry->value;
 
43
    return true;
 
44
}
 
45
 
 
46
static void adjustCapacity(DictuVM *vm, Table *table, int capacityMask) {
 
47
    Entry *entries = ALLOCATE(vm, Entry, capacityMask + 1);
 
48
    for (int i = 0; i <= capacityMask; i++) {
 
49
        entries[i].key = NULL;
 
50
        entries[i].value = NIL_VAL;
 
51
        entries[i].psl = 0;
 
52
    }
 
53
 
 
54
    Entry *oldEntries = table->entries;
 
55
    int oldMask = table->capacityMask;
 
56
 
 
57
    table->count = 0;
 
58
    table->entries = entries;
 
59
    table->capacityMask = capacityMask;
 
60
 
 
61
    for (int i = 0; i <= oldMask; i++) {
 
62
        Entry *entry = &oldEntries[i];
 
63
        if (entry->key == NULL) continue;
 
64
 
 
65
        tableSet(vm, table, entry->key, entry->value);
 
66
    }
 
67
 
 
68
    FREE_ARRAY(vm, Entry, oldEntries, oldMask + 1);
 
69
}
 
70
 
 
71
bool tableSet(DictuVM *vm, Table *table, ObjString *key, Value value) {
 
72
    if (table->count + 1 > (table->capacityMask + 1) * TABLE_MAX_LOAD) {
 
73
        // Figure out the new table size.
 
74
        int capacityMask = GROW_CAPACITY(table->capacityMask + 1) - 1;
 
75
        adjustCapacity(vm, table, capacityMask);
 
76
    }
 
77
 
 
78
    uint32_t index = key->hash & table->capacityMask;
 
79
    Entry *bucket;
 
80
    bool isNewKey = false;
 
81
 
 
82
    Entry entry;
 
83
    entry.key = key;
 
84
    entry.value = value;
 
85
    entry.psl = 0;
 
86
 
 
87
    for (;;) {
 
88
        bucket = &table->entries[index];
 
89
 
 
90
        if (bucket->key == NULL) {
 
91
            isNewKey = true;
 
92
            break;
 
93
        } else {
 
94
            if (bucket->key == key) {
 
95
                break;
 
96
            }
 
97
 
 
98
            if (entry.psl > bucket->psl) {
 
99
                isNewKey = true;
 
100
                Entry tmp = entry;
 
101
                entry = *bucket;
 
102
                *bucket = tmp;
 
103
            }
 
104
        }
 
105
 
 
106
        index = (index + 1) & table->capacityMask;
 
107
        entry.psl++;
 
108
    }
 
109
 
 
110
    *bucket = entry;
 
111
    if (isNewKey) table->count++;
 
112
    return isNewKey;
 
113
}
 
114
 
 
115
bool tableDelete(DictuVM *vm, Table *table, ObjString *key) {
 
116
    UNUSED(vm);
 
117
    if (table->count == 0) return false;
 
118
 
 
119
    int capacityMask = table->capacityMask;
 
120
    uint32_t index = key->hash & table->capacityMask;
 
121
    uint32_t psl = 0;
 
122
    Entry *entry;
 
123
 
 
124
    for (;;) {
 
125
        entry = &table->entries[index];
 
126
 
 
127
        if (entry->key == NULL || psl > entry->psl) {
 
128
            return false;
 
129
        }
 
130
 
 
131
        if (entry->key == key) {
 
132
            break;
 
133
        }
 
134
 
 
135
        index = (index + 1) & capacityMask;
 
136
        psl++;
 
137
    }
 
138
 
 
139
    table->count--;
 
140
 
 
141
    for (;;) {
 
142
        Entry *nextEntry;
 
143
        entry->key = NULL;
 
144
        entry->value = NIL_VAL;
 
145
        entry->psl = 0;
 
146
 
 
147
        index = (index + 1) & capacityMask;
 
148
        nextEntry = &table->entries[index];
 
149
 
 
150
        /*
 
151
         * Stop if we reach an empty bucket or hit a key which
 
152
         * is in its base (original) location.
 
153
         */
 
154
        if (nextEntry->key == NULL || nextEntry->psl == 0) {
 
155
            break;
 
156
        }
 
157
 
 
158
        nextEntry->psl--;
 
159
        *entry = *nextEntry;
 
160
        entry = nextEntry;
 
161
    }
 
162
 
 
163
    return true;
 
164
}
 
165
 
 
166
void tableAddAll(DictuVM *vm, Table *from, Table *to) {
 
167
    for (int i = 0; i <= from->capacityMask; i++) {
 
168
        Entry *entry = &from->entries[i];
 
169
        if (entry->key != NULL) {
 
170
            tableSet(vm, to, entry->key, entry->value);
 
171
        }
 
172
    }
 
173
}
 
174
 
 
175
// TODO: Return entry here rather than string
 
176
ObjString *tableFindString(Table *table, const char *chars, int length,
 
177
                           uint32_t hash) {
 
178
    // If the table is empty, we definitely won't find it.
 
179
    if (table->count == 0) return NULL;
 
180
 
 
181
    // Figure out where to insert it in the table. Use open addressing and
 
182
    // basic linear probing.
 
183
 
 
184
    uint32_t index = hash & table->capacityMask;
 
185
    uint32_t psl = 0;
 
186
 
 
187
    for (;;) {
 
188
        Entry *entry = &table->entries[index];
 
189
 
 
190
        if (entry->key == NULL || psl > entry->psl) {
 
191
            return NULL;
 
192
        }
 
193
 
 
194
        if (entry->key->length == length &&
 
195
            entry->key->hash == hash &&
 
196
            memcmp(entry->key->chars, chars, length) == 0) {
 
197
            // We found it.
 
198
            return entry->key;
 
199
        }
 
200
 
 
201
        index = (index + 1) & table->capacityMask;
 
202
        psl++;
 
203
    }
 
204
}
 
205
 
 
206
void tableRemoveWhite(DictuVM *vm, Table *table) {
 
207
    for (int i = 0; i <= table->capacityMask; i++) {
 
208
        Entry *entry = &table->entries[i];
 
209
        if (entry->key != NULL && !entry->key->obj.isDark) {
 
210
            tableDelete(vm, table, entry->key);
 
211
        }
 
212
    }
 
213
}
 
214
 
 
215
void grayTable(DictuVM *vm, Table *table) {
 
216
    for (int i = 0; i <= table->capacityMask; i++) {
 
217
        Entry *entry = &table->entries[i];
 
218
        grayObject(vm, (Obj *) entry->key);
 
219
        grayValue(vm, entry->value);
 
220
    }
 
221
}