ba8b5c17 |
1 | /* |
2 | ** $Id: ltable.c,v 2.72 2012/09/11 19:37:16 roberto Exp $ |
3 | ** Lua tables (hash) |
4 | ** See Copyright Notice in lua.h |
5 | */ |
6 | |
7 | |
8 | /* |
9 | ** Implementation of tables (aka arrays, objects, or hash tables). |
10 | ** Tables keep its elements in two parts: an array part and a hash part. |
11 | ** Non-negative integer keys are all candidates to be kept in the array |
12 | ** part. The actual size of the array is the largest `n' such that at |
13 | ** least half the slots between 0 and n are in use. |
14 | ** Hash uses a mix of chained scatter table with Brent's variation. |
15 | ** A main invariant of these tables is that, if an element is not |
16 | ** in its main position (i.e. the `original' position that its hash gives |
17 | ** to it), then the colliding element is in its own main position. |
18 | ** Hence even when the load factor reaches 100%, performance remains good. |
19 | */ |
20 | |
21 | #include <string.h> |
22 | |
23 | #define ltable_c |
24 | #define LUA_CORE |
25 | |
26 | #include "lua.h" |
27 | |
28 | #include "ldebug.h" |
29 | #include "ldo.h" |
30 | #include "lgc.h" |
31 | #include "lmem.h" |
32 | #include "lobject.h" |
33 | #include "lstate.h" |
34 | #include "lstring.h" |
35 | #include "ltable.h" |
36 | #include "lvm.h" |
37 | |
38 | |
39 | /* |
40 | ** max size of array part is 2^MAXBITS |
41 | */ |
42 | #if LUAI_BITSINT >= 32 |
43 | #define MAXBITS 30 |
44 | #else |
45 | #define MAXBITS (LUAI_BITSINT-2) |
46 | #endif |
47 | |
48 | #define MAXASIZE (1 << MAXBITS) |
49 | |
50 | |
51 | #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) |
52 | |
53 | #define hashstr(t,str) hashpow2(t, (str)->tsv.hash) |
54 | #define hashboolean(t,p) hashpow2(t, p) |
55 | |
56 | |
57 | /* |
58 | ** for some types, it is better to avoid modulus by power of 2, as |
59 | ** they tend to have many 2 factors. |
60 | */ |
61 | #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) |
62 | |
63 | |
64 | #define hashpointer(t,p) hashmod(t, IntPoint(p)) |
65 | |
66 | |
67 | #define dummynode (&dummynode_) |
68 | |
69 | #define isdummy(n) ((n) == dummynode) |
70 | |
71 | static const Node dummynode_ = { |
72 | {NILCONSTANT}, /* value */ |
73 | {{NILCONSTANT, NULL}} /* key */ |
74 | }; |
75 | |
76 | |
77 | /* |
78 | ** hash for lua_Numbers |
79 | */ |
80 | static Node *hashnum (const Table *t, lua_Number n) { |
81 | int i; |
82 | luai_hashnum(i, n); |
83 | if (i < 0) { |
84 | if (cast(unsigned int, i) == 0u - i) /* use unsigned to avoid overflows */ |
85 | i = 0; /* handle INT_MIN */ |
86 | i = -i; /* must be a positive value */ |
87 | } |
88 | return hashmod(t, i); |
89 | } |
90 | |
91 | |
92 | |
93 | /* |
94 | ** returns the `main' position of an element in a table (that is, the index |
95 | ** of its hash value) |
96 | */ |
97 | static Node *mainposition (const Table *t, const TValue *key) { |
98 | switch (ttype(key)) { |
99 | case LUA_TNUMBER: |
100 | return hashnum(t, nvalue(key)); |
101 | case LUA_TLNGSTR: { |
102 | TString *s = rawtsvalue(key); |
103 | if (s->tsv.extra == 0) { /* no hash? */ |
104 | s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash); |
105 | s->tsv.extra = 1; /* now it has its hash */ |
106 | } |
107 | return hashstr(t, rawtsvalue(key)); |
108 | } |
109 | case LUA_TSHRSTR: |
110 | return hashstr(t, rawtsvalue(key)); |
111 | case LUA_TBOOLEAN: |
112 | return hashboolean(t, bvalue(key)); |
113 | case LUA_TLIGHTUSERDATA: |
114 | return hashpointer(t, pvalue(key)); |
115 | case LUA_TLCF: |
116 | return hashpointer(t, fvalue(key)); |
117 | default: |
118 | return hashpointer(t, gcvalue(key)); |
119 | } |
120 | } |
121 | |
122 | |
123 | /* |
124 | ** returns the index for `key' if `key' is an appropriate key to live in |
125 | ** the array part of the table, -1 otherwise. |
126 | */ |
127 | static int arrayindex (const TValue *key) { |
128 | if (ttisnumber(key)) { |
129 | lua_Number n = nvalue(key); |
130 | int k; |
131 | lua_number2int(k, n); |
132 | if (luai_numeq(cast_num(k), n)) |
133 | return k; |
134 | } |
135 | return -1; /* `key' did not match some condition */ |
136 | } |
137 | |
138 | |
139 | /* |
140 | ** returns the index of a `key' for table traversals. First goes all |
141 | ** elements in the array part, then elements in the hash part. The |
142 | ** beginning of a traversal is signaled by -1. |
143 | */ |
144 | static int findindex (lua_State *L, Table *t, StkId key) { |
145 | int i; |
146 | if (ttisnil(key)) return -1; /* first iteration */ |
147 | i = arrayindex(key); |
148 | if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ |
149 | return i-1; /* yes; that's the index (corrected to C) */ |
150 | else { |
151 | Node *n = mainposition(t, key); |
152 | for (;;) { /* check whether `key' is somewhere in the chain */ |
153 | /* key may be dead already, but it is ok to use it in `next' */ |
154 | if (luaV_rawequalobj(gkey(n), key) || |
155 | (ttisdeadkey(gkey(n)) && iscollectable(key) && |
156 | deadvalue(gkey(n)) == gcvalue(key))) { |
157 | i = cast_int(n - gnode(t, 0)); /* key index in hash table */ |
158 | /* hash elements are numbered after array ones */ |
159 | return i + t->sizearray; |
160 | } |
161 | else n = gnext(n); |
162 | if (n == NULL) |
163 | luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */ |
164 | } |
165 | } |
166 | } |
167 | |
168 | |
169 | int luaH_next (lua_State *L, Table *t, StkId key) { |
170 | int i = findindex(L, t, key); /* find original element */ |
171 | for (i++; i < t->sizearray; i++) { /* try first array part */ |
172 | if (!ttisnil(&t->array[i])) { /* a non-nil value? */ |
173 | setnvalue(key, cast_num(i+1)); |
174 | setobj2s(L, key+1, &t->array[i]); |
175 | return 1; |
176 | } |
177 | } |
178 | for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ |
179 | if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ |
180 | setobj2s(L, key, gkey(gnode(t, i))); |
181 | setobj2s(L, key+1, gval(gnode(t, i))); |
182 | return 1; |
183 | } |
184 | } |
185 | return 0; /* no more elements */ |
186 | } |
187 | |
188 | |
189 | /* |
190 | ** {============================================================= |
191 | ** Rehash |
192 | ** ============================================================== |
193 | */ |
194 | |
195 | |
196 | static int computesizes (int nums[], int *narray) { |
197 | int i; |
198 | int twotoi; /* 2^i */ |
199 | int a = 0; /* number of elements smaller than 2^i */ |
200 | int na = 0; /* number of elements to go to array part */ |
201 | int n = 0; /* optimal size for array part */ |
202 | for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { |
203 | if (nums[i] > 0) { |
204 | a += nums[i]; |
205 | if (a > twotoi/2) { /* more than half elements present? */ |
206 | n = twotoi; /* optimal size (till now) */ |
207 | na = a; /* all elements smaller than n will go to array part */ |
208 | } |
209 | } |
210 | if (a == *narray) break; /* all elements already counted */ |
211 | } |
212 | *narray = n; |
213 | lua_assert(*narray/2 <= na && na <= *narray); |
214 | return na; |
215 | } |
216 | |
217 | |
218 | static int countint (const TValue *key, int *nums) { |
219 | int k = arrayindex(key); |
220 | if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ |
221 | nums[luaO_ceillog2(k)]++; /* count as such */ |
222 | return 1; |
223 | } |
224 | else |
225 | return 0; |
226 | } |
227 | |
228 | |
229 | static int numusearray (const Table *t, int *nums) { |
230 | int lg; |
231 | int ttlg; /* 2^lg */ |
232 | int ause = 0; /* summation of `nums' */ |
233 | int i = 1; /* count to traverse all array keys */ |
234 | for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ |
235 | int lc = 0; /* counter */ |
236 | int lim = ttlg; |
237 | if (lim > t->sizearray) { |
238 | lim = t->sizearray; /* adjust upper limit */ |
239 | if (i > lim) |
240 | break; /* no more elements to count */ |
241 | } |
242 | /* count elements in range (2^(lg-1), 2^lg] */ |
243 | for (; i <= lim; i++) { |
244 | if (!ttisnil(&t->array[i-1])) |
245 | lc++; |
246 | } |
247 | nums[lg] += lc; |
248 | ause += lc; |
249 | } |
250 | return ause; |
251 | } |
252 | |
253 | |
254 | static int numusehash (const Table *t, int *nums, int *pnasize) { |
255 | int totaluse = 0; /* total number of elements */ |
256 | int ause = 0; /* summation of `nums' */ |
257 | int i = sizenode(t); |
258 | while (i--) { |
259 | Node *n = &t->node[i]; |
260 | if (!ttisnil(gval(n))) { |
261 | ause += countint(gkey(n), nums); |
262 | totaluse++; |
263 | } |
264 | } |
265 | *pnasize += ause; |
266 | return totaluse; |
267 | } |
268 | |
269 | |
270 | static void setarrayvector (lua_State *L, Table *t, int size) { |
271 | int i; |
272 | luaM_reallocvector(L, t->array, t->sizearray, size, TValue); |
273 | for (i=t->sizearray; i<size; i++) |
274 | setnilvalue(&t->array[i]); |
275 | t->sizearray = size; |
276 | } |
277 | |
278 | |
279 | static void setnodevector (lua_State *L, Table *t, int size) { |
280 | int lsize; |
281 | if (size == 0) { /* no elements to hash part? */ |
282 | t->node = cast(Node *, dummynode); /* use common `dummynode' */ |
283 | lsize = 0; |
284 | } |
285 | else { |
286 | int i; |
287 | lsize = luaO_ceillog2(size); |
288 | if (lsize > MAXBITS) |
289 | luaG_runerror(L, "table overflow"); |
290 | size = twoto(lsize); |
291 | t->node = luaM_newvector(L, size, Node); |
292 | for (i=0; i<size; i++) { |
293 | Node *n = gnode(t, i); |
294 | gnext(n) = NULL; |
295 | setnilvalue(gkey(n)); |
296 | setnilvalue(gval(n)); |
297 | } |
298 | } |
299 | t->lsizenode = cast_byte(lsize); |
300 | t->lastfree = gnode(t, size); /* all positions are free */ |
301 | } |
302 | |
303 | |
304 | void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { |
305 | int i; |
306 | int oldasize = t->sizearray; |
307 | int oldhsize = t->lsizenode; |
308 | Node *nold = t->node; /* save old hash ... */ |
309 | if (nasize > oldasize) /* array part must grow? */ |
310 | setarrayvector(L, t, nasize); |
311 | /* create new hash part with appropriate size */ |
312 | setnodevector(L, t, nhsize); |
313 | if (nasize < oldasize) { /* array part must shrink? */ |
314 | t->sizearray = nasize; |
315 | /* re-insert elements from vanishing slice */ |
316 | for (i=nasize; i<oldasize; i++) { |
317 | if (!ttisnil(&t->array[i])) |
318 | luaH_setint(L, t, i + 1, &t->array[i]); |
319 | } |
320 | /* shrink array */ |
321 | luaM_reallocvector(L, t->array, oldasize, nasize, TValue); |
322 | } |
323 | /* re-insert elements from hash part */ |
324 | for (i = twoto(oldhsize) - 1; i >= 0; i--) { |
325 | Node *old = nold+i; |
326 | if (!ttisnil(gval(old))) { |
327 | /* doesn't need barrier/invalidate cache, as entry was |
328 | already present in the table */ |
329 | setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old)); |
330 | } |
331 | } |
332 | if (!isdummy(nold)) |
333 | luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old array */ |
334 | } |
335 | |
336 | |
337 | void luaH_resizearray (lua_State *L, Table *t, int nasize) { |
338 | int nsize = isdummy(t->node) ? 0 : sizenode(t); |
339 | luaH_resize(L, t, nasize, nsize); |
340 | } |
341 | |
342 | |
343 | static void rehash (lua_State *L, Table *t, const TValue *ek) { |
344 | int nasize, na; |
345 | int nums[MAXBITS+1]; /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */ |
346 | int i; |
347 | int totaluse; |
348 | for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ |
349 | nasize = numusearray(t, nums); /* count keys in array part */ |
350 | totaluse = nasize; /* all those keys are integer keys */ |
351 | totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ |
352 | /* count extra key */ |
353 | nasize += countint(ek, nums); |
354 | totaluse++; |
355 | /* compute new size for array part */ |
356 | na = computesizes(nums, &nasize); |
357 | /* resize the table to new computed sizes */ |
358 | luaH_resize(L, t, nasize, totaluse - na); |
359 | } |
360 | |
361 | |
362 | |
363 | /* |
364 | ** }============================================================= |
365 | */ |
366 | |
367 | |
368 | Table *luaH_new (lua_State *L) { |
369 | Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h; |
370 | t->metatable = NULL; |
371 | t->flags = cast_byte(~0); |
372 | t->array = NULL; |
373 | t->sizearray = 0; |
374 | setnodevector(L, t, 0); |
375 | return t; |
376 | } |
377 | |
378 | |
379 | void luaH_free (lua_State *L, Table *t) { |
380 | if (!isdummy(t->node)) |
381 | luaM_freearray(L, t->node, cast(size_t, sizenode(t))); |
382 | luaM_freearray(L, t->array, t->sizearray); |
383 | luaM_free(L, t); |
384 | } |
385 | |
386 | |
387 | static Node *getfreepos (Table *t) { |
388 | while (t->lastfree > t->node) { |
389 | t->lastfree--; |
390 | if (ttisnil(gkey(t->lastfree))) |
391 | return t->lastfree; |
392 | } |
393 | return NULL; /* could not find a free place */ |
394 | } |
395 | |
396 | |
397 | |
398 | /* |
399 | ** inserts a new key into a hash table; first, check whether key's main |
400 | ** position is free. If not, check whether colliding node is in its main |
401 | ** position or not: if it is not, move colliding node to an empty place and |
402 | ** put new key in its main position; otherwise (colliding node is in its main |
403 | ** position), new key goes to an empty position. |
404 | */ |
405 | TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { |
406 | Node *mp; |
407 | if (ttisnil(key)) luaG_runerror(L, "table index is nil"); |
408 | else if (ttisnumber(key) && luai_numisnan(L, nvalue(key))) |
409 | luaG_runerror(L, "table index is NaN"); |
410 | mp = mainposition(t, key); |
411 | if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */ |
412 | Node *othern; |
413 | Node *n = getfreepos(t); /* get a free place */ |
414 | if (n == NULL) { /* cannot find a free place? */ |
415 | rehash(L, t, key); /* grow table */ |
416 | /* whatever called 'newkey' take care of TM cache and GC barrier */ |
417 | return luaH_set(L, t, key); /* insert key into grown table */ |
418 | } |
419 | lua_assert(!isdummy(n)); |
420 | othern = mainposition(t, gkey(mp)); |
421 | if (othern != mp) { /* is colliding node out of its main position? */ |
422 | /* yes; move colliding node into free position */ |
423 | while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ |
424 | gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ |
425 | *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ |
426 | gnext(mp) = NULL; /* now `mp' is free */ |
427 | setnilvalue(gval(mp)); |
428 | } |
429 | else { /* colliding node is in its own main position */ |
430 | /* new node will go into free position */ |
431 | gnext(n) = gnext(mp); /* chain new position */ |
432 | gnext(mp) = n; |
433 | mp = n; |
434 | } |
435 | } |
436 | setobj2t(L, gkey(mp), key); |
437 | luaC_barrierback(L, obj2gco(t), key); |
438 | lua_assert(ttisnil(gval(mp))); |
439 | return gval(mp); |
440 | } |
441 | |
442 | |
443 | /* |
444 | ** search function for integers |
445 | */ |
446 | const TValue *luaH_getint (Table *t, int key) { |
447 | /* (1 <= key && key <= t->sizearray) */ |
448 | if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) |
449 | return &t->array[key-1]; |
450 | else { |
451 | lua_Number nk = cast_num(key); |
452 | Node *n = hashnum(t, nk); |
453 | do { /* check whether `key' is somewhere in the chain */ |
454 | if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) |
455 | return gval(n); /* that's it */ |
456 | else n = gnext(n); |
457 | } while (n); |
458 | return luaO_nilobject; |
459 | } |
460 | } |
461 | |
462 | |
463 | /* |
464 | ** search function for short strings |
465 | */ |
466 | const TValue *luaH_getstr (Table *t, TString *key) { |
467 | Node *n = hashstr(t, key); |
468 | lua_assert(key->tsv.tt == LUA_TSHRSTR); |
469 | do { /* check whether `key' is somewhere in the chain */ |
470 | if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)), key)) |
471 | return gval(n); /* that's it */ |
472 | else n = gnext(n); |
473 | } while (n); |
474 | return luaO_nilobject; |
475 | } |
476 | |
477 | |
478 | /* |
479 | ** main search function |
480 | */ |
481 | const TValue *luaH_get (Table *t, const TValue *key) { |
482 | switch (ttype(key)) { |
483 | case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key)); |
484 | case LUA_TNIL: return luaO_nilobject; |
485 | case LUA_TNUMBER: { |
486 | int k; |
487 | lua_Number n = nvalue(key); |
488 | lua_number2int(k, n); |
489 | if (luai_numeq(cast_num(k), n)) /* index is int? */ |
490 | return luaH_getint(t, k); /* use specialized version */ |
491 | /* else go through */ |
492 | } |
493 | default: { |
494 | Node *n = mainposition(t, key); |
495 | do { /* check whether `key' is somewhere in the chain */ |
496 | if (luaV_rawequalobj(gkey(n), key)) |
497 | return gval(n); /* that's it */ |
498 | else n = gnext(n); |
499 | } while (n); |
500 | return luaO_nilobject; |
501 | } |
502 | } |
503 | } |
504 | |
505 | |
506 | /* |
507 | ** beware: when using this function you probably need to check a GC |
508 | ** barrier and invalidate the TM cache. |
509 | */ |
510 | TValue *luaH_set (lua_State *L, Table *t, const TValue *key) { |
511 | const TValue *p = luaH_get(t, key); |
512 | if (p != luaO_nilobject) |
513 | return cast(TValue *, p); |
514 | else return luaH_newkey(L, t, key); |
515 | } |
516 | |
517 | |
518 | void luaH_setint (lua_State *L, Table *t, int key, TValue *value) { |
519 | const TValue *p = luaH_getint(t, key); |
520 | TValue *cell; |
521 | if (p != luaO_nilobject) |
522 | cell = cast(TValue *, p); |
523 | else { |
524 | TValue k; |
525 | setnvalue(&k, cast_num(key)); |
526 | cell = luaH_newkey(L, t, &k); |
527 | } |
528 | setobj2t(L, cell, value); |
529 | } |
530 | |
531 | |
532 | static int unbound_search (Table *t, unsigned int j) { |
533 | unsigned int i = j; /* i is zero or a present index */ |
534 | j++; |
535 | /* find `i' and `j' such that i is present and j is not */ |
536 | while (!ttisnil(luaH_getint(t, j))) { |
537 | i = j; |
538 | j *= 2; |
539 | if (j > cast(unsigned int, MAX_INT)) { /* overflow? */ |
540 | /* table was built with bad purposes: resort to linear search */ |
541 | i = 1; |
542 | while (!ttisnil(luaH_getint(t, i))) i++; |
543 | return i - 1; |
544 | } |
545 | } |
546 | /* now do a binary search between them */ |
547 | while (j - i > 1) { |
548 | unsigned int m = (i+j)/2; |
549 | if (ttisnil(luaH_getint(t, m))) j = m; |
550 | else i = m; |
551 | } |
552 | return i; |
553 | } |
554 | |
555 | |
556 | /* |
557 | ** Try to find a boundary in table `t'. A `boundary' is an integer index |
558 | ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). |
559 | */ |
560 | int luaH_getn (Table *t) { |
561 | unsigned int j = t->sizearray; |
562 | if (j > 0 && ttisnil(&t->array[j - 1])) { |
563 | /* there is a boundary in the array part: (binary) search for it */ |
564 | unsigned int i = 0; |
565 | while (j - i > 1) { |
566 | unsigned int m = (i+j)/2; |
567 | if (ttisnil(&t->array[m - 1])) j = m; |
568 | else i = m; |
569 | } |
570 | return i; |
571 | } |
572 | /* else must find a boundary in hash part */ |
573 | else if (isdummy(t->node)) /* hash part is empty? */ |
574 | return j; /* that is easy... */ |
575 | else return unbound_search(t, j); |
576 | } |
577 | |
578 | |
579 | |
580 | #if defined(LUA_DEBUG) |
581 | |
582 | Node *luaH_mainposition (const Table *t, const TValue *key) { |
583 | return mainposition(t, key); |
584 | } |
585 | |
586 | int luaH_isdummy (Node *n) { return isdummy(n); } |
587 | |
588 | #endif |