diff options
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 | } |