summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>1996-05-06 11:30:27 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>1996-05-06 11:30:27 -0300
commit1936a9e53bac819e3707a47998c9b5fb705c2b7c (patch)
tree8f8f57190af254943b1a042ab3c6d62ad7949392
parent820ec63bdf9722d670f2ab8497f639f5fee5942a (diff)
downloadlua-1936a9e53bac819e3707a47998c9b5fb705c2b7c.tar.gz
lua-1936a9e53bac819e3707a47998c9b5fb705c2b7c.tar.bz2
lua-1936a9e53bac819e3707a47998c9b5fb705c2b7c.zip
tables may grow bigger than words.
Diffstat
-rw-r--r--hash.c49
-rw-r--r--hash.h12
2 files changed, 31 insertions, 30 deletions
diff --git a/hash.c b/hash.c
index 8e541a1e..58598c7c 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.28 1996/02/12 18:32:40 roberto Exp roberto $"; 6char *rcs_hash="$Id: hash.c,v 2.29 1996/02/14 18:25:04 roberto Exp roberto $";
7 7
8 8
9#include "mem.h" 9#include "mem.h"
@@ -29,14 +29,15 @@ static Hash *listhead = NULL;
29 29
30 30
31/* hash dimensions values */ 31/* hash dimensions values */
32static Word dimensions[] = 32static Long dimensions[] =
33 {3, 5, 7, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 33 {3L, 5L, 7L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
34 12853, 25717, 51437, 65521, 0}; /* 65521 == last prime < MAX_WORD */ 34 12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
35 1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};
35 36
36Word luaI_redimension (Word nhash) 37int luaI_redimension (int nhash)
37{ 38{
38 Word i; 39 int i;
39 for (i=0; dimensions[i]!=0; i++) 40 for (i=0; dimensions[i]<MAX_INT; i++)
40 { 41 {
41 if (dimensions[i] > nhash) 42 if (dimensions[i] > nhash)
42 return dimensions[i]; 43 return dimensions[i];
@@ -45,7 +46,7 @@ Word luaI_redimension (Word nhash)
45 return 0; /* to avoid warnings */ 46 return 0; /* to avoid warnings */
46} 47}
47 48
48static Word hashindex (Hash *t, Object *ref) /* hash function */ 49static int hashindex (Hash *t, Object *ref) /* hash function */
49{ 50{
50 switch (tag(ref)) 51 switch (tag(ref))
51 { 52 {
@@ -53,9 +54,9 @@ static Word hashindex (Hash *t, Object *ref) /* hash function */
53 lua_error ("unexpected type to index table"); 54 lua_error ("unexpected type to index table");
54 return -1; /* UNREACHEABLE */ 55 return -1; /* UNREACHEABLE */
55 case LUA_T_NUMBER: 56 case LUA_T_NUMBER:
56 return (((Word)nvalue(ref))%nhash(t)); 57 return (((int)nvalue(ref))%nhash(t));
57 case LUA_T_STRING: 58 case LUA_T_STRING:
58 return (Word)((tsvalue(ref)->hash)%nhash(t)); /* make it a valid index */ 59 return (int)((tsvalue(ref)->hash)%nhash(t)); /* make it a valid index */
59 case LUA_T_FUNCTION: 60 case LUA_T_FUNCTION:
60 return (((IntPoint)ref->value.tf)%nhash(t)); 61 return (((IntPoint)ref->value.tf)%nhash(t));
61 case LUA_T_CFUNCTION: 62 case LUA_T_CFUNCTION:
@@ -82,9 +83,9 @@ int lua_equalObj (Object *t1, Object *t2)
82 } 83 }
83} 84}
84 85
85static Word present (Hash *t, Object *ref) 86static int present (Hash *t, Object *ref)
86{ 87{
87 Word h = hashindex(t, ref); 88 int h = hashindex(t, ref);
88 while (tag(ref(node(t, h))) != LUA_T_NIL) 89 while (tag(ref(node(t, h))) != LUA_T_NIL)
89 { 90 {
90 if (lua_equalObj(ref, ref(node(t, h)))) 91 if (lua_equalObj(ref, ref(node(t, h))))
@@ -98,9 +99,9 @@ static Word present (Hash *t, Object *ref)
98/* 99/*
99** Alloc a vector node 100** Alloc a vector node
100*/ 101*/
101static Node *hashnodecreate (Word nhash) 102static Node *hashnodecreate (int nhash)
102{ 103{
103 Word i; 104 int i;
104 Node *v = newvector (nhash, Node); 105 Node *v = newvector (nhash, Node);
105 for (i=0; i<nhash; i++) 106 for (i=0; i<nhash; i++)
106 tag(ref(&v[i])) = LUA_T_NIL; 107 tag(ref(&v[i])) = LUA_T_NIL;
@@ -110,10 +111,10 @@ static Node *hashnodecreate (Word nhash)
110/* 111/*
111** Create a new hash. Return the hash pointer or NULL on error. 112** Create a new hash. Return the hash pointer or NULL on error.
112*/ 113*/
113static Hash *hashcreate (Word nhash) 114static Hash *hashcreate (int nhash)
114{ 115{
115 Hash *t = new(Hash); 116 Hash *t = new(Hash);
116 nhash = luaI_redimension((Word)((float)nhash/REHASH_LIMIT)); 117 nhash = luaI_redimension((int)((float)nhash/REHASH_LIMIT));
117 nodevector(t) = hashnodecreate(nhash); 118 nodevector(t) = hashnodecreate(nhash);
118 nhash(t) = nhash; 119 nhash(t) = nhash;
119 nuse(t) = 0; 120 nuse(t) = 0;
@@ -138,7 +139,7 @@ void lua_hashmark (Hash *h)
138{ 139{
139 if (markarray(h) == 0) 140 if (markarray(h) == 0)
140 { 141 {
141 Word i; 142 int i;
142 markarray(h) = 1; 143 markarray(h) = 1;
143 for (i=0; i<nhash(h); i++) 144 for (i=0; i<nhash(h); i++)
144 { 145 {
@@ -205,7 +206,7 @@ Long lua_hashcollector (void)
205** executes garbage collection if the number of arrays created 206** executes garbage collection if the number of arrays created
206** exceed a pre-defined range. 207** exceed a pre-defined range.
207*/ 208*/
208Hash *lua_createarray (Word nhash) 209Hash *lua_createarray (int nhash)
209{ 210{
210 Hash *array; 211 Hash *array;
211 lua_pack(); 212 lua_pack();
@@ -221,8 +222,8 @@ Hash *lua_createarray (Word nhash)
221*/ 222*/
222static void rehash (Hash *t) 223static void rehash (Hash *t)
223{ 224{
224 Word i; 225 int i;
225 Word nold = nhash(t); 226 int nold = nhash(t);
226 Node *vold = nodevector(t); 227 Node *vold = nodevector(t);
227 nhash(t) = luaI_redimension(nhash(t)); 228 nhash(t) = luaI_redimension(nhash(t));
228 nodevector(t) = hashnodecreate(nhash(t)); 229 nodevector(t) = hashnodecreate(nhash(t));
@@ -241,7 +242,7 @@ static void rehash (Hash *t)
241*/ 242*/
242Object *lua_hashget (Hash *t, Object *ref) 243Object *lua_hashget (Hash *t, Object *ref)
243{ 244{
244 Word h = present(t, ref); 245 int h = present(t, ref);
245 if (tag(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h)); 246 if (tag(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
246 else return NULL; 247 else return NULL;
247} 248}
@@ -253,7 +254,7 @@ Object *lua_hashget (Hash *t, Object *ref)
253*/ 254*/
254Object *lua_hashdefine (Hash *t, Object *ref) 255Object *lua_hashdefine (Hash *t, Object *ref)
255{ 256{
256 Word h; 257 int h;
257 Node *n; 258 Node *n;
258 h = present(t, ref); 259 h = present(t, ref);
259 n = node(t, h); 260 n = node(t, h);
@@ -279,7 +280,7 @@ Object *lua_hashdefine (Hash *t, Object *ref)
279** in the hash. 280** in the hash.
280** This function pushs the element value and its reference to the stack. 281** This function pushs the element value and its reference to the stack.
281*/ 282*/
282static void hashnext (Hash *t, Word i) 283static void hashnext (Hash *t, int i)
283{ 284{
284 if (i >= nhash(t)) 285 if (i >= nhash(t))
285 { 286 {
@@ -316,7 +317,7 @@ void lua_next (void)
316 } 317 }
317 else 318 else
318 { 319 {
319 Word h = present (t, luaI_Address(r)); 320 int h = present (t, luaI_Address(r));
320 hashnext(t, h+1); 321 hashnext(t, h+1);
321 } 322 }
322} 323}
diff --git a/hash.h b/hash.h
index e2bd2233..d0e26f90 100644
--- a/hash.h
+++ b/hash.h
@@ -1,7 +1,7 @@
1/* 1/*
2** hash.h 2** hash.h
3** hash manager for lua 3** hash manager for lua
4** $Id: hash.h,v 2.10 1996/02/12 18:32:40 roberto Exp roberto $ 4** $Id: hash.h,v 2.11 1996/03/08 12:04:04 roberto Exp roberto $
5*/ 5*/
6 6
7#ifndef hash_h 7#ifndef hash_h
@@ -19,16 +19,16 @@ typedef struct node
19typedef struct Hash 19typedef struct Hash
20{ 20{
21 struct Hash *next; 21 struct Hash *next;
22 char mark;
23 Word nhash;
24 Word nuse;
25 Node *node; 22 Node *node;
23 int nhash;
24 int nuse;
25 char mark;
26} Hash; 26} Hash;
27 27
28 28
29int lua_equalObj (Object *t1, Object *t2); 29int lua_equalObj (Object *t1, Object *t2);
30Word luaI_redimension (Word nhash); 30int luaI_redimension (int nhash);
31Hash *lua_createarray (Word nhash); 31Hash *lua_createarray (int nhash);
32void lua_hashmark (Hash *h); 32void lua_hashmark (Hash *h);
33Long lua_hashcollector (void); 33Long lua_hashcollector (void);
34Object *lua_hashget (Hash *t, Object *ref); 34Object *lua_hashget (Hash *t, Object *ref);
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-16 23:50:42 +0000