diff options
Diffstat (limited to 'ltable.c')
-rw-r--r-- | ltable.c | 36 |
1 files changed, 18 insertions, 18 deletions
@@ -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 | */ |
117 | static Node *mainposition (const Table *t, const TValue *key) { | 117 | static 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 | */ |
149 | static unsigned int arrayindex (const TValue *key) { | 149 | static 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 | ||
245 | static int countint (const TValue *key, unsigned int *nums) { | 245 | static 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) { | |||
256 | static unsigned int numusearray (const Table *t, unsigned int *nums) { | 256 | static 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) { | |||
308 | static void setnodevector (lua_State *L, Table *t, unsigned int size) { | 308 | static 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) { | |||
518 | const TValue *luaH_getstr (Table *t, TString *key) { | 518 | const 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) { | |||
592 | static int unbound_search (Table *t, unsigned int j) { | 592 | static 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 | */ |
620 | int luaH_getn (Table *t) { | 620 | int luaH_getn (Table *t) { |