Fix some syntax quirks preventing the use of gnu-indent
[olsrd.git] / lib / tas / src / lua / ltable.c
1 /*
2 ** Lua tables (hash)
3 ** See Copyright Notice in lua.h
4 */
5
6
7 /*
8 ** Implementation of tables (aka arrays, objects, or hash tables).
9 ** Tables keep its elements in two parts: an array part and a hash part.
10 ** Non-negative integer keys are all candidates to be kept in the array
11 ** part. The actual size of the array is the largest `n' such that at
12 ** least half the slots between 0 and n are in use.
13 ** Hash uses a mix of chained scatter table with Brent's variation.
14 ** A main invariant of these tables is that, if an element is not
15 ** in its main position (i.e. the `original' position that its hash gives
16 ** to it), then the colliding element is in its own main position.
17 ** In other words, there are collisions only when two elements have the
18 ** same main position (i.e. the same hash values for that table size).
19 ** Because of that, the load factor of these tables can be 100% without
20 ** performance penalties.
21 */
22
23 #include <string.h>
24
25 #define ltable_c
26
27 #include "lua.h"
28
29 #include "ldebug.h"
30 #include "ldo.h"
31 #include "lgc.h"
32 #include "lmem.h"
33 #include "lobject.h"
34 #include "lstate.h"
35 #include "ltable.h"
36
37
38 /*
39 ** max size of array part is 2^MAXBITS
40 */
41 #if BITS_INT > 26
42 #define MAXBITS         24
43 #else
44 #define MAXBITS         (BITS_INT-2)
45 #endif
46
47 /* check whether `x' < 2^MAXBITS */
48 #define toobig(x)       ((((x)-1) >> MAXBITS) != 0)
49
50
51 /* function to convert a lua_Number to int (with any rounding method) */
52 #ifndef lua_number2int
53 #define lua_number2int(i,n)     ((i)=(int)(n))
54 #endif
55
56
57 #define hashpow2(t,n)      (gnode(t, lmod((n), sizenode(t))))
58   
59 #define hashstr(t,str)  hashpow2(t, (str)->tsv.hash)
60 #define hashboolean(t,p)        hashpow2(t, p)
61
62
63 /*
64 ** for some types, it is better to avoid modulus by power of 2, as
65 ** they tend to have many 2 factors.
66 */
67 #define hashmod(t,n)    (gnode(t, ((n) % ((sizenode(t)-1)|1))))
68
69
70 #define hashpointer(t,p)        hashmod(t, IntPoint(p))
71
72
73 /*
74 ** number of ints inside a lua_Number
75 */
76 #define numints         cast(int, sizeof(lua_Number)/sizeof(int))
77
78
79 /*
80 ** hash for lua_Numbers
81 */
82 static Node *hashnum (const Table *t, lua_Number n) {
83   unsigned int a[numints];
84   int i;
85   n += 1;  /* normalize number (avoid -0) */
86   lua_assert(sizeof(a) <= sizeof(n));
87   memcpy(a, &n, sizeof(a));
88   for (i = 1; i < numints; i++) a[0] += a[i];
89   return hashmod(t, cast(lu_hash, a[0]));
90 }
91
92
93
94 /*
95 ** returns the `main' position of an element in a table (that is, the index
96 ** of its hash value)
97 */
98 Node *luaH_mainposition (const Table *t, const TObject *key) {
99   switch (ttype(key)) {
100     case LUA_TNUMBER:
101       return hashnum(t, nvalue(key));
102     case LUA_TSTRING:
103       return hashstr(t, tsvalue(key));
104     case LUA_TBOOLEAN:
105       return hashboolean(t, bvalue(key));
106     case LUA_TLIGHTUSERDATA:
107       return hashpointer(t, pvalue(key));
108     default:
109       return hashpointer(t, gcvalue(key));
110   }
111 }
112
113
114 /*
115 ** returns the index for `key' if `key' is an appropriate key to live in
116 ** the array part of the table, -1 otherwise.
117 */
118 static int arrayindex (const TObject *key) {
119   if (ttisnumber(key)) {
120     int k;
121     lua_number2int(k, (nvalue(key)));
122     if (cast(lua_Number, k) == nvalue(key) && k >= 1 && !toobig(k))
123       return k;
124   }
125   return -1;  /* `key' did not match some condition */
126 }
127
128
129 /*
130 ** returns the index of a `key' for table traversals. First goes all
131 ** elements in the array part, then elements in the hash part. The
132 ** beginning and end of a traversal are signalled by -1.
133 */
134 static int luaH_index (lua_State *L, Table *t, StkId key) {
135   int i;
136   if (ttisnil(key)) return -1;  /* first iteration */
137   i = arrayindex(key);
138   if (0 <= i && i <= t->sizearray) {  /* is `key' inside array part? */
139     return i-1;  /* yes; that's the index (corrected to C) */
140   }
141   else {
142     const TObject *v = luaH_get(t, key);
143     if (v == &luaO_nilobject)
144       luaG_runerror(L, "invalid key for `next'");
145     i = cast(int, (cast(const lu_byte *, v) -
146                    cast(const lu_byte *, gval(gnode(t, 0)))) / sizeof(Node));
147     return i + t->sizearray;  /* hash elements are numbered after array ones */
148   }
149 }
150
151
152 int luaH_next (lua_State *L, Table *t, StkId key) {
153   int i = luaH_index(L, t, key);  /* find original element */
154   for (i++; i < t->sizearray; i++) {  /* try first array part */
155     if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
156       setnvalue(key, cast(lua_Number, i+1));
157       setobj2s(key+1, &t->array[i]);
158       return 1;
159     }
160   }
161   for (i -= t->sizearray; i < sizenode(t); i++) {  /* then hash part */
162     if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
163       setobj2s(key, gkey(gnode(t, i)));
164       setobj2s(key+1, gval(gnode(t, i)));
165       return 1;
166     }
167   }
168   return 0;  /* no more elements */
169 }
170
171
172 /*
173 ** {=============================================================
174 ** Rehash
175 ** ==============================================================
176 */
177
178
179 static void computesizes  (int nums[], int ntotal, int *narray, int *nhash) {
180   int i;
181   int a = nums[0];  /* number of elements smaller than 2^i */
182   int na = a;  /* number of elements to go to array part */
183   int n = (na == 0) ? -1 : 0;  /* (log of) optimal size for array part */
184   for (i = 1; a < *narray && *narray >= twoto(i-1); i++) {
185     if (nums[i] > 0) {
186       a += nums[i];
187       if (a >= twoto(i-1)) {  /* more than half elements in use? */
188         n = i;
189         na = a;
190       }
191     }
192   }
193   lua_assert(na <= *narray && *narray <= ntotal);
194   *nhash = ntotal - na;
195   *narray = (n == -1) ? 0 : twoto(n);
196   lua_assert(na <= *narray && na >= *narray/2);
197 }
198
199
200 static void numuse (const Table *t, int *narray, int *nhash) {
201   int nums[MAXBITS+1];
202   int i, lg;
203   int totaluse = 0;
204   /* count elements in array part */
205   for (i=0, lg=0; lg<=MAXBITS; lg++) {  /* for each slice [2^(lg-1) to 2^lg) */
206     int ttlg = twoto(lg);  /* 2^lg */
207     if (ttlg > t->sizearray) {
208       ttlg = t->sizearray;
209       if (i >= ttlg) break;
210     }
211     nums[lg] = 0;
212     for (; i<ttlg; i++) {
213       if (!ttisnil(&t->array[i])) {
214         nums[lg]++;
215         totaluse++;
216       }
217     }
218   }
219   for (; lg<=MAXBITS; lg++) nums[lg] = 0;  /* reset other counts */
220   *narray = totaluse;  /* all previous uses were in array part */
221   /* count elements in hash part */
222   i = sizenode(t);
223   while (i--) {
224     Node *n = &t->node[i];
225     if (!ttisnil(gval(n))) {
226       int k = arrayindex(gkey(n));
227       if (k >= 0) {  /* is `key' an appropriate array index? */
228         nums[luaO_log2(k-1)+1]++;  /* count as such */
229         (*narray)++;
230       }
231       totaluse++;
232     }
233   }
234   computesizes(nums, totaluse, narray, nhash);
235 }
236
237
238 static void setarrayvector (lua_State *L, Table *t, int size) {
239   int i;
240   luaM_reallocvector(L, t->array, t->sizearray, size, TObject);
241   for (i=t->sizearray; i<size; i++)
242      setnilvalue(&t->array[i]);
243   t->sizearray = size;
244 }
245
246
247 static void setnodevector (lua_State *L, Table *t, int lsize) {
248   int i;
249   int size = twoto(lsize);
250   if (lsize > MAXBITS)
251     luaG_runerror(L, "table overflow");
252   if (lsize == 0) {  /* no elements to hash part? */
253     t->node = G(L)->dummynode;  /* use common `dummynode' */
254     lua_assert(ttisnil(gkey(t->node)));  /* assert invariants: */
255     lua_assert(ttisnil(gval(t->node)));
256     lua_assert(t->node->next == NULL);  /* (`dummynode' must be empty) */
257   }
258   else {
259     t->node = luaM_newvector(L, size, Node);
260     for (i=0; i<size; i++) {
261       t->node[i].next = NULL;
262       setnilvalue(gkey(gnode(t, i)));
263       setnilvalue(gval(gnode(t, i)));
264     }
265   }
266   t->lsizenode = cast(lu_byte, lsize);
267   t->firstfree = gnode(t, size-1);  /* first free position to be used */
268 }
269
270
271 static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
272   int i;
273   int oldasize = t->sizearray;
274   int oldhsize = t->lsizenode;
275   Node *nold;
276   Node temp[1];
277   if (oldhsize)
278     nold = t->node;  /* save old hash ... */
279   else {  /* old hash is `dummynode' */
280     lua_assert(t->node == G(L)->dummynode);
281     temp[0] = t->node[0];  /* copy it to `temp' */
282     nold = temp;
283     setnilvalue(gkey(G(L)->dummynode));  /* restate invariant */
284     setnilvalue(gval(G(L)->dummynode));
285     lua_assert(G(L)->dummynode->next == NULL);
286   }
287   if (nasize > oldasize)  /* array part must grow? */
288     setarrayvector(L, t, nasize);
289   /* create new hash part with appropriate size */
290   setnodevector(L, t, nhsize);  
291   /* re-insert elements */
292   if (nasize < oldasize) {  /* array part must shrink? */
293     t->sizearray = nasize;
294     /* re-insert elements from vanishing slice */
295     for (i=nasize; i<oldasize; i++) {
296       if (!ttisnil(&t->array[i]))
297         setobjt2t(luaH_setnum(L, t, i+1), &t->array[i]);
298     }
299     /* shrink array */
300     luaM_reallocvector(L, t->array, oldasize, nasize, TObject);
301   }
302   /* re-insert elements in hash part */
303   for (i = twoto(oldhsize) - 1; i >= 0; i--) {
304     Node *old = nold+i;
305     if (!ttisnil(gval(old)))
306       setobjt2t(luaH_set(L, t, gkey(old)), gval(old));
307   }
308   if (oldhsize)
309     luaM_freearray(L, nold, twoto(oldhsize), Node);  /* free old array */
310 }
311
312
313 static void rehash (lua_State *L, Table *t) {
314   int nasize, nhsize;
315   numuse(t, &nasize, &nhsize);  /* compute new sizes for array and hash parts */
316   resize(L, t, nasize, luaO_log2(nhsize)+1);
317 }
318
319
320
321 /*
322 ** }=============================================================
323 */
324
325
326 Table *luaH_new (lua_State *L, int narray, int lnhash) {
327   Table *t = luaM_new(L, Table);
328   luaC_link(L, valtogco(t), LUA_TTABLE);
329   t->metatable = hvalue(defaultmeta(L));
330   t->flags = cast(lu_byte, ~0);
331   /* temporary values (kept only if some malloc fails) */
332   t->array = NULL;
333   t->sizearray = 0;
334   t->lsizenode = 0;
335   t->node = NULL;
336   setarrayvector(L, t, narray);
337   setnodevector(L, t, lnhash);
338   return t;
339 }
340
341
342 void luaH_free (lua_State *L, Table *t) {
343   if (t->lsizenode)
344     luaM_freearray(L, t->node, sizenode(t), Node);
345   luaM_freearray(L, t->array, t->sizearray, TObject);
346   luaM_freelem(L, t);
347 }
348
349
350 #if 0
351 /*
352 ** try to remove an element from a hash table; cannot move any element
353 ** (because gc can call `remove' during a table traversal)
354 */
355 void luaH_remove (Table *t, Node *e) {
356   Node *mp = luaH_mainposition(t, gkey(e));
357   if (e != mp) {  /* element not in its main position? */
358     while (mp->next != e) mp = mp->next;  /* find previous */
359     mp->next = e->next;  /* remove `e' from its list */
360   }
361   else {
362 #error The following line has an error in the original source.
363 //    if (e->next != NULL) ??
364   }
365   lua_assert(ttisnil(gval(node)));
366   setnilvalue(gkey(e));  /* clear node `e' */
367   e->next = NULL;
368 }
369 #endif
370
371
372 /*
373 ** inserts a new key into a hash table; first, check whether key's main 
374 ** position is free. If not, check whether colliding node is in its main 
375 ** position or not: if it is not, move colliding node to an empty place and 
376 ** put new key in its main position; otherwise (colliding node is in its main 
377 ** position), new key goes to an empty position. 
378 */
379 static TObject *newkey (lua_State *L, Table *t, const TObject *key) {
380   TObject *val;
381   Node *mp = luaH_mainposition(t, key);
382   if (!ttisnil(gval(mp))) {  /* main position is not free? */
383     Node *othern = luaH_mainposition(t, gkey(mp));  /* `mp' of colliding node */
384     Node *n = t->firstfree;  /* get a free place */
385     if (othern != mp) {  /* is colliding node out of its main position? */
386       /* yes; move colliding node into free position */
387       while (othern->next != mp) othern = othern->next;  /* find previous */
388       othern->next = n;  /* redo the chain with `n' in place of `mp' */
389       *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
390       mp->next = NULL;  /* now `mp' is free */
391       setnilvalue(gval(mp));
392     }
393     else {  /* colliding node is in its own main position */
394       /* new node will go into free position */
395       n->next = mp->next;  /* chain new position */
396       mp->next = n;
397       mp = n;
398     }
399   }
400   setobj2t(gkey(mp), key);  /* write barrier */
401   lua_assert(ttisnil(gval(mp)));
402   for (;;) {  /* correct `firstfree' */
403     if (ttisnil(gkey(t->firstfree)))
404       return gval(mp);  /* OK; table still has a free place */
405     else if (t->firstfree == t->node) break;  /* cannot decrement from here */
406     else (t->firstfree)--;
407   }
408   /* no more free places; must create one */
409   setbvalue(gval(mp), 0);  /* avoid new key being removed */
410   rehash(L, t);  /* grow table */
411   val = cast(TObject *, luaH_get(t, key));  /* get new position */
412   lua_assert(ttisboolean(val));
413   setnilvalue(val);
414   return val;
415 }
416
417
418 /*
419 ** generic search function
420 */
421 static const TObject *luaH_getany (Table *t, const TObject *key) {
422   if (ttisnil(key)) return &luaO_nilobject;
423   else {
424     Node *n = luaH_mainposition(t, key);
425     do {  /* check whether `key' is somewhere in the chain */
426       if (luaO_rawequalObj(gkey(n), key)) return gval(n);  /* that's it */
427       else n = n->next;
428     } while (n);
429     return &luaO_nilobject;
430   }
431 }
432
433
434 /*
435 ** search function for integers
436 */
437 const TObject *luaH_getnum (Table *t, int key) {
438   if (1 <= key && key <= t->sizearray)
439     return &t->array[key-1];
440   else {
441     lua_Number nk = cast(lua_Number, key);
442     Node *n = hashnum(t, nk);
443     do {  /* check whether `key' is somewhere in the chain */
444       if (ttisnumber(gkey(n)) && nvalue(gkey(n)) == nk)
445         return gval(n);  /* that's it */
446       else n = n->next;
447     } while (n);
448     return &luaO_nilobject;
449   }
450 }
451
452
453 /*
454 ** search function for strings
455 */
456 const TObject *luaH_getstr (Table *t, TString *key) {
457   Node *n = hashstr(t, key);
458   do {  /* check whether `key' is somewhere in the chain */
459     if (ttisstring(gkey(n)) && tsvalue(gkey(n)) == key)
460       return gval(n);  /* that's it */
461     else n = n->next;
462   } while (n);
463   return &luaO_nilobject;
464 }
465
466
467 /*
468 ** main search function
469 */
470 const TObject *luaH_get (Table *t, const TObject *key) {
471   switch (ttype(key)) {
472     case LUA_TSTRING: return luaH_getstr(t, tsvalue(key));
473     case LUA_TNUMBER: {
474       int k;
475       lua_number2int(k, (nvalue(key)));
476       if (cast(lua_Number, k) == nvalue(key))  /* is an integer index? */
477         return luaH_getnum(t, k);  /* use specialized version */
478       /* else go through */
479     }
480     default: return luaH_getany(t, key);
481   }
482 }
483
484
485 TObject *luaH_set (lua_State *L, Table *t, const TObject *key) {
486   const TObject *p = luaH_get(t, key);
487   t->flags = 0;
488   if (p != &luaO_nilobject)
489     return cast(TObject *, p);
490   else {
491     if (ttisnil(key)) luaG_runerror(L, "table index is nil");
492     else if (ttisnumber(key) && nvalue(key) != nvalue(key))
493       luaG_runerror(L, "table index is NaN");
494     return newkey(L, t, key);
495   }
496 }
497
498
499 TObject *luaH_setnum (lua_State *L, Table *t, int key) {
500   const TObject *p = luaH_getnum(t, key);
501   if (p != &luaO_nilobject)
502     return cast(TObject *, p);
503   else {
504     TObject k;
505     setnvalue(&k, cast(lua_Number, key));
506     return newkey(L, t, &k);
507   }
508 }
509