aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--hash.c337
-rw-r--r--hash.h39
-rw-r--r--ltable.c218
-rw-r--r--ltable.h27
4 files changed, 245 insertions, 376 deletions
diff --git a/hash.c b/hash.c
deleted file mode 100644
index 64b9b313..00000000
--- a/hash.c
+++ /dev/null
@@ -1,337 +0,0 @@
1/*
2** hash.c
3** hash manager for lua
4*/
5
6char *rcs_hash="$Id: hash.c,v 2.43 1997/05/14 18:38:29 roberto Exp roberto $";
7
8
9#include "luamem.h"
10#include "opcode.h"
11#include "hash.h"
12#include "table.h"
13#include "lua.h"
14#include "auxlib.h"
15
16
17#define nhash(t) ((t)->nhash)
18#define nuse(t) ((t)->nuse)
19#define markarray(t) ((t)->mark)
20#define nodevector(t) ((t)->node)
21#define node(t,i) (&(t)->node[i])
22#define ref(n) (&(n)->ref)
23#define val(n) (&(n)->val)
24
25
26#define REHASH_LIMIT 0.70 /* avoid more than this % full */
27
28#define TagDefault LUA_T_ARRAY;
29
30
31static Hash *listhead = NULL;
32
33
34/* hash dimensions values */
35static Long dimensions[] =
36 {5L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
37 12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
38 1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};
39
40int luaI_redimension (int nhash)
41{
42 int i;
43 for (i=0; dimensions[i]<MAX_INT; i++)
44 {
45 if (dimensions[i] > nhash)
46 return dimensions[i];
47 }
48 lua_error("table overflow");
49 return 0; /* to avoid warnings */
50}
51
52
53int lua_equalObj (TObject *t1, TObject *t2)
54{
55 if (ttype(t1) != ttype(t2)) return 0;
56 switch (ttype(t1))
57 {
58 case LUA_T_NIL: return 1;
59 case LUA_T_NUMBER: return nvalue(t1) == nvalue(t2);
60 case LUA_T_STRING: case LUA_T_USERDATA: return svalue(t1) == svalue(t2);
61 case LUA_T_ARRAY: return avalue(t1) == avalue(t2);
62 case LUA_T_FUNCTION: return t1->value.tf == t2->value.tf;
63 case LUA_T_CFUNCTION: return fvalue(t1) == fvalue(t2);
64 default:
65 lua_error("internal error in `lua_equalObj'");
66 return 0; /* UNREACHEABLE */
67 }
68}
69
70
71static long int hashindex (TObject *ref)
72{
73 long int h;
74 switch (ttype(ref)) {
75 case LUA_T_NUMBER:
76 h = (long int)nvalue(ref); break;
77 case LUA_T_STRING: case LUA_T_USERDATA:
78 h = tsvalue(ref)->hash; break;
79 case LUA_T_FUNCTION:
80 h = (IntPoint)ref->value.tf; break;
81 case LUA_T_CFUNCTION:
82 h = (IntPoint)fvalue(ref); break;
83 case LUA_T_ARRAY:
84 h = (IntPoint)avalue(ref); break;
85 default:
86 lua_error ("unexpected type to index table");
87 h = 0; /* UNREACHEABLE */
88 }
89 if (h < 0) h = -h;
90 return h;
91}
92
93
94static int present (Hash *t, TObject *key)
95{
96 long int h = hashindex(key);
97 int tsize = nhash(t);
98 int h1 = h%tsize;
99 TObject *rf = ref(node(t, h1));
100 if (ttype(rf) != LUA_T_NIL && !lua_equalObj(key, rf)) {
101 int h2 = h%(tsize-2) + 1;
102 do {
103 h1 = (h1+h2)%tsize;
104 rf = ref(node(t, h1));
105 } while (ttype(rf) != LUA_T_NIL && !lua_equalObj(key, rf));
106 }
107 return h1;
108}
109
110
111/*
112** Alloc a vector node
113*/
114static Node *hashnodecreate (int nhash)
115{
116 int i;
117 Node *v = newvector (nhash, Node);
118 for (i=0; i<nhash; i++)
119 ttype(ref(&v[i])) = LUA_T_NIL;
120 return v;
121}
122
123/*
124** Create a new hash. Return the hash pointer or NULL on error.
125*/
126static Hash *hashcreate (int nhash)
127{
128 Hash *t = new(Hash);
129 nhash = luaI_redimension((int)((float)nhash/REHASH_LIMIT));
130 nodevector(t) = hashnodecreate(nhash);
131 nhash(t) = nhash;
132 nuse(t) = 0;
133 markarray(t) = 0;
134 t->htag = TagDefault;
135 return t;
136}
137
138/*
139** Delete a hash
140*/
141static void hashdelete (Hash *t)
142{
143 luaI_free (nodevector(t));
144 luaI_free(t);
145}
146
147
148/*
149** Mark a hash and check its elements
150*/
151void lua_hashmark (Hash *h)
152{
153 if (markarray(h) == 0)
154 {
155 int i;
156 markarray(h) = 1;
157 for (i=0; i<nhash(h); i++)
158 {
159 Node *n = node(h,i);
160 if (ttype(ref(n)) != LUA_T_NIL)
161 {
162 lua_markobject(&n->ref);
163 lua_markobject(&n->val);
164 }
165 }
166 }
167}
168
169
170void luaI_hashcallIM (Hash *l)
171{
172 TObject t;
173 ttype(&t) = LUA_T_ARRAY;
174 for (; l; l=l->next) {
175 avalue(&t) = l;
176 luaI_gcIM(&t);
177 }
178}
179
180
181void luaI_hashfree (Hash *frees)
182{
183 while (frees) {
184 Hash *next = frees->next;
185 hashdelete(frees);
186 frees = next;
187 }
188}
189
190
191Hash *luaI_hashcollector (long *acum)
192{
193 Hash *curr_array = listhead, *prev = NULL, *frees = NULL;
194 long counter = 0;
195 while (curr_array != NULL) {
196 Hash *next = curr_array->next;
197 if (markarray(curr_array) != 1) {
198 if (prev == NULL)
199 listhead = next;
200 else
201 prev->next = next;
202 curr_array->next = frees;
203 frees = curr_array;
204 ++counter;
205 }
206 else {
207 markarray(curr_array) = 0;
208 prev = curr_array;
209 }
210 curr_array = next;
211 }
212 *acum += counter;
213 return frees;
214}
215
216
217/*
218** Create a new array
219** This function inserts the new array in the array list. It also
220** executes garbage collection if the number of arrays created
221** exceed a pre-defined range.
222*/
223Hash *lua_createarray (int nhash)
224{
225 Hash *array;
226 lua_pack();
227 array = hashcreate(nhash);
228 array->next = listhead;
229 listhead = array;
230 return array;
231}
232
233
234/*
235** Rehash:
236** Check if table has deleted slots. It it has, it does not need to
237** grow, since rehash will reuse them.
238*/
239static int emptyslots (Hash *t)
240{
241 int i;
242 for (i=nhash(t)-1; i>=0; i--) {
243 Node *n = node(t, i);
244 if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) == LUA_T_NIL)
245 return 1;
246 }
247 return 0;
248}
249
250static void rehash (Hash *t)
251{
252 int nold = nhash(t);
253 Node *vold = nodevector(t);
254 int i;
255 if (!emptyslots(t))
256 nhash(t) = luaI_redimension(nhash(t));
257 nodevector(t) = hashnodecreate(nhash(t));
258 for (i=0; i<nold; i++) {
259 Node *n = vold+i;
260 if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL)
261 *node(t, present(t, ref(n))) = *n; /* copy old node to new hash */
262 }
263 luaI_free(vold);
264}
265
266/*
267** If the hash node is present, return its pointer, otherwise return
268** null.
269*/
270TObject *lua_hashget (Hash *t, TObject *ref)
271{
272 int h = present(t, ref);
273 if (ttype(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
274 else return NULL;
275}
276
277
278/*
279** If the hash node is present, return its pointer, otherwise create a new
280** node for the given reference and also return its pointer.
281*/
282TObject *lua_hashdefine (Hash *t, TObject *ref)
283{
284 Node *n = node(t, present(t, ref));
285 if (ttype(ref(n)) == LUA_T_NIL) {
286 nuse(t)++;
287 if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT) {
288 rehash(t);
289 n = node(t, present(t, ref));
290 }
291 *ref(n) = *ref;
292 ttype(val(n)) = LUA_T_NIL;
293 }
294 return (val(n));
295}
296
297
298/*
299** Internal function to manipulate arrays.
300** Given an array object and a reference value, return the next element
301** in the hash.
302** This function pushs the element value and its reference to the stack.
303*/
304static void hashnext (Hash *t, int i)
305{
306 Node *n;
307 int tsize = nhash(t);
308 if (i >= tsize)
309 return;
310 n = node(t, i);
311 while (ttype(ref(n)) == LUA_T_NIL || ttype(val(n)) == LUA_T_NIL) {
312 if (++i >= tsize)
313 return;
314 n = node(t, i);
315 }
316 luaI_pushobject(ref(node(t,i)));
317 luaI_pushobject(val(node(t,i)));
318}
319
320void lua_next (void)
321{
322 Hash *t;
323 lua_Object o = lua_getparam(1);
324 lua_Object r = lua_getparam(2);
325 luaL_arg_check(lua_istable(o), 1, "table expected");
326 luaL_arg_check(r != LUA_NOOBJECT, 2, "value expected");
327 t = avalue(luaI_Address(o));
328 if (lua_isnil(r))
329 hashnext(t, 0);
330 else {
331 int i = present(t, luaI_Address(r));
332 Node *n = node(t, i);
333 luaL_arg_check(ttype(ref(n))!=LUA_T_NIL && ttype(val(n))!=LUA_T_NIL,
334 2, "key not found");
335 hashnext(t, i+1);
336 }
337}
diff --git a/hash.h b/hash.h
deleted file mode 100644
index 4fbde55c..00000000
--- a/hash.h
+++ /dev/null
@@ -1,39 +0,0 @@
1/*
2** hash.h
3** hash manager for lua
4** $Id: hash.h,v 2.15 1997/03/31 14:02:58 roberto Exp roberto $
5*/
6
7#ifndef hash_h
8#define hash_h
9
10#include "types.h"
11#include "opcode.h"
12
13typedef struct node {
14 TObject ref;
15 TObject val;
16} Node;
17
18typedef struct Hash {
19 struct Hash *next;
20 Node *node;
21 int nhash;
22 int nuse;
23 int htag;
24 char mark;
25} Hash;
26
27
28int lua_equalObj (TObject *t1, TObject *t2);
29int luaI_redimension (int nhash);
30Hash *lua_createarray (int nhash);
31void lua_hashmark (Hash *h);
32Hash *luaI_hashcollector (long *count);
33void luaI_hashcallIM (Hash *l);
34void luaI_hashfree (Hash *frees);
35TObject *lua_hashget (Hash *t, TObject *ref);
36TObject *lua_hashdefine (Hash *t, TObject *ref);
37void lua_next (void);
38
39#endif
diff --git a/ltable.c b/ltable.c
new file mode 100644
index 00000000..6279d936
--- /dev/null
+++ b/ltable.c
@@ -0,0 +1,218 @@
1/*
2** $Id: ltable.c,v 1.1 1997/08/14 20:19:10 roberto Exp roberto $
3** Lua tables (hash)
4** See Copyright Notice in lua.h
5*/
6
7#include <stdlib.h>
8
9#include "lauxlib.h"
10#include "lmem.h"
11#include "lobject.h"
12#include "ltable.h"
13#include "lua.h"
14
15
16#define nuse(t) ((t)->nuse)
17#define nodevector(t) ((t)->node)
18#define val(n) (&(n)->val)
19
20
21#define REHASH_LIMIT 0.70 /* avoid more than this % full */
22
23#define TagDefault LUA_T_ARRAY;
24
25
26Hash *luaH_root = NULL;
27
28
29
30static long int hashindex (TObject *ref)
31{
32 long int h;
33 switch (ttype(ref)) {
34 case LUA_T_NUMBER:
35 h = (long int)nvalue(ref);
36 break;
37 case LUA_T_STRING: case LUA_T_USERDATA:
38 h = (IntPoint)tsvalue(ref);
39 break;
40 case LUA_T_FUNCTION:
41 h = (IntPoint)clvalue(ref);
42 break;
43 case LUA_T_CFUNCTION:
44 h = (IntPoint)fvalue(ref);
45 break;
46 case LUA_T_ARRAY:
47 h = (IntPoint)avalue(ref);
48 break;
49 default:
50 lua_error("unexpected type to index table");
51 h = 0; /* UNREACHEABLE */
52 }
53 return (h >= 0 ? h : -(h+1));
54}
55
56
57static int present (Hash *t, TObject *key)
58{
59 int tsize = nhash(t);
60 long int h = hashindex(key);
61 int h1 = h%tsize;
62 TObject *rf = ref(node(t, h1));
63 if (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf)) {
64 int h2 = h%(tsize-2) + 1;
65 do {
66 h1 = (h1+h2)%tsize;
67 rf = ref(node(t, h1));
68 } while (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf));
69 }
70 return h1;
71}
72
73
74/*
75** Alloc a vector node
76*/
77static Node *hashnodecreate (int nhash)
78{
79 int i;
80 Node *v = luaM_newvector (nhash, Node);
81 for (i=0; i<nhash; i++)
82 ttype(ref(&v[i])) = LUA_T_NIL;
83 return v;
84}
85
86/*
87** Delete a hash
88*/
89static void hashdelete (Hash *t)
90{
91 luaM_free (nodevector(t));
92 luaM_free(t);
93}
94
95
96void luaH_free (Hash *frees)
97{
98 while (frees) {
99 Hash *next = (Hash *)frees->head.next;
100 hashdelete(frees);
101 frees = next;
102 }
103}
104
105
106static void inserttable (Hash *table)
107{
108 ++luaO_nentities;
109 table->head.next = (GCnode *)luaH_root;
110 luaH_root = table;
111 table->head.marked = 0;
112}
113
114Hash *luaH_new (int nhash)
115{
116 Hash *t = luaM_new(Hash);
117 nhash = luaO_redimension((int)((float)nhash/REHASH_LIMIT));
118 nodevector(t) = hashnodecreate(nhash);
119 nhash(t) = nhash;
120 nuse(t) = 0;
121 t->htag = TagDefault;
122 inserttable(t);
123 return t;
124}
125
126
127/*
128** Rehash:
129** Check if table has deleted slots. It it has, it does not need to
130** grow, since rehash will reuse them.
131*/
132static int emptyslots (Hash *t)
133{
134 int i;
135 for (i=nhash(t)-1; i>=0; i--) {
136 Node *n = node(t, i);
137 if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) == LUA_T_NIL)
138 return 1;
139 }
140 return 0;
141}
142
143static void rehash (Hash *t)
144{
145 int nold = nhash(t);
146 Node *vold = nodevector(t);
147 int i;
148 if (!emptyslots(t))
149 nhash(t) = luaO_redimension(nhash(t));
150 nodevector(t) = hashnodecreate(nhash(t));
151 for (i=0; i<nold; i++) {
152 Node *n = vold+i;
153 if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL)
154 *node(t, present(t, ref(n))) = *n; /* copy old node to luaM_new hash */
155 }
156 luaM_free(vold);
157}
158
159/*
160** If the hash node is present, return its pointer, otherwise return
161** null.
162*/
163TObject *luaH_get (Hash *t, TObject *ref)
164{
165 int h = present(t, ref);
166 if (ttype(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
167 else return NULL;
168}
169
170
171/*
172** If the hash node is present, return its pointer, otherwise create a luaM_new
173** node for the given reference and also return its pointer.
174*/
175TObject *luaH_set (Hash *t, TObject *ref)
176{
177 Node *n = node(t, present(t, ref));
178 if (ttype(ref(n)) == LUA_T_NIL) {
179 nuse(t)++;
180 if ((float)nuse(t) > (float)nhash(t)*REHASH_LIMIT) {
181 rehash(t);
182 n = node(t, present(t, ref));
183 }
184 *ref(n) = *ref;
185 ttype(val(n)) = LUA_T_NIL;
186 }
187 return (val(n));
188}
189
190
191static Node *hashnext (Hash *t, int i)
192{
193 Node *n;
194 int tsize = nhash(t);
195 if (i >= tsize)
196 return NULL;
197 n = node(t, i);
198 while (ttype(ref(n)) == LUA_T_NIL || ttype(val(n)) == LUA_T_NIL) {
199 if (++i >= tsize)
200 return NULL;
201 n = node(t, i);
202 }
203 return node(t, i);
204}
205
206Node *luaH_next (TObject *o, TObject *r)
207{
208 Hash *t = avalue(o);
209 if (ttype(r) == LUA_T_NIL)
210 return hashnext(t, 0);
211 else {
212 int i = present(t, r);
213 Node *n = node(t, i);
214 luaL_arg_check(ttype(ref(n))!=LUA_T_NIL && ttype(val(n))!=LUA_T_NIL,
215 2, "key not found");
216 return hashnext(t, i+1);
217 }
218}
diff --git a/ltable.h b/ltable.h
new file mode 100644
index 00000000..2633a63f
--- /dev/null
+++ b/ltable.h
@@ -0,0 +1,27 @@
1/*
2** $Id: $
3** Lua tables (hash)
4** See Copyright Notice in lua.h
5*/
6
7#ifndef ltable_h
8#define ltable_h
9
10#include "lobject.h"
11
12
13extern Hash *luaH_root;
14
15
16#define node(t,i) (&(t)->node[i])
17#define ref(n) (&(n)->ref)
18#define nhash(t) ((t)->nhash)
19
20Hash *luaH_new (int nhash);
21void luaH_callIM (Hash *l);
22void luaH_free (Hash *frees);
23TObject *luaH_get (Hash *t, TObject *ref);
24TObject *luaH_set (Hash *t, TObject *ref);
25Node *luaH_next (TObject *o, TObject *r);
26
27#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2026-01-13 17:48:54 +0000