diff options
Diffstat (limited to 'ltable.c')
| -rw-r--r-- | ltable.c | 51 |
1 files changed, 23 insertions, 28 deletions
| @@ -1,5 +1,5 @@ | |||
| 1 | /* | 1 | /* |
| 2 | ** $Id: ltable.c,v 1.44 2000/06/05 20:07:53 roberto Exp roberto $ | 2 | ** $Id: ltable.c,v 1.45 2000/06/05 20:15:33 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 | */ |
| @@ -193,12 +193,12 @@ static int numuse (const Hash *t) { | |||
| 193 | static void rehash (lua_State *L, Hash *t) { | 193 | static void rehash (lua_State *L, Hash *t) { |
| 194 | int oldsize = t->size; | 194 | int oldsize = t->size; |
| 195 | Node *nold = t->node; | 195 | Node *nold = t->node; |
| 196 | int newsize = numuse(t); | 196 | int nelems = numuse(t); |
| 197 | int i; | 197 | int i; |
| 198 | LUA_ASSERT(L, newsize<=oldsize, "wrong count"); | 198 | LUA_ASSERT(L, nelems<=oldsize, "wrong count"); |
| 199 | if (newsize >= oldsize-oldsize/4) /* using more than 3/4? */ | 199 | if (nelems >= oldsize-oldsize/4) /* using more than 3/4? */ |
| 200 | setnodevector(L, t, (lint32)oldsize*2); | 200 | setnodevector(L, t, (lint32)oldsize*2); |
| 201 | else if (newsize <= oldsize/4 && /* less than 1/4? */ | 201 | else if (nelems <= oldsize/4 && /* less than 1/4? */ |
| 202 | oldsize > MINPOWER2) | 202 | oldsize > MINPOWER2) |
| 203 | setnodevector(L, t, oldsize/2); | 203 | setnodevector(L, t, oldsize/2); |
| 204 | else | 204 | else |
| @@ -207,35 +207,28 @@ static void rehash (lua_State *L, Hash *t) { | |||
| 207 | for (i=0; i<oldsize; i++) { | 207 | for (i=0; i<oldsize; i++) { |
| 208 | Node *old = nold+i; | 208 | Node *old = nold+i; |
| 209 | if (ttype(&old->val) != TAG_NIL) | 209 | if (ttype(&old->val) != TAG_NIL) |
| 210 | luaH_set(L, t, &old->key, &old->val); | 210 | *luaH_set(L, t, &old->key) = old->val; |
| 211 | } | 211 | } |
| 212 | luaM_free(L, nold); /* free old array */ | 212 | luaM_free(L, nold); /* free old array */ |
| 213 | } | 213 | } |
| 214 | 214 | ||
| 215 | 215 | ||
| 216 | /* | 216 | /* |
| 217 | ** sets a pair key-value in a hash table; first, check whether key is | 217 | ** inserts a key into a hash table; first, check whether key is |
| 218 | ** already present; if not, check whether key's main position is free; | 218 | ** already present; if not, check whether key's main position is free; |
| 219 | ** if not, check whether colliding node is in its main position or not; | 219 | ** if not, check whether colliding node is in its main position or not; |
| 220 | ** if it is not, move colliding node to an empty place and put new pair | 220 | ** if it is not, move colliding node to an empty place and put new key |
| 221 | ** in its main position; otherwise (colliding node is in its main position), | 221 | ** in its main position; otherwise (colliding node is in its main position), |
| 222 | ** new pair goes to an empty position. | 222 | ** new key goes to an empty position. |
| 223 | ** Tricky point: the only place where an old element is moved is when | ||
| 224 | ** we move the colliding node to an empty place; nevertheless, its old | ||
| 225 | ** value is still in that position until we set the value for the new | ||
| 226 | ** pair; therefore, even when `val' points to an element of this table | ||
| 227 | ** (this happens when we use `luaH_move'), there is no problem. | ||
| 228 | */ | 223 | */ |
| 229 | void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val) { | 224 | TObject *luaH_set (lua_State *L, Hash *t, const TObject *key) { |
| 230 | Node *mp = luaH_mainposition(t, key); | 225 | Node *mp = luaH_mainposition(t, key); |
| 231 | Node *n = mp; | 226 | Node *n = mp; |
| 232 | if (!mp) | 227 | if (!mp) |
| 233 | lua_error(L, "unexpected type to index table"); | 228 | lua_error(L, "unexpected type to index table"); |
| 234 | do { /* check whether `key' is somewhere in the chain */ | 229 | do { /* check whether `key' is somewhere in the chain */ |
| 235 | if (luaO_equalObj(key, &n->key)) { | 230 | if (luaO_equalObj(key, &n->key)) |
| 236 | n->val = *val; /* update value */ | 231 | return &n->val; /* that's all */ |
| 237 | return; /* that's all */ | ||
| 238 | } | ||
| 239 | else n = n->next; | 232 | else n = n->next; |
| 240 | } while (n); | 233 | } while (n); |
| 241 | /* `key' not found; must insert it */ | 234 | /* `key' not found; must insert it */ |
| @@ -243,7 +236,7 @@ void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val) { | |||
| 243 | Node *othern; /* main position of colliding node */ | 236 | Node *othern; /* main position of colliding node */ |
| 244 | n = t->firstfree; /* get a free place */ | 237 | n = t->firstfree; /* get a free place */ |
| 245 | /* is colliding node out of its main position? (can only happens if | 238 | /* is colliding node out of its main position? (can only happens if |
| 246 | its position if after "firstfree") */ | 239 | its position is after "firstfree") */ |
| 247 | if (mp > n && (othern=luaH_mainposition(t, &mp->key)) != mp) { | 240 | if (mp > n && (othern=luaH_mainposition(t, &mp->key)) != mp) { |
| 248 | /* yes; move colliding node into free position */ | 241 | /* yes; move colliding node into free position */ |
| 249 | while (othern->next != mp) othern = othern->next; /* find previous */ | 242 | while (othern->next != mp) othern = othern->next; /* find previous */ |
| @@ -259,30 +252,32 @@ void luaH_set (lua_State *L, Hash *t, const TObject *key, const TObject *val) { | |||
| 259 | } | 252 | } |
| 260 | } | 253 | } |
| 261 | mp->key = *key; | 254 | mp->key = *key; |
| 262 | mp->val = *val; | 255 | for (;;) { /* correct `firstfree' */ |
| 263 | for (;;) { /* check free places */ | ||
| 264 | if (ttype(&t->firstfree->key) == TAG_NIL) | 256 | if (ttype(&t->firstfree->key) == TAG_NIL) |
| 265 | return; /* OK; table still has a free place */ | 257 | return &mp->val; /* OK; table still has a free place */ |
| 266 | else if (t->firstfree == t->node) break; /* cannot decrement from here */ | 258 | else if (t->firstfree == t->node) break; /* cannot decrement from here */ |
| 267 | else (t->firstfree)--; | 259 | else (t->firstfree)--; |
| 268 | } | 260 | } |
| 269 | rehash(L, t); /* no more free places */ | 261 | rehash(L, t); /* no more free places */ |
| 262 | return luaH_set(L, t, key); /* `rehash' invalidates this insertion */ | ||
| 270 | } | 263 | } |
| 271 | 264 | ||
| 272 | 265 | ||
| 273 | void luaH_setint (lua_State *L, Hash *t, int key, const TObject *val) { | 266 | TObject *luaH_setint (lua_State *L, Hash *t, int key) { |
| 274 | TObject index; | 267 | TObject index; |
| 275 | ttype(&index) = TAG_NUMBER; | 268 | ttype(&index) = TAG_NUMBER; |
| 276 | nvalue(&index) = key; | 269 | nvalue(&index) = key; |
| 277 | luaH_set(L, t, &index, val); | 270 | return luaH_set(L, t, &index); |
| 278 | } | 271 | } |
| 279 | 272 | ||
| 280 | 273 | ||
| 281 | void luaH_setstr (lua_State *L, Hash *t, TString *key, const TObject *val) { | 274 | void luaH_setstrnum (lua_State *L, Hash *t, TString *key, Number val) { |
| 282 | TObject index; | 275 | TObject *value, index; |
| 283 | ttype(&index) = TAG_STRING; | 276 | ttype(&index) = TAG_STRING; |
| 284 | tsvalue(&index) = key; | 277 | tsvalue(&index) = key; |
| 285 | luaH_set(L, t, &index, val); | 278 | value = luaH_set(L, t, &index); |
| 279 | ttype(value) = TAG_NUMBER; | ||
| 280 | nvalue(value) = val; | ||
| 286 | } | 281 | } |
| 287 | 282 | ||
| 288 | 283 | ||
