rpm
4.5
|
00001 /* 00002 ** $Id: ltable.c,v 1.1 2004/03/16 21:58:30 niemeyer Exp $ 00003 ** Lua tables (hash) 00004 ** See Copyright Notice in lua.h 00005 */ 00006 00007 00008 /* 00009 ** Implementation of tables (aka arrays, objects, or hash tables). 00010 ** Tables keep its elements in two parts: an array part and a hash part. 00011 ** Non-negative integer keys are all candidates to be kept in the array 00012 ** part. The actual size of the array is the largest `n' such that at 00013 ** least half the slots between 0 and n are in use. 00014 ** Hash uses a mix of chained scatter table with Brent's variation. 00015 ** A main invariant of these tables is that, if an element is not 00016 ** in its main position (i.e. the `original' position that its hash gives 00017 ** to it), then the colliding element is in its own main position. 00018 ** In other words, there are collisions only when two elements have the 00019 ** same main position (i.e. the same hash values for that table size). 00020 ** Because of that, the load factor of these tables can be 100% without 00021 ** performance penalties. 00022 */ 00023 00024 #include <string.h> 00025 00026 #define ltable_c 00027 00028 #include "lua.h" 00029 00030 #include "ldebug.h" 00031 #include "ldo.h" 00032 #include "lgc.h" 00033 #include "lmem.h" 00034 #include "lobject.h" 00035 #include "lstate.h" 00036 #include "ltable.h" 00037 00038 00039 /* 00040 ** max size of array part is 2^MAXBITS 00041 */ 00042 #if BITS_INT > 26 00043 #define MAXBITS 24 00044 #else 00045 #define MAXBITS (BITS_INT-2) 00046 #endif 00047 00048 /* check whether `x' < 2^MAXBITS */ 00049 #define toobig(x) ((((x)-1) >> MAXBITS) != 0) 00050 00051 00052 /* function to convert a lua_Number to int (with any rounding method) */ 00053 #ifndef lua_number2int 00054 #define lua_number2int(i,n) ((i)=(int)(n)) 00055 #endif 00056 00057 00058 #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) 00059 00060 #define hashstr(t,str) hashpow2(t, (str)->tsv.hash) 00061 #define hashboolean(t,p) hashpow2(t, p) 00062 00063 00064 /* 00065 ** for some types, it is better to avoid modulus by power of 2, as 00066 ** they tend to have many 2 factors. 00067 */ 00068 #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) 00069 00070 00071 #define hashpointer(t,p) hashmod(t, IntPoint(p)) 00072 00073 00074 /* 00075 ** number of ints inside a lua_Number 00076 */ 00077 #define numints cast(int, sizeof(lua_Number)/sizeof(int)) 00078 00079 00080 /* 00081 ** hash for lua_Numbers 00082 */ 00083 static Node *hashnum (const Table *t, lua_Number n) 00084 /*@*/ 00085 { 00086 unsigned int a[numints]; 00087 int i; 00088 n += 1; /* normalize number (avoid -0) */ 00089 lua_assert(sizeof(a) <= sizeof(n)); 00090 memcpy(a, &n, sizeof(a)); 00091 for (i = 1; i < numints; i++) a[0] += a[i]; 00092 return hashmod(t, cast(lu_hash, a[0])); 00093 } 00094 00095 00096 00097 /* 00098 ** returns the `main' position of an element in a table (that is, the index 00099 ** of its hash value) 00100 */ 00101 Node *luaH_mainposition (const Table *t, const TObject *key) { 00102 switch (ttype(key)) { 00103 case LUA_TNUMBER: 00104 return hashnum(t, nvalue(key)); 00105 case LUA_TSTRING: 00106 return hashstr(t, tsvalue(key)); 00107 case LUA_TBOOLEAN: 00108 return hashboolean(t, bvalue(key)); 00109 case LUA_TLIGHTUSERDATA: 00110 return hashpointer(t, pvalue(key)); 00111 default: 00112 return hashpointer(t, gcvalue(key)); 00113 } 00114 } 00115 00116 00117 /* 00118 ** returns the index for `key' if `key' is an appropriate key to live in 00119 ** the array part of the table, -1 otherwise. 00120 */ 00121 static int arrayindex (const TObject *key) 00122 /*@*/ 00123 { 00124 if (ttisnumber(key)) { 00125 int k; 00126 lua_number2int(k, (nvalue(key))); 00127 if (cast(lua_Number, k) == nvalue(key) && k >= 1 && !toobig(k)) 00128 return k; 00129 } 00130 return -1; /* `key' did not match some condition */ 00131 } 00132 00133 00134 /* 00135 ** returns the index of a `key' for table traversals. First goes all 00136 ** elements in the array part, then elements in the hash part. The 00137 ** beginning and end of a traversal are signalled by -1. 00138 */ 00139 static int luaH_index (lua_State *L, Table *t, StkId key) 00140 /*@modifies L @*/ 00141 { 00142 int i; 00143 if (ttisnil(key)) return -1; /* first iteration */ 00144 i = arrayindex(key); 00145 if (0 <= i && i <= t->sizearray) { /* is `key' inside array part? */ 00146 return i-1; /* yes; that's the index (corrected to C) */ 00147 } 00148 else { 00149 const TObject *v = luaH_get(t, key); 00150 if (v == &luaO_nilobject) 00151 luaG_runerror(L, "invalid key for `next'"); 00152 i = cast(int, (cast(const lu_byte *, v) - 00153 cast(const lu_byte *, gval(gnode(t, 0)))) / sizeof(Node)); 00154 return i + t->sizearray; /* hash elements are numbered after array ones */ 00155 } 00156 } 00157 00158 00159 int luaH_next (lua_State *L, Table *t, StkId key) { 00160 int i = luaH_index(L, t, key); /* find original element */ 00161 for (i++; i < t->sizearray; i++) { /* try first array part */ 00162 if (!ttisnil(&t->array[i])) { /* a non-nil value? */ 00163 setnvalue(key, cast(lua_Number, i+1)); 00164 setobj2s(key+1, &t->array[i]); 00165 return 1; 00166 } 00167 } 00168 for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ 00169 if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ 00170 setobj2s(key, gkey(gnode(t, i))); 00171 setobj2s(key+1, gval(gnode(t, i))); 00172 return 1; 00173 } 00174 } 00175 return 0; /* no more elements */ 00176 } 00177 00178 00179 /* 00180 ** {============================================================= 00181 ** Rehash 00182 ** ============================================================== 00183 */ 00184 00185 00186 static void computesizes (int nums[], int ntotal, int *narray, int *nhash) 00187 /*@modifies *narray, *nhash @*/ 00188 { 00189 int i; 00190 int a = nums[0]; /* number of elements smaller than 2^i */ 00191 int na = a; /* number of elements to go to array part */ 00192 int n = (na == 0) ? -1 : 0; /* (log of) optimal size for array part */ 00193 for (i = 1; a < *narray && *narray >= twoto(i-1); i++) { 00194 if (nums[i] > 0) { 00195 a += nums[i]; 00196 if (a >= twoto(i-1)) { /* more than half elements in use? */ 00197 n = i; 00198 na = a; 00199 } 00200 } 00201 } 00202 lua_assert(na <= *narray && *narray <= ntotal); 00203 *nhash = ntotal - na; 00204 *narray = (n == -1) ? 0 : twoto(n); 00205 lua_assert(na <= *narray && na >= *narray/2); 00206 } 00207 00208 00209 static void numuse (const Table *t, int *narray, int *nhash) 00210 /*@modifies *narray, *nhash @*/ 00211 { 00212 int nums[MAXBITS+1]; 00213 int i, lg; 00214 int totaluse = 0; 00215 /* count elements in array part */ 00216 for (i=0, lg=0; lg<=MAXBITS; lg++) { /* for each slice [2^(lg-1) to 2^lg) */ 00217 int ttlg = twoto(lg); /* 2^lg */ 00218 if (ttlg > t->sizearray) { 00219 ttlg = t->sizearray; 00220 if (i >= ttlg) break; 00221 } 00222 nums[lg] = 0; 00223 for (; i<ttlg; i++) { 00224 if (!ttisnil(&t->array[i])) { 00225 nums[lg]++; 00226 totaluse++; 00227 } 00228 } 00229 } 00230 for (; lg<=MAXBITS; lg++) nums[lg] = 0; /* reset other counts */ 00231 *narray = totaluse; /* all previous uses were in array part */ 00232 /* count elements in hash part */ 00233 i = sizenode(t); 00234 while (i--) { 00235 Node *n = &t->node[i]; 00236 if (!ttisnil(gval(n))) { 00237 int k = arrayindex(gkey(n)); 00238 if (k >= 0) { /* is `key' an appropriate array index? */ 00239 nums[luaO_log2(k-1)+1]++; /* count as such */ 00240 (*narray)++; 00241 } 00242 totaluse++; 00243 } 00244 } 00245 computesizes(nums, totaluse, narray, nhash); 00246 } 00247 00248 00249 static void setarrayvector (lua_State *L, Table *t, int size) 00250 /*@modifies L, t @*/ 00251 { 00252 int i; 00253 luaM_reallocvector(L, t->array, t->sizearray, size, TObject); 00254 for (i=t->sizearray; i<size; i++) 00255 setnilvalue(&t->array[i]); 00256 t->sizearray = size; 00257 } 00258 00259 00260 static void setnodevector (lua_State *L, Table *t, int lsize) 00261 /*@modifies L, t @*/ 00262 { 00263 int i; 00264 int size = twoto(lsize); 00265 if (lsize > MAXBITS) 00266 luaG_runerror(L, "table overflow"); 00267 if (lsize == 0) { /* no elements to hash part? */ 00268 t->node = G(L)->dummynode; /* use common `dummynode' */ 00269 lua_assert(ttisnil(gkey(t->node))); /* assert invariants: */ 00270 lua_assert(ttisnil(gval(t->node))); 00271 lua_assert(t->node->next == NULL); /* (`dummynode' must be empty) */ 00272 } 00273 else { 00274 t->node = luaM_newvector(L, size, Node); 00275 for (i=0; i<size; i++) { 00276 t->node[i].next = NULL; 00277 setnilvalue(gkey(gnode(t, i))); 00278 setnilvalue(gval(gnode(t, i))); 00279 } 00280 } 00281 t->lsizenode = cast(lu_byte, lsize); 00282 t->firstfree = gnode(t, size-1); /* first free position to be used */ 00283 } 00284 00285 00286 static void resize (lua_State *L, Table *t, int nasize, int nhsize) 00287 /*@modifies L, t @*/ 00288 { 00289 int i; 00290 int oldasize = t->sizearray; 00291 int oldhsize = t->lsizenode; 00292 Node *nold; 00293 Node temp[1]; 00294 if (oldhsize) 00295 nold = t->node; /* save old hash ... */ 00296 else { /* old hash is `dummynode' */ 00297 lua_assert(t->node == G(L)->dummynode); 00298 temp[0] = t->node[0]; /* copy it to `temp' */ 00299 nold = temp; 00300 setnilvalue(gkey(G(L)->dummynode)); /* restate invariant */ 00301 setnilvalue(gval(G(L)->dummynode)); 00302 lua_assert(G(L)->dummynode->next == NULL); 00303 } 00304 if (nasize > oldasize) /* array part must grow? */ 00305 setarrayvector(L, t, nasize); 00306 /* create new hash part with appropriate size */ 00307 setnodevector(L, t, nhsize); 00308 /* re-insert elements */ 00309 if (nasize < oldasize) { /* array part must shrink? */ 00310 t->sizearray = nasize; 00311 /* re-insert elements from vanishing slice */ 00312 for (i=nasize; i<oldasize; i++) { 00313 if (!ttisnil(&t->array[i])) 00314 setobjt2t(luaH_setnum(L, t, i+1), &t->array[i]); 00315 } 00316 /* shrink array */ 00317 luaM_reallocvector(L, t->array, oldasize, nasize, TObject); 00318 } 00319 /* re-insert elements in hash part */ 00320 for (i = twoto(oldhsize) - 1; i >= 0; i--) { 00321 Node *old = nold+i; 00322 if (!ttisnil(gval(old))) 00323 setobjt2t(luaH_set(L, t, gkey(old)), gval(old)); 00324 } 00325 if (oldhsize) 00326 luaM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */ 00327 } 00328 00329 00330 static void rehash (lua_State *L, Table *t) 00331 /*@modifies L, t @*/ 00332 { 00333 int nasize, nhsize; 00334 numuse(t, &nasize, &nhsize); /* compute new sizes for array and hash parts */ 00335 resize(L, t, nasize, luaO_log2(nhsize)+1); 00336 } 00337 00338 00339 00340 /* 00341 ** }============================================================= 00342 */ 00343 00344 00345 Table *luaH_new (lua_State *L, int narray, int lnhash) { 00346 Table *t = luaM_new(L, Table); 00347 luaC_link(L, valtogco(t), LUA_TTABLE); 00348 t->metatable = hvalue(defaultmeta(L)); 00349 t->flags = cast(lu_byte, ~0); 00350 /* temporary values (kept only if some malloc fails) */ 00351 t->array = NULL; 00352 t->sizearray = 0; 00353 t->lsizenode = 0; 00354 t->node = NULL; 00355 setarrayvector(L, t, narray); 00356 setnodevector(L, t, lnhash); 00357 return t; 00358 } 00359 00360 00361 void luaH_free (lua_State *L, Table *t) { 00362 if (t->lsizenode) 00363 luaM_freearray(L, t->node, sizenode(t), Node); 00364 luaM_freearray(L, t->array, t->sizearray, TObject); 00365 luaM_freelem(L, t); 00366 } 00367 00368 00369 #if 0 00370 /* 00371 ** try to remove an element from a hash table; cannot move any element 00372 ** (because gc can call `remove' during a table traversal) 00373 */ 00374 void luaH_remove (Table *t, Node *e) { 00375 Node *mp = luaH_mainposition(t, gkey(e)); 00376 if (e != mp) { /* element not in its main position? */ 00377 while (mp->next != e) mp = mp->next; /* find previous */ 00378 mp->next = e->next; /* remove `e' from its list */ 00379 } 00380 else { 00381 if (e->next != NULL) ?? 00382 } 00383 lua_assert(ttisnil(gval(node))); 00384 setnilvalue(gkey(e)); /* clear node `e' */ 00385 e->next = NULL; 00386 } 00387 #endif 00388 00389 00390 /* 00391 ** inserts a new key into a hash table; first, check whether key's main 00392 ** position is free. If not, check whether colliding node is in its main 00393 ** position or not: if it is not, move colliding node to an empty place and 00394 ** put new key in its main position; otherwise (colliding node is in its main 00395 ** position), new key goes to an empty position. 00396 */ 00397 static TObject *newkey (lua_State *L, Table *t, const TObject *key) 00398 /*@modifies L, t @*/ 00399 { 00400 TObject *val; 00401 Node *mp = luaH_mainposition(t, key); 00402 if (!ttisnil(gval(mp))) { /* main position is not free? */ 00403 Node *othern = luaH_mainposition(t, gkey(mp)); /* `mp' of colliding node */ 00404 Node *n = t->firstfree; /* get a free place */ 00405 if (othern != mp) { /* is colliding node out of its main position? */ 00406 /* yes; move colliding node into free position */ 00407 while (othern->next != mp) othern = othern->next; /* find previous */ 00408 othern->next = n; /* redo the chain with `n' in place of `mp' */ 00409 *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ 00410 mp->next = NULL; /* now `mp' is free */ 00411 setnilvalue(gval(mp)); 00412 } 00413 else { /* colliding node is in its own main position */ 00414 /* new node will go into free position */ 00415 n->next = mp->next; /* chain new position */ 00416 mp->next = n; 00417 mp = n; 00418 } 00419 } 00420 setobj2t(gkey(mp), key); /* write barrier */ 00421 lua_assert(ttisnil(gval(mp))); 00422 for (;;) { /* correct `firstfree' */ 00423 if (ttisnil(gkey(t->firstfree))) 00424 return gval(mp); /* OK; table still has a free place */ 00425 else if (t->firstfree == t->node) break; /* cannot decrement from here */ 00426 else (t->firstfree)--; 00427 } 00428 /* no more free places; must create one */ 00429 setbvalue(gval(mp), 0); /* avoid new key being removed */ 00430 rehash(L, t); /* grow table */ 00431 val = cast(TObject *, luaH_get(t, key)); /* get new position */ 00432 lua_assert(ttisboolean(val)); 00433 setnilvalue(val); 00434 /*@-observertrans -dependenttrans @*/ 00435 return val; 00436 /*@=observertrans =dependenttrans @*/ 00437 } 00438 00439 00440 /* 00441 ** generic search function 00442 */ 00443 /*@observer@*/ 00444 static const TObject *luaH_getany (Table *t, const TObject *key) 00445 /*@*/ 00446 { 00447 if (ttisnil(key)) return &luaO_nilobject; 00448 else { 00449 Node *n = luaH_mainposition(t, key); 00450 do { /* check whether `key' is somewhere in the chain */ 00451 if (luaO_rawequalObj(gkey(n), key)) return gval(n); /* that's it */ 00452 else n = n->next; 00453 } while (n); 00454 return &luaO_nilobject; 00455 } 00456 } 00457 00458 00459 /* 00460 ** search function for integers 00461 */ 00462 const TObject *luaH_getnum (Table *t, int key) { 00463 if (1 <= key && key <= t->sizearray) 00464 return &t->array[key-1]; 00465 else { 00466 lua_Number nk = cast(lua_Number, key); 00467 Node *n = hashnum(t, nk); 00468 do { /* check whether `key' is somewhere in the chain */ 00469 if (ttisnumber(gkey(n)) && nvalue(gkey(n)) == nk) 00470 return gval(n); /* that's it */ 00471 else n = n->next; 00472 } while (n); 00473 return &luaO_nilobject; 00474 } 00475 } 00476 00477 00478 /* 00479 ** search function for strings 00480 */ 00481 const TObject *luaH_getstr (Table *t, TString *key) { 00482 Node *n = hashstr(t, key); 00483 do { /* check whether `key' is somewhere in the chain */ 00484 if (ttisstring(gkey(n)) && tsvalue(gkey(n)) == key) 00485 return gval(n); /* that's it */ 00486 else n = n->next; 00487 } while (n); 00488 return &luaO_nilobject; 00489 } 00490 00491 00492 /* 00493 ** main search function 00494 */ 00495 const TObject *luaH_get (Table *t, const TObject *key) { 00496 switch (ttype(key)) { 00497 case LUA_TSTRING: return luaH_getstr(t, tsvalue(key)); 00498 case LUA_TNUMBER: { 00499 int k; 00500 lua_number2int(k, (nvalue(key))); 00501 if (cast(lua_Number, k) == nvalue(key)) /* is an integer index? */ 00502 return luaH_getnum(t, k); /* use specialized version */ 00503 /* else go through */ 00504 } 00505 default: return luaH_getany(t, key); 00506 } 00507 } 00508 00509 00510 TObject *luaH_set (lua_State *L, Table *t, const TObject *key) { 00511 const TObject *p = luaH_get(t, key); 00512 t->flags = 0; 00513 if (p != &luaO_nilobject) 00514 /*@-observertrans -dependenttrans @*/ 00515 return cast(TObject *, p); 00516 /*@=observertrans =dependenttrans @*/ 00517 else { 00518 if (ttisnil(key)) luaG_runerror(L, "table index is nil"); 00519 else if (ttisnumber(key) && nvalue(key) != nvalue(key)) 00520 luaG_runerror(L, "table index is NaN"); 00521 return newkey(L, t, key); 00522 } 00523 } 00524 00525 00526 TObject *luaH_setnum (lua_State *L, Table *t, int key) { 00527 const TObject *p = luaH_getnum(t, key); 00528 if (p != &luaO_nilobject) 00529 /*@-observertrans -dependenttrans @*/ 00530 return cast(TObject *, p); 00531 /*@=observertrans =dependenttrans @*/ 00532 else { 00533 TObject k; 00534 setnvalue(&k, cast(lua_Number, key)); 00535 return newkey(L, t, &k); 00536 } 00537 } 00538