/*** $Id: ltable.c,v 2.71 2012/05/23 15:37:09 roberto Exp $** Lua tables (hash)** See Copyright Notice in lua.h*/ /*** Implementation of tables (aka arrays, objects, or hash tables).** Tables keep its elements in two parts: an array part and a hash part.** Non-negative integer keys are all candidates to be kept in the array** part. The actual size of the array is the largest `n' such that at** least half the slots between 0 and n are in use.** Hash uses a mix of chained scatter table with Brent's variation.** A main invariant of these tables is that, if an element is not** in its main position (i.e. the `original' position that its hash gives** to it), then the colliding element is in its own main position.** Hence even when the load factor reaches 100%, performance remains good.*/ #include <string.h> #define ltable_c#define LUA_CORE #include "lua.h" #include "ldebug.h"#include "ldo.h"#include "lgc.h"#include "lmem.h"#include "lobject.h"#include "lstate.h"#include "lstring.h"#include "ltable.h"#include "lvm.h" /*** max size of array part is 2^MAXBITS*/#if LUAI_BITSINT >= 32#define MAXBITS 30#else#define MAXBITS (LUAI_BITSINT-2)#endif #define MAXASIZE (1 << MAXBITS) #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) #define hashstr(t,str) hashpow2(t, (str)->tsv.hash)#define hashboolean(t,p) hashpow2(t, p) /*** for some types, it is better to avoid modulus by power of 2, as** they tend to have many 2 factors.*/#define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) #define hashpointer(t,p) hashmod(t, IntPoint(p)) #define dummynode (&dummynode_) #define isdummy(n) ((n) == dummynode) static const Node dummynode_ = { {NILCONSTANT}, /* value */ {{NILCONSTANT, NULL}} /* key */}; /*** hash for lua_Numbers*/static Node *hashnum (const Table *t, lua_Number n) { int i; luai_hashnum(i, n); if (i < 0) { if (cast(unsigned int, i) == 0u - i) /* use unsigned to avoid overflows */ i = 0; /* handle INT_MIN */ i = -i; /* must be a positive value */ } return hashmod(t, i);} /*** returns the `main' position of an element in a table (that is, the index** of its hash value)*/static Node *mainposition (const Table *t, const TValue *key) { switch (ttype(key)) { case LUA_TNUMBER: return hashnum(t, nvalue(key)); case LUA_TLNGSTR: { TString *s = rawtsvalue(key); if (s->tsv.extra == 0) { /* no hash? */ s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash); s->tsv.extra = 1; /* now it has its hash */ } return hashstr(t, rawtsvalue(key)); } case LUA_TSHRSTR: return hashstr(t, rawtsvalue(key)); case LUA_TBOOLEAN: return hashboolean(t, bvalue(key)); case LUA_TLIGHTUSERDATA: return hashpointer(t, pvalue(key)); case LUA_TLCF: return hashpointer(t, fvalue(key)); default: return hashpointer(t, gcvalue(key)); }} /*** returns the index for `key' if `key' is an appropriate key to live in** the array part of the table, -1 otherwise.*/static int arrayindex (const TValue *key) { if (ttisnumber(key)) { lua_Number n = nvalue(key); int k; lua_number2int(k, n); if (luai_numeq(cast_num(k), n)) return k; } return -1; /* `key' did not match some condition */} /*** returns the index of a `key' for table traversals. First goes all** elements in the array part, then elements in the hash part. The** beginning of a traversal is signaled by -1.*/static int findindex (lua_State *L, Table *t, StkId key) { int i; if (ttisnil(key)) return -1; /* first iteration */ i = arrayindex(key); if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ return i-1; /* yes; that's the index (corrected to C) */ else { Node *n = mainposition(t, key); for (;;) { /* check whether `key' is somewhere in the chain */ /* key may be dead already, but it is ok to use it in `next' */ if (luaV_rawequalobj(gkey(n), key) || (ttisdeadkey(gkey(n)) && iscollectable(key) && deadvalue(gkey(n)) == gcvalue(key))) { i = cast_int(n - gnode(t, 0)); /* key index in hash table */ /* hash elements are numbered after array ones */ return i + t->sizearray; } else n = gnext(n); if (n == NULL) luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */ } }} int luaH_next (lua_State *L, Table *t, StkId key) { int i = findindex(L, t, key); /* find original element */ for (i++; i < t->sizearray; i++) { /* try first array part */ if (!ttisnil(&t->array[i])) { /* a non-nil value? */ setnvalue(key, cast_num(i+1)); setobj2s(L, key+1, &t->array[i]); return 1; } } for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ setobj2s(L, key, gkey(gnode(t, i))); setobj2s(L, key+1, gval(gnode(t, i))); return 1; } } return 0; /* no more elements */} /*** {=============================================================** Rehash** ==============================================================*/ static int computesizes (int nums[], int *narray) { int i; int twotoi; /* 2^i */ int a = 0; /* number of elements smaller than 2^i */ int na = 0; /* number of elements to go to array part */ int n = 0; /* optimal size for array part */ for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { if (nums[i] > 0) { a += nums[i]; if (a > twotoi/2) { /* more than half elements present? */ n = twotoi; /* optimal size (till now) */ na = a; /* all elements smaller than n will go to array part */ } } if (a == *narray) break; /* all elements already counted */ } *narray = n; lua_assert(*narray/2 <= na && na <= *narray); return na;} static int countint (const TValue *key, int *nums) { int k = arrayindex(key); if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ nums[luaO_ceillog2(k)]++; /* count as such */ return 1; } else return 0;} static int numusearray (const Table *t, int *nums) { int lg; int ttlg; /* 2^lg */ int ause = 0; /* summation of `nums' */ int i = 1; /* count to traverse all array keys */ for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ int lc = 0; /* counter */ int lim = ttlg; if (lim > t->sizearray) { lim = t->sizearray; /* adjust upper limit */ if (i > lim) break; /* no more elements to count */ } /* count elements in range (2^(lg-1), 2^lg] */ for (; i <= lim; i++) { if (!ttisnil(&t->array[i-1])) lc++; } nums[lg] += lc; ause += lc; } return ause;} static int numusehash (const Table *t, int *nums, int *pnasize) { int totaluse = 0; /* total number of elements */ int ause = 0; /* summation of `nums' */ int i = sizenode(t); while (i--) { Node *n = &t->node[i]; if (!ttisnil(gval(n))) { ause += countint(gkey(n), nums); totaluse++; } } *pnasize += ause; return totaluse;} static void setarrayvector (lua_State *L, Table *t, int size) { int i; luaM_reallocvector(L, t->array, t->sizearray, size, TValue); for (i=t->sizearray; i<size; i++) setnilvalue(&t->array[i]); t->sizearray = size;} static void setnodevector (lua_State *L, Table *t, int size) { int lsize; if (size == 0) { /* no elements to hash part? */ t->node = cast(Node *, dummynode); /* use common `dummynode' */ lsize = 0; } else { int i; lsize = luaO_ceillog2(size); if (lsize > MAXBITS) luaG_runerror(L, "table overflow"); size = twoto(lsize); t->node = luaM_newvector(L, size, Node); for (i=0; i<size; i++) { Node *n = gnode(t, i); gnext(n) = NULL; setnilvalue(gkey(n)); setnilvalue(gval(n)); } } t->lsizenode = cast_byte(lsize); t->lastfree = gnode(t, size); /* all positions are free */} void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { int i; int oldasize = t->sizearray; int oldhsize = t->lsizenode; Node *nold = t->node; /* save old hash ... */ if (nasize > oldasize) /* array part must grow? */ setarrayvector(L, t, nasize); /* create new hash part with appropriate size */ setnodevector(L, t, nhsize); if (nasize < oldasize) { /* array part must shrink? */ t->sizearray = nasize; /* re-insert elements from vanishing slice */ for (i=nasize; i<oldasize; i++) { if (!ttisnil(&t->array[i])) luaH_setint(L, t, i + 1, &t->array[i]); } /* shrink array */ luaM_reallocvector(L, t->array, oldasize, nasize, TValue); } /* re-insert elements from hash part */ for (i = twoto(oldhsize) - 1; i >= 0; i--) { Node *old = nold+i; if (!ttisnil(gval(old))) { /* doesn't need barrier/invalidate cache, as entry was already present in the table */ setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old)); } } if (!isdummy(nold)) luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old array */} void luaH_resizearray (lua_State *L, Table *t, int nasize) { int nsize = isdummy(t->node) ? 0 : sizenode(t); luaH_resize(L, t, nasize, nsize);} static void rehash (lua_State *L, Table *t, const TValue *ek) { int nasize, na; int nums[MAXBITS+1]; /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */ int i; int totaluse; for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ nasize = numusearray(t, nums); /* count keys in array part */ totaluse = nasize; /* all those keys are integer keys */ totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ /* count extra key */ nasize += countint(ek, nums); totaluse++; /* compute new size for array part */ na = computesizes(nums, &nasize); /* resize the table to new computed sizes */ luaH_resize(L, t, nasize, totaluse - na);} /*** }=============================================================*/ Table *luaH_new (lua_State *L) { Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h; t->metatable = NULL; t->flags = cast_byte(~0); t->array = NULL; t->sizearray = 0; setnodevector(L, t, 0); return t;} void luaH_free (lua_State *L, Table *t) { if (!isdummy(t->node)) luaM_freearray(L, t->node, cast(size_t, sizenode(t))); luaM_freearray(L, t->array, t->sizearray); luaM_free(L, t);} static Node *getfreepos (Table *t) { while (t->lastfree > t->node) { t->lastfree--; if (ttisnil(gkey(t->lastfree))) return t->lastfree; } return NULL; /* could not find a free place */} /*** inserts a new key into a hash table; first, check whether key's main** position is free. If not, check whether colliding node is in its main** position or not: if it is not, move colliding node to an empty place and** put new key in its main position; otherwise (colliding node is in its main** position), new key goes to an empty position.*/TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { Node *mp; if (ttisnil(key)) luaG_runerror(L, "table index is nil"); else if (ttisnumber(key) && luai_numisnan(L, nvalue(key))) luaG_runerror(L, "table index is NaN"); mp = mainposition(t, key); if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */ Node *othern; Node *n = getfreepos(t); /* get a free place */ if (n == NULL) { /* cannot find a free place? */ rehash(L, t, key); /* grow table */ /* whatever called 'newkey' take care of TM cache and GC barrier */ return luaH_set(L, t, key); /* insert key into grown table */ } lua_assert(!isdummy(n)); othern = mainposition(t, gkey(mp)); if (othern != mp) { /* is colliding node out of its main position? */ /* yes; move colliding node into free position */ while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ gnext(mp) = NULL; /* now `mp' is free */ setnilvalue(gval(mp)); } else { /* colliding node is in its own main position */ /* new node will go into free position */ gnext(n) = gnext(mp); /* chain new position */ gnext(mp) = n; mp = n; } } setobj2t(L, gkey(mp), key); luaC_barrierback(L, obj2gco(t), key); lua_assert(ttisnil(gval(mp))); return gval(mp);} /*** search function for integers*/const TValue *luaH_getint (Table *t, int key) { /* (1 <= key && key <= t->sizearray) */ if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) return &t->array[key-1]; else { lua_Number nk = cast_num(key); Node *n = hashnum(t, nk); do { /* check whether `key' is somewhere in the chain */ if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject; }} /*** search function for short strings*/const TValue *luaH_getstr (Table *t, TString *key) { Node *n = hashstr(t, key); lua_assert(key->tsv.tt == LUA_TSHRSTR); do { /* check whether `key' is somewhere in the chain */ if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)), key)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject;} /*** main search function*/const TValue *luaH_get (Table *t, const TValue *key) { switch (ttype(key)) { case LUA_TNIL: return luaO_nilobject; case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key)); case LUA_TNUMBER: { int k; lua_Number n = nvalue(key); lua_number2int(k, n); if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */ return luaH_getint(t, k); /* use specialized version */ /* else go through */ } default: { Node *n = mainposition(t, key); do { /* check whether `key' is somewhere in the chain */ if (luaV_rawequalobj(gkey(n), key)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject;Lines 1–500 of 588. Load more
/* ** $Id: ltable.c,v 2.71 2012/05/23 15:37:09 roberto Exp $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ /* ** Implementation of tables (aka arrays, objects, or hash tables). ** Tables keep its elements in two parts: an array part and a hash part. ** Non-negative integer keys are all candidates to be kept in the array ** part. The actual size of the array is the largest `n' such that at ** least half the slots between 0 and n are in use. ** Hash uses a mix of chained scatter table with Brent's variation. ** A main invariant of these tables is that, if an element is not ** in its main position (i.e. the `original' position that its hash gives ** to it), then the colliding element is in its own main position. ** Hence even when the load factor reaches 100%, performance remains good. */ #include <string.h> #define ltable_c #define LUA_CORE #include "lua.h" #include "ldebug.h" #include "ldo.h" #include "lgc.h" #include "lmem.h" #include "lobject.h" #include "lstate.h" #include "lstring.h" #include "ltable.h" #include "lvm.h" /* ** max size of array part is 2^MAXBITS */ #if LUAI_BITSINT >= 32 #define MAXBITS 30 #else #define MAXBITS (LUAI_BITSINT-2) #endif #define MAXASIZE (1 << MAXBITS) #define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t)))) #define hashstr(t,str) hashpow2(t, (str)->tsv.hash) #define hashboolean(t,p) hashpow2(t, p) /* ** for some types, it is better to avoid modulus by power of 2, as ** they tend to have many 2 factors. */ #define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1)))) #define hashpointer(t,p) hashmod(t, IntPoint(p)) #define dummynode (&dummynode_) #define isdummy(n) ((n) == dummynode) static const Node dummynode_ = { {NILCONSTANT}, /* value */ {{NILCONSTANT, NULL}} /* key */ }; /* ** hash for lua_Numbers */ static Node *hashnum (const Table *t, lua_Number n) { int i; luai_hashnum(i, n); if (i < 0) { if (cast(unsigned int, i) == 0u - i) /* use unsigned to avoid overflows */ i = 0; /* handle INT_MIN */ i = -i; /* must be a positive value */ } return hashmod(t, i); } /* ** returns the `main' position of an element in a table (that is, the index ** of its hash value) */ static Node *mainposition (const Table *t, const TValue *key) { switch (ttype(key)) { case LUA_TNUMBER: return hashnum(t, nvalue(key)); case LUA_TLNGSTR: { TString *s = rawtsvalue(key); if (s->tsv.extra == 0) { /* no hash? */ s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash); s->tsv.extra = 1; /* now it has its hash */ } return hashstr(t, rawtsvalue(key)); } case LUA_TSHRSTR: return hashstr(t, rawtsvalue(key)); case LUA_TBOOLEAN: return hashboolean(t, bvalue(key)); case LUA_TLIGHTUSERDATA: return hashpointer(t, pvalue(key)); case LUA_TLCF: return hashpointer(t, fvalue(key)); default: return hashpointer(t, gcvalue(key)); } } /* ** returns the index for `key' if `key' is an appropriate key to live in ** the array part of the table, -1 otherwise. */ static int arrayindex (const TValue *key) { if (ttisnumber(key)) { lua_Number n = nvalue(key); int k; lua_number2int(k, n); if (luai_numeq(cast_num(k), n)) return k; } return -1; /* `key' did not match some condition */ } /* ** returns the index of a `key' for table traversals. First goes all ** elements in the array part, then elements in the hash part. The ** beginning of a traversal is signaled by -1. */ static int findindex (lua_State *L, Table *t, StkId key) { int i; if (ttisnil(key)) return -1; /* first iteration */ i = arrayindex(key); if (0 < i && i <= t->sizearray) /* is `key' inside array part? */ return i-1; /* yes; that's the index (corrected to C) */ else { Node *n = mainposition(t, key); for (;;) { /* check whether `key' is somewhere in the chain */ /* key may be dead already, but it is ok to use it in `next' */ if (luaV_rawequalobj(gkey(n), key) || (ttisdeadkey(gkey(n)) && iscollectable(key) && deadvalue(gkey(n)) == gcvalue(key))) { i = cast_int(n - gnode(t, 0)); /* key index in hash table */ /* hash elements are numbered after array ones */ return i + t->sizearray; } else n = gnext(n); if (n == NULL) luaG_runerror(L, "invalid key to " LUA_QL("next")); /* key not found */ } } } int luaH_next (lua_State *L, Table *t, StkId key) { int i = findindex(L, t, key); /* find original element */ for (i++; i < t->sizearray; i++) { /* try first array part */ if (!ttisnil(&t->array[i])) { /* a non-nil value? */ setnvalue(key, cast_num(i+1)); setobj2s(L, key+1, &t->array[i]); return 1; } } for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */ if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */ setobj2s(L, key, gkey(gnode(t, i))); setobj2s(L, key+1, gval(gnode(t, i))); return 1; } } return 0; /* no more elements */ } /* ** {============================================================= ** Rehash ** ============================================================== */ static int computesizes (int nums[], int *narray) { int i; int twotoi; /* 2^i */ int a = 0; /* number of elements smaller than 2^i */ int na = 0; /* number of elements to go to array part */ int n = 0; /* optimal size for array part */ for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) { if (nums[i] > 0) { a += nums[i]; if (a > twotoi/2) { /* more than half elements present? */ n = twotoi; /* optimal size (till now) */ na = a; /* all elements smaller than n will go to array part */ } } if (a == *narray) break; /* all elements already counted */ } *narray = n; lua_assert(*narray/2 <= na && na <= *narray); return na; } static int countint (const TValue *key, int *nums) { int k = arrayindex(key); if (0 < k && k <= MAXASIZE) { /* is `key' an appropriate array index? */ nums[luaO_ceillog2(k)]++; /* count as such */ return 1; } else return 0; } static int numusearray (const Table *t, int *nums) { int lg; int ttlg; /* 2^lg */ int ause = 0; /* summation of `nums' */ int i = 1; /* count to traverse all array keys */ for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) { /* for each slice */ int lc = 0; /* counter */ int lim = ttlg; if (lim > t->sizearray) { lim = t->sizearray; /* adjust upper limit */ if (i > lim) break; /* no more elements to count */ } /* count elements in range (2^(lg-1), 2^lg] */ for (; i <= lim; i++) { if (!ttisnil(&t->array[i-1])) lc++; } nums[lg] += lc; ause += lc; } return ause; } static int numusehash (const Table *t, int *nums, int *pnasize) { int totaluse = 0; /* total number of elements */ int ause = 0; /* summation of `nums' */ int i = sizenode(t); while (i--) { Node *n = &t->node[i]; if (!ttisnil(gval(n))) { ause += countint(gkey(n), nums); totaluse++; } } *pnasize += ause; return totaluse; } static void setarrayvector (lua_State *L, Table *t, int size) { int i; luaM_reallocvector(L, t->array, t->sizearray, size, TValue); for (i=t->sizearray; i<size; i++) setnilvalue(&t->array[i]); t->sizearray = size; } static void setnodevector (lua_State *L, Table *t, int size) { int lsize; if (size == 0) { /* no elements to hash part? */ t->node = cast(Node *, dummynode); /* use common `dummynode' */ lsize = 0; } else { int i; lsize = luaO_ceillog2(size); if (lsize > MAXBITS) luaG_runerror(L, "table overflow"); size = twoto(lsize); t->node = luaM_newvector(L, size, Node); for (i=0; i<size; i++) { Node *n = gnode(t, i); gnext(n) = NULL; setnilvalue(gkey(n)); setnilvalue(gval(n)); } } t->lsizenode = cast_byte(lsize); t->lastfree = gnode(t, size); /* all positions are free */ } void luaH_resize (lua_State *L, Table *t, int nasize, int nhsize) { int i; int oldasize = t->sizearray; int oldhsize = t->lsizenode; Node *nold = t->node; /* save old hash ... */ if (nasize > oldasize) /* array part must grow? */ setarrayvector(L, t, nasize); /* create new hash part with appropriate size */ setnodevector(L, t, nhsize); if (nasize < oldasize) { /* array part must shrink? */ t->sizearray = nasize; /* re-insert elements from vanishing slice */ for (i=nasize; i<oldasize; i++) { if (!ttisnil(&t->array[i])) luaH_setint(L, t, i + 1, &t->array[i]); } /* shrink array */ luaM_reallocvector(L, t->array, oldasize, nasize, TValue); } /* re-insert elements from hash part */ for (i = twoto(oldhsize) - 1; i >= 0; i--) { Node *old = nold+i; if (!ttisnil(gval(old))) { /* doesn't need barrier/invalidate cache, as entry was already present in the table */ setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old)); } } if (!isdummy(nold)) luaM_freearray(L, nold, cast(size_t, twoto(oldhsize))); /* free old array */ } void luaH_resizearray (lua_State *L, Table *t, int nasize) { int nsize = isdummy(t->node) ? 0 : sizenode(t); luaH_resize(L, t, nasize, nsize); } static void rehash (lua_State *L, Table *t, const TValue *ek) { int nasize, na; int nums[MAXBITS+1]; /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */ int i; int totaluse; for (i=0; i<=MAXBITS; i++) nums[i] = 0; /* reset counts */ nasize = numusearray(t, nums); /* count keys in array part */ totaluse = nasize; /* all those keys are integer keys */ totaluse += numusehash(t, nums, &nasize); /* count keys in hash part */ /* count extra key */ nasize += countint(ek, nums); totaluse++; /* compute new size for array part */ na = computesizes(nums, &nasize); /* resize the table to new computed sizes */ luaH_resize(L, t, nasize, totaluse - na); } /* ** }============================================================= */ Table *luaH_new (lua_State *L) { Table *t = &luaC_newobj(L, LUA_TTABLE, sizeof(Table), NULL, 0)->h; t->metatable = NULL; t->flags = cast_byte(~0); t->array = NULL; t->sizearray = 0; setnodevector(L, t, 0); return t; } void luaH_free (lua_State *L, Table *t) { if (!isdummy(t->node)) luaM_freearray(L, t->node, cast(size_t, sizenode(t))); luaM_freearray(L, t->array, t->sizearray); luaM_free(L, t); } static Node *getfreepos (Table *t) { while (t->lastfree > t->node) { t->lastfree--; if (ttisnil(gkey(t->lastfree))) return t->lastfree; } return NULL; /* could not find a free place */ } /* ** inserts a new key into a hash table; first, check whether key's main ** position is free. If not, check whether colliding node is in its main ** position or not: if it is not, move colliding node to an empty place and ** put new key in its main position; otherwise (colliding node is in its main ** position), new key goes to an empty position. */ TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { Node *mp; if (ttisnil(key)) luaG_runerror(L, "table index is nil"); else if (ttisnumber(key) && luai_numisnan(L, nvalue(key))) luaG_runerror(L, "table index is NaN"); mp = mainposition(t, key); if (!ttisnil(gval(mp)) || isdummy(mp)) { /* main position is taken? */ Node *othern; Node *n = getfreepos(t); /* get a free place */ if (n == NULL) { /* cannot find a free place? */ rehash(L, t, key); /* grow table */ /* whatever called 'newkey' take care of TM cache and GC barrier */ return luaH_set(L, t, key); /* insert key into grown table */ } lua_assert(!isdummy(n)); othern = mainposition(t, gkey(mp)); if (othern != mp) { /* is colliding node out of its main position? */ /* yes; move colliding node into free position */ while (gnext(othern) != mp) othern = gnext(othern); /* find previous */ gnext(othern) = n; /* redo the chain with `n' in place of `mp' */ *n = *mp; /* copy colliding node into free pos. (mp->next also goes) */ gnext(mp) = NULL; /* now `mp' is free */ setnilvalue(gval(mp)); } else { /* colliding node is in its own main position */ /* new node will go into free position */ gnext(n) = gnext(mp); /* chain new position */ gnext(mp) = n; mp = n; } } setobj2t(L, gkey(mp), key); luaC_barrierback(L, obj2gco(t), key); lua_assert(ttisnil(gval(mp))); return gval(mp); } /* ** search function for integers */ const TValue *luaH_getint (Table *t, int key) { /* (1 <= key && key <= t->sizearray) */ if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray)) return &t->array[key-1]; else { lua_Number nk = cast_num(key); Node *n = hashnum(t, nk); do { /* check whether `key' is somewhere in the chain */ if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject; } } /* ** search function for short strings */ const TValue *luaH_getstr (Table *t, TString *key) { Node *n = hashstr(t, key); lua_assert(key->tsv.tt == LUA_TSHRSTR); do { /* check whether `key' is somewhere in the chain */ if (ttisshrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)), key)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject; } /* ** main search function */ const TValue *luaH_get (Table *t, const TValue *key) { switch (ttype(key)) { case LUA_TNIL: return luaO_nilobject; case LUA_TSHRSTR: return luaH_getstr(t, rawtsvalue(key)); case LUA_TNUMBER: { int k; lua_Number n = nvalue(key); lua_number2int(k, n); if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */ return luaH_getint(t, k); /* use specialized version */ /* else go through */ } default: { Node *n = mainposition(t, key); do { /* check whether `key' is somewhere in the chain */ if (luaV_rawequalobj(gkey(n), key)) return gval(n); /* that's it */ else n = gnext(n); } while (n); return luaO_nilobject;