aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c36
1 files changed, 18 insertions, 18 deletions
diff --git a/ltable.c b/ltable.c
index 3d41f4db..71259630 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltable.c,v 2.96 2014/10/17 16:28:21 roberto Exp roberto $ 2** $Id: ltable.c,v 2.97 2014/10/24 11:42:06 roberto Exp roberto $
3** Lua tables (hash) 3** Lua tables (hash)
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -9,11 +9,11 @@
9** Implementation of tables (aka arrays, objects, or hash tables). 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. 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 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 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. 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. 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 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 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. 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. 18** Hence even when the load factor reaches 100%, performance remains good.
19*/ 19*/
@@ -111,7 +111,7 @@ static Node *hashfloat (const Table *t, lua_Number n) {
111 111
112 112
113/* 113/*
114** returns the `main' position of an element in a table (that is, the index 114** returns the 'main' position of an element in a table (that is, the index
115** of its hash value) 115** of its hash value)
116*/ 116*/
117static Node *mainposition (const Table *t, const TValue *key) { 117static Node *mainposition (const Table *t, const TValue *key) {
@@ -143,7 +143,7 @@ static Node *mainposition (const Table *t, const TValue *key) {
143 143
144 144
145/* 145/*
146** returns the index for `key' if `key' is an appropriate key to live in 146** returns the index for 'key' if 'key' is an appropriate key to live in
147** the array part of the table, 0 otherwise. 147** the array part of the table, 0 otherwise.
148*/ 148*/
149static unsigned int arrayindex (const TValue *key) { 149static unsigned int arrayindex (const TValue *key) {
@@ -152,12 +152,12 @@ static unsigned int arrayindex (const TValue *key) {
152 if (0 < k && (lua_Unsigned)k <= MAXASIZE) 152 if (0 < k && (lua_Unsigned)k <= MAXASIZE)
153 return cast(unsigned int, k); /* 'key' is an appropriate array index */ 153 return cast(unsigned int, k); /* 'key' is an appropriate array index */
154 } 154 }
155 return 0; /* `key' did not match some condition */ 155 return 0; /* 'key' did not match some condition */
156} 156}
157 157
158 158
159/* 159/*
160** returns the index of a `key' for table traversals. First goes all 160** returns the index of a 'key' for table traversals. First goes all
161** elements in the array part, then elements in the hash part. The 161** elements in the array part, then elements in the hash part. The
162** beginning of a traversal is signaled by 0. 162** beginning of a traversal is signaled by 0.
163*/ 163*/
@@ -165,13 +165,13 @@ static unsigned int findindex (lua_State *L, Table *t, StkId key) {
165 unsigned int i; 165 unsigned int i;
166 if (ttisnil(key)) return 0; /* first iteration */ 166 if (ttisnil(key)) return 0; /* first iteration */
167 i = arrayindex(key); 167 i = arrayindex(key);
168 if (i != 0 && i <= t->sizearray) /* is `key' inside array part? */ 168 if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */
169 return i; /* yes; that's the index */ 169 return i; /* yes; that's the index */
170 else { 170 else {
171 int nx; 171 int nx;
172 Node *n = mainposition(t, key); 172 Node *n = mainposition(t, key);
173 for (;;) { /* check whether `key' is somewhere in the chain */ 173 for (;;) { /* check whether 'key' is somewhere in the chain */
174 /* key may be dead already, but it is ok to use it in `next' */ 174 /* key may be dead already, but it is ok to use it in 'next' */
175 if (luaV_rawequalobj(gkey(n), key) || 175 if (luaV_rawequalobj(gkey(n), key) ||
176 (ttisdeadkey(gkey(n)) && iscollectable(key) && 176 (ttisdeadkey(gkey(n)) && iscollectable(key) &&
177 deadvalue(gkey(n)) == gcvalue(key))) { 177 deadvalue(gkey(n)) == gcvalue(key))) {
@@ -244,7 +244,7 @@ static unsigned int computesizes (unsigned int nums[], unsigned int *narray) {
244 244
245static int countint (const TValue *key, unsigned int *nums) { 245static int countint (const TValue *key, unsigned int *nums) {
246 unsigned int k = arrayindex(key); 246 unsigned int k = arrayindex(key);
247 if (k != 0) { /* is `key' an appropriate array index? */ 247 if (k != 0) { /* is 'key' an appropriate array index? */
248 nums[luaO_ceillog2(k)]++; /* count as such */ 248 nums[luaO_ceillog2(k)]++; /* count as such */
249 return 1; 249 return 1;
250 } 250 }
@@ -256,7 +256,7 @@ static int countint (const TValue *key, unsigned int *nums) {
256static unsigned int numusearray (const Table *t, unsigned int *nums) { 256static unsigned int numusearray (const Table *t, unsigned int *nums) {
257 int lg; 257 int lg;
258 unsigned int ttlg; /* 2^lg */ 258 unsigned int ttlg; /* 2^lg */
259 unsigned int ause = 0; /* summation of `nums' */ 259 unsigned int ause = 0; /* summation of 'nums' */
260 unsigned int i = 1; /* count to traverse all array keys */ 260 unsigned int i = 1; /* count to traverse all array keys */
261 /* traverse each slice */ 261 /* traverse each slice */
262 for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { 262 for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
@@ -308,7 +308,7 @@ static void setarrayvector (lua_State *L, Table *t, unsigned int size) {
308static void setnodevector (lua_State *L, Table *t, unsigned int size) { 308static void setnodevector (lua_State *L, Table *t, unsigned int size) {
309 int lsize; 309 int lsize;
310 if (size == 0) { /* no elements to hash part? */ 310 if (size == 0) { /* no elements to hash part? */
311 t->node = cast(Node *, dummynode); /* use common `dummynode' */ 311 t->node = cast(Node *, dummynode); /* use common 'dummynode' */
312 lsize = 0; 312 lsize = 0;
313 } 313 }
314 else { 314 else {
@@ -498,7 +498,7 @@ const TValue *luaH_getint (Table *t, lua_Integer key) {
498 return &t->array[key - 1]; 498 return &t->array[key - 1];
499 else { 499 else {
500 Node *n = hashint(t, key); 500 Node *n = hashint(t, key);
501 for (;;) { /* check whether `key' is somewhere in the chain */ 501 for (;;) { /* check whether 'key' is somewhere in the chain */
502 if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key) 502 if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
503 return gval(n); /* that's it */ 503 return gval(n); /* that's it */
504 else { 504 else {
@@ -518,7 +518,7 @@ const TValue *luaH_getint (Table *t, lua_Integer key) {
518const TValue *luaH_getstr (Table *t, TString *key) { 518const TValue *luaH_getstr (Table *t, TString *key) {
519 Node *n = hashstr(t, key); 519 Node *n = hashstr(t, key);
520 lua_assert(key->tt == LUA_TSHRSTR); 520 lua_assert(key->tt == LUA_TSHRSTR);
521 for (;;) { /* check whether `key' is somewhere in the chain */ 521 for (;;) { /* check whether 'key' is somewhere in the chain */
522 const TValue *k = gkey(n); 522 const TValue *k = gkey(n);
523 if (ttisshrstring(k) && eqshrstr(tsvalue(k), key)) 523 if (ttisshrstring(k) && eqshrstr(tsvalue(k), key))
524 return gval(n); /* that's it */ 524 return gval(n); /* that's it */
@@ -548,7 +548,7 @@ const TValue *luaH_get (Table *t, const TValue *key) {
548 } 548 }
549 default: { 549 default: {
550 Node *n = mainposition(t, key); 550 Node *n = mainposition(t, key);
551 for (;;) { /* check whether `key' is somewhere in the chain */ 551 for (;;) { /* check whether 'key' is somewhere in the chain */
552 if (luaV_rawequalobj(gkey(n), key)) 552 if (luaV_rawequalobj(gkey(n), key))
553 return gval(n); /* that's it */ 553 return gval(n); /* that's it */
554 else { 554 else {
@@ -592,7 +592,7 @@ void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {
592static int unbound_search (Table *t, unsigned int j) { 592static int unbound_search (Table *t, unsigned int j) {
593 unsigned int i = j; /* i is zero or a present index */ 593 unsigned int i = j; /* i is zero or a present index */
594 j++; 594 j++;
595 /* find `i' and `j' such that i is present and j is not */ 595 /* find 'i' and 'j' such that i is present and j is not */
596 while (!ttisnil(luaH_getint(t, j))) { 596 while (!ttisnil(luaH_getint(t, j))) {
597 i = j; 597 i = j;
598 if (j > cast(unsigned int, MAX_INT)/2) { /* overflow? */ 598 if (j > cast(unsigned int, MAX_INT)/2) { /* overflow? */
@@ -614,7 +614,7 @@ static int unbound_search (Table *t, unsigned int j) {
614 614
615 615
616/* 616/*
617** Try to find a boundary in table `t'. A `boundary' is an integer index 617** Try to find a boundary in table 't'. A 'boundary' is an integer index
618** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). 618** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
619*/ 619*/
620int luaH_getn (Table *t) { 620int luaH_getn (Table *t) {