table.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <kuroko/kuroko.h>
4 #include <kuroko/object.h>
5 #include <kuroko/value.h>
6 #include <kuroko/memory.h>
7 #include <kuroko/table.h>
8 #include <kuroko/vm.h>
9 #include <kuroko/threads.h>
10 #include <kuroko/util.h>
11 
12 #define TABLE_MAX_LOAD 3 / 4
13 
14 void krk_initTable(KrkTable * table) {
15  table->count = 0;
16  table->capacity = 0;
17  table->entries = NULL;
18 }
19 
20 void krk_freeTable(KrkTable * table) {
21  FREE_ARRAY(KrkTableEntry, table->entries, table->capacity);
22  krk_initTable(table);
23 }
24 
25 inline int krk_hashValue(KrkValue value, uint32_t *hashOut) {
26  switch (KRK_VAL_TYPE(value)) {
27  case KRK_VAL_BOOLEAN:
28  case KRK_VAL_INTEGER:
29  case KRK_VAL_NONE:
30  case KRK_VAL_HANDLER:
31  case KRK_VAL_KWARGS:
32  *hashOut = (uint32_t)AS_INTEGER(value);
33  return 0;
34  case KRK_VAL_OBJECT:
35  if (AS_OBJECT(value)->flags & KRK_OBJ_FLAGS_VALID_HASH) {
36  *hashOut = AS_OBJECT(value)->hash;
37  return 0;
38  }
39  break;
40  default:
41 #ifndef KRK_NO_FLOAT
42  *hashOut = (uint32_t)AS_FLOATING(value);
43  return 0;
44 #else
45  break;
46 #endif
47  }
48  KrkClass * type = krk_getType(value);
49  if (type && type->_hash) {
50  krk_push(value);
51  KrkValue result = krk_callDirect(type->_hash, 1);
52  if (!IS_INTEGER(result)) goto _unhashable;
53  *hashOut = (uint32_t)AS_INTEGER(result);
54  return 0;
55  }
56  if (IS_CLASS(value)) {
57  *hashOut = INTEGER_VAL((int)(intptr_t)AS_OBJECT(value));
58  return 0;
59  }
60 _unhashable:
62  krk_runtimeError(vm.exceptions->typeError, "unhashable type: '%T'", value);
63  return 1;
64 }
65 
66 KrkTableEntry * krk_findEntry(KrkTableEntry * entries, size_t capacity, KrkValue key) {
67  uint32_t index;
68  if (krk_hashValue(key, &index)) {
69  return NULL;
70  }
71  index &= (capacity-1);
72  KrkTableEntry * tombstone = NULL;
73  for (;;) {
74  KrkTableEntry * entry = &entries[index];
75  if (entry->key == KWARGS_VAL(0)) {
76  return tombstone != NULL ? tombstone : entry;
77  } else if (entry->key == KWARGS_VAL(1)) {
78  if (tombstone == entry) return tombstone;
79  if (tombstone == NULL) tombstone = entry;
80  } else if (krk_valuesSameOrEqual(entry->key, key)) {
81  return entry;
82  }
83  index = (index + 1) & (capacity-1);
84  }
85 }
86 
87 KrkTableEntry * krk_findEntryExact(KrkTableEntry * entries, size_t capacity, KrkValue key) {
88  uint32_t index;
89  if (krk_hashValue(key, &index)) {
90  return NULL;
91  }
92  index &= (capacity-1);
93  KrkTableEntry * tombstone = NULL;
94  for (;;) {
95  KrkTableEntry * entry = &entries[index];
96  if (entry->key == KWARGS_VAL(0)) {
97  return tombstone != NULL ? tombstone : entry;
98  } else if (entry->key == KWARGS_VAL(1)) {
99  if (tombstone == entry) return tombstone;
100  if (tombstone == NULL) tombstone = entry;
101  } else if (krk_valuesSame(entry->key, key)) {
102  return entry;
103  }
104  index = (index + 1) & (capacity-1);
105  }
106 }
107 
108 #ifdef __TINYC__
109 int __builtin_clz(unsigned int x) {
110  int i = 31;
111  while (!(x & (1 << i)) && i >= 0) i--;
112  return 31-i;
113 }
114 #endif
115 
116 void krk_tableAdjustCapacity(KrkTable * table, size_t capacity) {
117  if (capacity) {
118  /* Fast power-of-two calculation */
119  size_t powerOfTwoCapacity = __builtin_clz(1) - __builtin_clz(capacity);
120  if ((1UL << powerOfTwoCapacity) != capacity) powerOfTwoCapacity++;
121  capacity = (1UL << powerOfTwoCapacity);
122  }
123 
124  KrkTableEntry * entries = ALLOCATE(KrkTableEntry, capacity);
125  for (size_t i = 0; i < capacity; ++i) {
126  entries[i].key = KWARGS_VAL(0);
127  entries[i].value = KWARGS_VAL(0);
128  }
129 
130  table->count = 0;
131  for (size_t i = 0; i < table->capacity; ++i) {
132  KrkTableEntry * entry = &table->entries[i];
133  if (IS_KWARGS(entry->key)) continue;
134  KrkTableEntry * dest = krk_findEntry(entries, capacity, entry->key);
135  dest->key = entry->key;
136  dest->value = entry->value;
137  table->count++;
138  }
139 
140  FREE_ARRAY(KrkTableEntry, table->entries, table->capacity);
141  table->entries = entries;
142  table->capacity = capacity;
143 }
144 
145 int krk_tableSet(KrkTable * table, KrkValue key, KrkValue value) {
146  if (table->count + 1 > table->capacity * TABLE_MAX_LOAD) {
147  size_t capacity = GROW_CAPACITY(table->capacity);
148  krk_tableAdjustCapacity(table, capacity);
149  }
150  KrkTableEntry * entry = krk_findEntry(table->entries, table->capacity, key);
151  if (!entry) return 0;
152  int isNewKey = IS_KWARGS(entry->key);
153  if (isNewKey) table->count++;
154  entry->key = key;
155  entry->value = value;
156  return isNewKey;
157 }
158 
159 int krk_tableSetIfExists(KrkTable * table, KrkValue key, KrkValue value) {
160  if (table->count == 0) return 0;
161  KrkTableEntry * entry = krk_findEntry(table->entries, table->capacity, key);
162  if (!entry) return 0;
163  if (IS_KWARGS(entry->key)) return 0; /* Not found */
164  entry->key = key;
165  entry->value = value;
166  return 1;
167 }
168 
169 void krk_tableAddAll(KrkTable * from, KrkTable * to) {
170  for (size_t i = 0; i < from->capacity; ++i) {
171  KrkTableEntry * entry = &from->entries[i];
172  if (!IS_KWARGS(entry->key)) {
173  krk_tableSet(to, entry->key, entry->value);
174  }
175  }
176 }
177 
178 int krk_tableGet(KrkTable * table, KrkValue key, KrkValue * value) {
179  if (table->count == 0) return 0;
180  KrkTableEntry * entry = krk_findEntry(table->entries, table->capacity, key);
181  if (!entry || IS_KWARGS(entry->key)) {
182  return 0;
183  } else {
184  *value = entry->value;
185  return 1;
186  }
187 }
188 
189 int krk_tableGet_fast(KrkTable * table, KrkString * str, KrkValue * value) {
190  if (unlikely(table->count == 0)) return 0;
191  uint32_t index = str->obj.hash & (table->capacity-1);
192  KrkTableEntry * tombstone = NULL;
193  for (;;) {
194  KrkTableEntry * entry = &table->entries[index];
195  if (entry->key == KWARGS_VAL(0)) {
196  return 0;
197  } else if (entry->key == KWARGS_VAL(1)) {
198  if (tombstone == entry) return 0;
199  if (tombstone == NULL) tombstone = entry;
200  } else if (entry->key == OBJECT_VAL(str)) {
201  *value = entry->value;
202  return 1;
203  }
204  index = (index + 1) & (table->capacity-1);
205  }
206 }
207 
208 int krk_tableDelete(KrkTable * table, KrkValue key) {
209  if (table->count == 0) return 0;
210  KrkTableEntry * entry = krk_findEntry(table->entries, table->capacity, key);
211  if (!entry || IS_KWARGS(entry->key)) {
212  return 0;
213  }
214  table->count--;
215  entry->key = KWARGS_VAL(1);
216  entry->value = KWARGS_VAL(0);
217  return 1;
218 }
219 
221  if (table->count == 0) return 0;
222  KrkTableEntry * entry = krk_findEntryExact(table->entries, table->capacity, key);
223  if (!entry || IS_KWARGS(entry->key)) {
224  return 0;
225  }
226  table->count--;
227  entry->key = KWARGS_VAL(1);
228  entry->value = KWARGS_VAL(0);
229  return 1;
230 }
231 
232 KrkString * krk_tableFindString(KrkTable * table, const char * chars, size_t length, uint32_t hash) {
233  if (table->count == 0) return NULL;
234 
235  uint32_t index = hash & (table->capacity-1);
236  KrkTableEntry * tombstone = NULL;
237  for (;;) {
238  KrkTableEntry * entry = &table->entries[index];
239  if (entry->key == KWARGS_VAL(0)) {
240  return NULL;
241  } else if (entry->key == KWARGS_VAL(1)) {
242  if (tombstone == entry) return NULL;
243  if (tombstone == NULL) tombstone = entry;
244  } else if (AS_STRING(entry->key)->length == length &&
245  AS_OBJECT(entry->key)->hash == hash &&
246  memcmp(AS_STRING(entry->key)->chars, chars, length) == 0) {
247  return AS_STRING(entry->key);
248  }
249  index = (index + 1) & (table->capacity-1);
250  }
251 }
KrkValue krk_runtimeError(KrkClass *type, const char *fmt,...)
Produce and raise an exception with a formatted message.
Definition: exceptions.c:445
Top-level header with configuration macros.
Functions for dealing with garbage collection and memory allocation.
Struct definitions for core object types.
Type object.
Definition: object.h:189
KrkObj * _hash
__hash__ Called when an instance is a key in a dict or an entry in a set
Definition: object.h:219
uint32_t hash
Cached hash value for table keys.
Definition: object.h:44
Immutable sequence of Unicode codepoints.
Definition: object.h:93
KrkObj obj
Base.
Definition: object.h:94
One (key,value) pair in a table.
Definition: table.h:20
Simple hash table of arbitrary keys to values.
Definition: table.h:28
void krk_initTable(KrkTable *table)
Initialize a hash table.
Definition: table.c:14
int krk_tableGet(KrkTable *table, KrkValue key, KrkValue *value)
Obtain the value associated with a key in a table.
Definition: table.c:178
int krk_tableDeleteExact(KrkTable *table, KrkValue key)
Remove a key from a hash table, with identity lookup.
Definition: table.c:220
int krk_tableDelete(KrkTable *table, KrkValue key)
Remove a key from a hash table.
Definition: table.c:208
int krk_tableSet(KrkTable *table, KrkValue key, KrkValue value)
Assign a value to a key in a table.
Definition: table.c:145
void krk_tableAdjustCapacity(KrkTable *table, size_t capacity)
Preset the size of a table.
Definition: table.c:116
struct KrkString * krk_tableFindString(KrkTable *table, const char *chars, size_t length, uint32_t hash)
Find a character sequence in the string interning table.
Definition: table.c:232
void krk_tableAddAll(KrkTable *from, KrkTable *to)
Add all key-value pairs from 'from' into 'to'.
Definition: table.c:169
void krk_freeTable(KrkTable *table)
Release resources associated with a hash table.
Definition: table.c:20
int krk_tableGet_fast(KrkTable *table, struct KrkString *str, KrkValue *value)
Obtain the value associated with a string key in a table.
Definition: table.c:189
KrkTableEntry * krk_findEntry(KrkTableEntry *entries, size_t capacity, KrkValue key)
Internal table scan function.
Definition: table.c:66
int krk_tableSetIfExists(KrkTable *table, KrkValue key, KrkValue value)
Update the value of a table entry only if it is found.
Definition: table.c:159
KrkValue currentException
Definition: vm.h:173
Stack reference or primative value.
int krk_valuesSame(KrkValue a, KrkValue b)
Compare two values by identity.
Definition: value.c:151
KrkClass * krk_getType(KrkValue value)
Get the class representing a value.
Definition: vm.c:275
int krk_valuesSameOrEqual(KrkValue a, KrkValue b)
Compare two values by identity, then by equality.
int krk_hashValue(KrkValue value, uint32_t *hashOut)
Calculate the hash for a value.
Definition: table.c:25
Implementation of a generic hash table.
Convience header for providing atomic operations to threads.
Utilities for creating native bindings.
Definitions for primitive stack references.
Core API for the bytecode virtual machine.
#define vm
Convenience macro for namespacing.
Definition: vm.h:267
threadLocal KrkThreadState krk_currentThread
Thread-local VM state.
void krk_push(KrkValue value)
Push a stack value.
Definition: vm.c:157
KrkValue krk_callDirect(KrkObj *callable, int argCount)
Call a closure or native function with argCount arguments.
Definition: vm.c:771