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