aboutsummaryrefslogtreecommitdiff
path: root/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'hash.c')
-rw-r--r--hash.c62
1 files changed, 32 insertions, 30 deletions
diff --git a/hash.c b/hash.c
index c9b27b10..db87645b 100644
--- a/hash.c
+++ b/hash.c
@@ -3,7 +3,7 @@
3** hash manager for lua 3** hash manager for lua
4*/ 4*/
5 5
6char *rcs_hash="$Id: hash.c,v 2.20 1994/11/28 15:10:51 roberto Exp roberto $"; 6char *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 */
34static int dimensions[] = 34static 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 */
37static int redimension (int nhash) 37
38static 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
48static int hashindex (Hash *t, Object *ref) /* hash function */ 50static 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
80int lua_equalObj (Object *t1, Object *t2) 82Bool 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
95static int present (Hash *t, Object *ref) 97static 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*/
111static Node *hashnodecreate (int nhash) 113static 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*/
123static Hash *hashcreate (int nhash) 125static 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*/
186int lua_hashcollector (void) 188Word 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*/
218Hash *lua_createarray (int nhash) 220Hash *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*/
232static void rehash (Hash *t) 234static 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*/
252Object *lua_hashget (Hash *t, Object *ref) 254Object *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*/
264Object *lua_hashdefine (Hash *t, Object *ref) 266Object *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*/
292static void hashnext (Hash *t, int i) 294static 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}