diff options
| author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 1994-12-20 19:20:36 -0200 |
|---|---|---|
| committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 1994-12-20 19:20:36 -0200 |
| commit | 8cb8594a3bcfdc1447aebfcd0ac85db9af5ca490 (patch) | |
| tree | 13d09f704662cafa2597e77c92611b468e4741c9 /hash.c | |
| parent | fe8338335dfb4bf37e6b164cb55bfcc94ec6563d (diff) | |
| download | lua-8cb8594a3bcfdc1447aebfcd0ac85db9af5ca490.tar.gz lua-8cb8594a3bcfdc1447aebfcd0ac85db9af5ca490.tar.bz2 lua-8cb8594a3bcfdc1447aebfcd0ac85db9af5ca490.zip | |
better control of integer types and their limits
Diffstat (limited to 'hash.c')
| -rw-r--r-- | hash.c | 62 |
1 files changed, 32 insertions, 30 deletions
| @@ -3,7 +3,7 @@ | |||
| 3 | ** hash manager for lua | 3 | ** hash manager for lua |
| 4 | */ | 4 | */ |
| 5 | 5 | ||
| 6 | char *rcs_hash="$Id: hash.c,v 2.20 1994/11/28 15:10:51 roberto Exp roberto $"; | 6 | char *rcs_hash="$Id: hash.c,v 2.21 1994/12/16 15:55:04 roberto Exp roberto $"; |
| 7 | 7 | ||
| 8 | #include "mem.h" | 8 | #include "mem.h" |
| 9 | #include "opcode.h" | 9 | #include "opcode.h" |
| @@ -31,21 +31,23 @@ static Hash *listhead = NULL; | |||
| 31 | 31 | ||
| 32 | 32 | ||
| 33 | /* hash dimensions values */ | 33 | /* hash dimensions values */ |
| 34 | static int dimensions[] = | 34 | static Word dimensions[] = |
| 35 | {3, 5, 7, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, | 35 | {3, 5, 7, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, |
| 36 | 12853, 25717, 51437, 0}; | 36 | 12853, 25717, 51437, 65521, 0}; /* 65521 == last prime < MAX_WORD */ |
| 37 | static int redimension (int nhash) | 37 | |
| 38 | static Word redimension (Word nhash) | ||
| 38 | { | 39 | { |
| 39 | int i; | 40 | Word i; |
| 40 | for (i=0; dimensions[i]!=0; i++) | 41 | for (i=0; dimensions[i]!=0; i++) |
| 41 | { | 42 | { |
| 42 | if (dimensions[i] > nhash) | 43 | if (dimensions[i] > nhash) |
| 43 | return dimensions[i]; | 44 | return dimensions[i]; |
| 44 | } | 45 | } |
| 45 | return nhash*2+1; | 46 | lua_error("table overflow"); |
| 47 | return 0; /* to avoid warnings */ | ||
| 46 | } | 48 | } |
| 47 | 49 | ||
| 48 | static int hashindex (Hash *t, Object *ref) /* hash function */ | 50 | static Word hashindex (Hash *t, Object *ref) /* hash function */ |
| 49 | { | 51 | { |
| 50 | switch (tag(ref)) | 52 | switch (tag(ref)) |
| 51 | { | 53 | { |
| @@ -53,7 +55,7 @@ static int hashindex (Hash *t, Object *ref) /* hash function */ | |||
| 53 | lua_reportbug ("unexpected type to index table"); | 55 | lua_reportbug ("unexpected type to index table"); |
| 54 | return -1; /* UNREACHEABLE */ | 56 | return -1; /* UNREACHEABLE */ |
| 55 | case LUA_T_NUMBER: | 57 | case LUA_T_NUMBER: |
| 56 | return (((int)nvalue(ref))%nhash(t)); | 58 | return (((Word)nvalue(ref))%nhash(t)); |
| 57 | case LUA_T_STRING: | 59 | case LUA_T_STRING: |
| 58 | { | 60 | { |
| 59 | unsigned long h = tsvalue(ref)->hash; | 61 | unsigned long h = tsvalue(ref)->hash; |
| @@ -64,20 +66,20 @@ static int hashindex (Hash *t, Object *ref) /* hash function */ | |||
| 64 | h = ((h<<5)-h)^(unsigned char)*(name++); | 66 | h = ((h<<5)-h)^(unsigned char)*(name++); |
| 65 | tsvalue(ref)->hash = h; | 67 | tsvalue(ref)->hash = h; |
| 66 | } | 68 | } |
| 67 | return h%nhash(t); /* make it a valid index */ | 69 | return (Word)h%nhash(t); /* make it a valid index */ |
| 68 | } | 70 | } |
| 69 | case LUA_T_FUNCTION: | 71 | case LUA_T_FUNCTION: |
| 70 | return (((int)bvalue(ref))%nhash(t)); | 72 | return (((IntPoint)bvalue(ref))%nhash(t)); |
| 71 | case LUA_T_CFUNCTION: | 73 | case LUA_T_CFUNCTION: |
| 72 | return (((int)fvalue(ref))%nhash(t)); | 74 | return (((IntPoint)fvalue(ref))%nhash(t)); |
| 73 | case LUA_T_ARRAY: | 75 | case LUA_T_ARRAY: |
| 74 | return (((int)avalue(ref))%nhash(t)); | 76 | return (((IntPoint)avalue(ref))%nhash(t)); |
| 75 | default: /* user data */ | 77 | default: /* user data */ |
| 76 | return (((int)uvalue(ref))%nhash(t)); | 78 | return (((IntPoint)uvalue(ref))%nhash(t)); |
| 77 | } | 79 | } |
| 78 | } | 80 | } |
| 79 | 81 | ||
| 80 | int lua_equalObj (Object *t1, Object *t2) | 82 | Bool lua_equalObj (Object *t1, Object *t2) |
| 81 | { | 83 | { |
| 82 | if (tag(t1) != tag(t2)) return 0; | 84 | if (tag(t1) != tag(t2)) return 0; |
| 83 | switch (tag(t1)) | 85 | switch (tag(t1)) |
| @@ -92,9 +94,9 @@ int lua_equalObj (Object *t1, Object *t2) | |||
| 92 | } | 94 | } |
| 93 | } | 95 | } |
| 94 | 96 | ||
| 95 | static int present (Hash *t, Object *ref) | 97 | static Word present (Hash *t, Object *ref) |
| 96 | { | 98 | { |
| 97 | int h = hashindex(t, ref); | 99 | Word h = hashindex(t, ref); |
| 98 | while (tag(ref(node(t, h))) != LUA_T_NIL) | 100 | while (tag(ref(node(t, h))) != LUA_T_NIL) |
| 99 | { | 101 | { |
| 100 | if (lua_equalObj(ref, ref(node(t, h)))) | 102 | if (lua_equalObj(ref, ref(node(t, h)))) |
| @@ -108,9 +110,9 @@ static int present (Hash *t, Object *ref) | |||
| 108 | /* | 110 | /* |
| 109 | ** Alloc a vector node | 111 | ** Alloc a vector node |
| 110 | */ | 112 | */ |
| 111 | static Node *hashnodecreate (int nhash) | 113 | static Node *hashnodecreate (Word nhash) |
| 112 | { | 114 | { |
| 113 | int i; | 115 | Word i; |
| 114 | Node *v = newvector (nhash, Node); | 116 | Node *v = newvector (nhash, Node); |
| 115 | for (i=0; i<nhash; i++) | 117 | for (i=0; i<nhash; i++) |
| 116 | tag(ref(&v[i])) = LUA_T_NIL; | 118 | tag(ref(&v[i])) = LUA_T_NIL; |
| @@ -120,10 +122,10 @@ static Node *hashnodecreate (int nhash) | |||
| 120 | /* | 122 | /* |
| 121 | ** Create a new hash. Return the hash pointer or NULL on error. | 123 | ** Create a new hash. Return the hash pointer or NULL on error. |
| 122 | */ | 124 | */ |
| 123 | static Hash *hashcreate (int nhash) | 125 | static Hash *hashcreate (Word nhash) |
| 124 | { | 126 | { |
| 125 | Hash *t = new(Hash); | 127 | Hash *t = new(Hash); |
| 126 | nhash = redimension((int)((float)nhash/REHASH_LIMIT)); | 128 | nhash = redimension((Word)((float)nhash/REHASH_LIMIT)); |
| 127 | nodevector(t) = hashnodecreate(nhash); | 129 | nodevector(t) = hashnodecreate(nhash); |
| 128 | nhash(t) = nhash; | 130 | nhash(t) = nhash; |
| 129 | nuse(t) = 0; | 131 | nuse(t) = 0; |
| @@ -148,7 +150,7 @@ void lua_hashmark (Hash *h) | |||
| 148 | { | 150 | { |
| 149 | if (markarray(h) == 0) | 151 | if (markarray(h) == 0) |
| 150 | { | 152 | { |
| 151 | int i; | 153 | Word i; |
| 152 | markarray(h) = 1; | 154 | markarray(h) = 1; |
| 153 | for (i=0; i<nhash(h); i++) | 155 | for (i=0; i<nhash(h); i++) |
| 154 | { | 156 | { |
| @@ -183,10 +185,10 @@ static void call_fallbacks (void) | |||
| 183 | ** Garbage collection to arrays | 185 | ** Garbage collection to arrays |
| 184 | ** Delete all unmarked arrays. | 186 | ** Delete all unmarked arrays. |
| 185 | */ | 187 | */ |
| 186 | int lua_hashcollector (void) | 188 | Word lua_hashcollector (void) |
| 187 | { | 189 | { |
| 188 | Hash *curr_array = listhead, *prev = NULL; | 190 | Hash *curr_array = listhead, *prev = NULL; |
| 189 | int counter = 0; | 191 | Word counter = 0; |
| 190 | call_fallbacks(); | 192 | call_fallbacks(); |
| 191 | while (curr_array != NULL) | 193 | while (curr_array != NULL) |
| 192 | { | 194 | { |
| @@ -215,7 +217,7 @@ int lua_hashcollector (void) | |||
| 215 | ** executes garbage collection if the number of arrays created | 217 | ** executes garbage collection if the number of arrays created |
| 216 | ** exceed a pre-defined range. | 218 | ** exceed a pre-defined range. |
| 217 | */ | 219 | */ |
| 218 | Hash *lua_createarray (int nhash) | 220 | Hash *lua_createarray (Word nhash) |
| 219 | { | 221 | { |
| 220 | Hash *array; | 222 | Hash *array; |
| 221 | lua_pack(); | 223 | lua_pack(); |
| @@ -231,8 +233,8 @@ Hash *lua_createarray (int nhash) | |||
| 231 | */ | 233 | */ |
| 232 | static void rehash (Hash *t) | 234 | static void rehash (Hash *t) |
| 233 | { | 235 | { |
| 234 | int i; | 236 | Word i; |
| 235 | int nold = nhash(t); | 237 | Word nold = nhash(t); |
| 236 | Node *vold = nodevector(t); | 238 | Node *vold = nodevector(t); |
| 237 | nhash(t) = redimension(nhash(t)); | 239 | nhash(t) = redimension(nhash(t)); |
| 238 | nodevector(t) = hashnodecreate(nhash(t)); | 240 | nodevector(t) = hashnodecreate(nhash(t)); |
| @@ -251,7 +253,7 @@ static void rehash (Hash *t) | |||
| 251 | */ | 253 | */ |
| 252 | Object *lua_hashget (Hash *t, Object *ref) | 254 | Object *lua_hashget (Hash *t, Object *ref) |
| 253 | { | 255 | { |
| 254 | int h = present(t, ref); | 256 | Word h = present(t, ref); |
| 255 | if (tag(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h)); | 257 | if (tag(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h)); |
| 256 | else return NULL; | 258 | else return NULL; |
| 257 | } | 259 | } |
| @@ -263,7 +265,7 @@ Object *lua_hashget (Hash *t, Object *ref) | |||
| 263 | */ | 265 | */ |
| 264 | Object *lua_hashdefine (Hash *t, Object *ref) | 266 | Object *lua_hashdefine (Hash *t, Object *ref) |
| 265 | { | 267 | { |
| 266 | int h; | 268 | Word h; |
| 267 | Node *n; | 269 | Node *n; |
| 268 | h = present(t, ref); | 270 | h = present(t, ref); |
| 269 | n = node(t, h); | 271 | n = node(t, h); |
| @@ -289,7 +291,7 @@ Object *lua_hashdefine (Hash *t, Object *ref) | |||
| 289 | ** in the hash. | 291 | ** in the hash. |
| 290 | ** This function pushs the element value and its reference to the stack. | 292 | ** This function pushs the element value and its reference to the stack. |
| 291 | */ | 293 | */ |
| 292 | static void hashnext (Hash *t, int i) | 294 | static void hashnext (Hash *t, Word i) |
| 293 | { | 295 | { |
| 294 | if (i >= nhash(t)) | 296 | if (i >= nhash(t)) |
| 295 | { | 297 | { |
| @@ -326,7 +328,7 @@ void lua_next (void) | |||
| 326 | } | 328 | } |
| 327 | else | 329 | else |
| 328 | { | 330 | { |
| 329 | int h = present (t, luaI_Address(r)); | 331 | Word h = present (t, luaI_Address(r)); |
| 330 | hashnext(t, h+1); | 332 | hashnext(t, h+1); |
| 331 | } | 333 | } |
| 332 | } | 334 | } |
