xref: /illumos-gate/usr/src/uts/common/fs/zfs/lua/ltable.c (revision 46ac8fdf)
1 /*
2 ** $Id: ltable.c,v 2.72.1.1 2013/04/12 18:48:47 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 <sys/zfs_context.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 */
hashnum(const Table * t,lua_Number n)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 */
mainposition(const Table * t,const TValue * key)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 */
arrayindex(const TValue * key)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 */
findindex(lua_State * L,Table * t,StkId key)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 
luaH_next(lua_State * L,Table * t,StkId key)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 
computesizes(int nums[],int * narray)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 
countint(const TValue * key,int * nums)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 
numusearray(const Table * t,int * nums)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 
numusehash(const Table * t,int * nums,int * pnasize)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 
setarrayvector(lua_State * L,Table * t,int size)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 
setnodevector(lua_State * L,Table * t,int size)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 
luaH_resize(lua_State * L,Table * t,int nasize,int nhsize)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 
luaH_resizearray(lua_State * L,Table * t,int nasize)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 
rehash(lua_State * L,Table * t,const TValue * ek)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 
luaH_new(lua_State * L)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 
luaH_free(lua_State * L,Table * t)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 
getfreepos(Table * t)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 */
luaH_newkey(lua_State * L,Table * t,const TValue * key)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 */
luaH_getint(Table * t,int key)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 */
luaH_getstr(Table * t,TString * key)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 */
luaH_get(Table * t,const TValue * key)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     /* FALLTHROUGH */
494     default: {
495       Node *n = mainposition(t, key);
496       do {  /* check whether `key' is somewhere in the chain */
497         if (luaV_rawequalobj(gkey(n), key))
498           return gval(n);  /* that's it */
499         else n = gnext(n);
500       } while (n);
501       return luaO_nilobject;
502     }
503   }
504 }
505 
506 
507 /*
508 ** beware: when using this function you probably need to check a GC
509 ** barrier and invalidate the TM cache.
510 */
luaH_set(lua_State * L,Table * t,const TValue * key)511 TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
512   const TValue *p = luaH_get(t, key);
513   if (p != luaO_nilobject)
514     return cast(TValue *, p);
515   else return luaH_newkey(L, t, key);
516 }
517 
518 
luaH_setint(lua_State * L,Table * t,int key,TValue * value)519 void luaH_setint (lua_State *L, Table *t, int key, TValue *value) {
520   const TValue *p = luaH_getint(t, key);
521   TValue *cell;
522   if (p != luaO_nilobject)
523     cell = cast(TValue *, p);
524   else {
525     TValue k;
526     setnvalue(&k, cast_num(key));
527     cell = luaH_newkey(L, t, &k);
528   }
529   setobj2t(L, cell, value);
530 }
531 
532 
unbound_search(Table * t,unsigned int j)533 static int unbound_search (Table *t, unsigned int j) {
534   unsigned int i = j;  /* i is zero or a present index */
535   j++;
536   /* find `i' and `j' such that i is present and j is not */
537   while (!ttisnil(luaH_getint(t, j))) {
538     i = j;
539     j *= 2;
540     if (j > cast(unsigned int, MAX_INT)) {  /* overflow? */
541       /* table was built with bad purposes: resort to linear search */
542       i = 1;
543       while (!ttisnil(luaH_getint(t, i))) i++;
544       return i - 1;
545     }
546   }
547   /* now do a binary search between them */
548   while (j - i > 1) {
549     unsigned int m = (i+j)/2;
550     if (ttisnil(luaH_getint(t, m))) j = m;
551     else i = m;
552   }
553   return i;
554 }
555 
556 
557 /*
558 ** Try to find a boundary in table `t'. A `boundary' is an integer index
559 ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
560 */
luaH_getn(Table * t)561 int luaH_getn (Table *t) {
562   unsigned int j = t->sizearray;
563   if (j > 0 && ttisnil(&t->array[j - 1])) {
564     /* there is a boundary in the array part: (binary) search for it */
565     unsigned int i = 0;
566     while (j - i > 1) {
567       unsigned int m = (i+j)/2;
568       if (ttisnil(&t->array[m - 1])) j = m;
569       else i = m;
570     }
571     return i;
572   }
573   /* else must find a boundary in hash part */
574   else if (isdummy(t->node))  /* hash part is empty? */
575     return j;  /* that is easy... */
576   else return unbound_search(t, j);
577 }
578 
579 
580 
581 #if defined(LUA_DEBUG)
582 
luaH_mainposition(const Table * t,const TValue * key)583 Node *luaH_mainposition (const Table *t, const TValue *key) {
584   return mainposition(t, key);
585 }
586 
luaH_isdummy(Node * n)587 int luaH_isdummy (Node *n) { return isdummy(n); }
588 
589 #endif
590