aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>1999-01-22 16:47:23 -0200
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>1999-01-22 16:47:23 -0200
commit933bead92e48cdd8f2c9b5953854270e98d58c9a (patch)
tree38877ad72b5ca9f3f8704847655da50f5dbcc9a4
parent3314f49ec46edae53c34ecc1cedf7a9d0e345840 (diff)
downloadlua-933bead92e48cdd8f2c9b5953854270e98d58c9a.tar.gz
lua-933bead92e48cdd8f2c9b5953854270e98d58c9a.tar.bz2
lua-933bead92e48cdd8f2c9b5953854270e98d58c9a.zip
small optimizations(?)
Diffstat
-rw-r--r--ltable.c85
1 files changed, 36 insertions, 49 deletions
diff --git a/ltable.c b/ltable.c
index c875d189..205ab574 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: ltable.c,v 1.16 1998/12/30 13:14:46 roberto Exp $ 2** $Id: ltable.c,v 1.17 1999/01/04 12:54:33 roberto Exp $
3** Lua tables (hash) 3** Lua tables (hash)
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -24,8 +24,7 @@
24 24
25 25
26 26
27static long int hashindex (TObject *ref) 27static long int hashindex (TObject *ref) {
28{
29 long int h; 28 long int h;
30 switch (ttype(ref)) { 29 switch (ttype(ref)) {
31 case LUA_T_NUMBER: 30 case LUA_T_NUMBER:
@@ -54,57 +53,46 @@ static long int hashindex (TObject *ref)
54} 53}
55 54
56 55
57static int present (Hash *t, TObject *key) 56static Node *present (Hash *t, TObject *key) {
58{
59 int tsize = nhash(t); 57 int tsize = nhash(t);
60 long int h = hashindex(key); 58 long int h = hashindex(key);
61 int h1 = h%tsize; 59 int h1 = h%tsize;
62 TObject *rf = ref(node(t, h1)); 60 Node *n = node(t, h1);
63 if (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf)) { 61 /* keep looking until an entry with "ref" equal to key or nil */
62 if ((ttype(ref(n)) == ttype(key) ? !luaO_equalval(key, ref(n))
63 : ttype(ref(n)) != LUA_T_NIL)) {
64 int h2 = h%(tsize-2) + 1; 64 int h2 = h%(tsize-2) + 1;
65 do { 65 do {
66 h1 += h2; 66 h1 += h2;
67 if (h1 >= tsize) h1 -= tsize; 67 if (h1 >= tsize) h1 -= tsize;
68 rf = ref(node(t, h1)); 68 n = node(t, h1);
69 } while (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf)); 69 } while ((ttype(ref(n)) == ttype(key) ? !luaO_equalval(key, ref(n))
70 : ttype(ref(n)) != LUA_T_NIL));
70 } 71 }
71 return h1; 72 return n;
72} 73}
73 74
74 75
75/* 76void luaH_free (Hash *frees) {
76** Alloc a vector node
77*/
78static Node *hashnodecreate (int nhash)
79{
80 Node *v = luaM_newvector(nhash, Node);
81 int i;
82 for (i=0; i<nhash; i++)
83 ttype(ref(&v[i])) = LUA_T_NIL;
84 return v;
85}
86
87/*
88** Delete a hash
89*/
90static void hashdelete (Hash *t)
91{
92 luaM_free(nodevector(t));
93 luaM_free(t);
94}
95
96
97void luaH_free (Hash *frees)
98{
99 while (frees) { 77 while (frees) {
100 Hash *next = (Hash *)frees->head.next; 78 Hash *next = (Hash *)frees->head.next;
101 L->nblocks -= gcsize(frees->nhash); 79 L->nblocks -= gcsize(frees->nhash);
102 hashdelete(frees); 80 luaM_free(nodevector(frees));
81 luaM_free(frees);
103 frees = next; 82 frees = next;
104 } 83 }
105} 84}
106 85
107 86
87static Node *hashnodecreate (int nhash) {
88 Node *v = luaM_newvector(nhash, Node);
89 int i;
90 for (i=0; i<nhash; i++)
91 ttype(ref(&v[i])) = LUA_T_NIL;
92 return v;
93}
94
95
108Hash *luaH_new (int nhash) { 96Hash *luaH_new (int nhash) {
109 Hash *t = luaM_new(Hash); 97 Hash *t = luaM_new(Hash);
110 nhash = luaO_redimension(nhash*3/2); 98 nhash = luaO_redimension(nhash*3/2);
@@ -130,6 +118,7 @@ static int newsize (Hash *t) {
130 return luaO_redimension((realuse+1)*2); /* +1 is the new element */ 118 return luaO_redimension((realuse+1)*2); /* +1 is the new element */
131} 119}
132 120
121
133static void rehash (Hash *t) { 122static void rehash (Hash *t) {
134 int nold = nhash(t); 123 int nold = nhash(t);
135 Node *vold = nodevector(t); 124 Node *vold = nodevector(t);
@@ -141,7 +130,7 @@ static void rehash (Hash *t) {
141 for (i=0; i<nold; i++) { 130 for (i=0; i<nold; i++) {
142 Node *n = vold+i; 131 Node *n = vold+i;
143 if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL) { 132 if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL) {
144 *node(t, present(t, ref(n))) = *n; /* copy old node to luaM_new hash */ 133 *present(t, ref(n)) = *n; /* copy old node to new hash */
145 nuse(t)++; 134 nuse(t)++;
146 } 135 }
147 } 136 }
@@ -149,29 +138,28 @@ static void rehash (Hash *t) {
149 luaM_free(vold); 138 luaM_free(vold);
150} 139}
151 140
141
152/* 142/*
153** If the hash node is present, return its pointer, otherwise return 143** If the hash node is present, return its pointer, otherwise return
154** null. 144** null.
155*/ 145*/
156TObject *luaH_get (Hash *t, TObject *ref) 146TObject *luaH_get (Hash *t, TObject *ref) {
157{ 147 Node *n = present(t, ref);
158 int h = present(t, ref); 148 if (ttype(ref(n)) != LUA_T_NIL) return val(n);
159 if (ttype(ref(node(t, h))) != LUA_T_NIL) return val(node(t, h));
160 else return &luaO_nilobject; 149 else return &luaO_nilobject;
161} 150}
162 151
163 152
164/* 153/*
165** If the hash node is present, return its pointer, otherwise create a luaM_new 154** If the hash node is present, return its pointer, otherwise create a new
166** node for the given reference and also return its pointer. 155** node for the given reference and also return its pointer.
167*/ 156*/
168TObject *luaH_set (Hash *t, TObject *ref) 157TObject *luaH_set (Hash *t, TObject *ref) {
169{ 158 Node *n = present(t, ref);
170 Node *n = node(t, present(t, ref));
171 if (ttype(ref(n)) == LUA_T_NIL) { 159 if (ttype(ref(n)) == LUA_T_NIL) {
172 if ((long)nuse(t)*3L > (long)nhash(t)*2L) { 160 if ((long)nuse(t)*3L > (long)nhash(t)*2L) {
173 rehash(t); 161 rehash(t);
174 n = node(t, present(t, ref)); 162 n = present(t, ref);
175 } 163 }
176 nuse(t)++; 164 nuse(t)++;
177 *ref(n) = *ref; 165 *ref(n) = *ref;
@@ -192,18 +180,17 @@ static Node *hashnext (Hash *t, int i) {
192 return NULL; 180 return NULL;
193 n = node(t, i); 181 n = node(t, i);
194 } 182 }
195 return node(t, i); 183 return n;
196} 184}
197 185
198Node *luaH_next (Hash *t, TObject *r) { 186Node *luaH_next (Hash *t, TObject *r) {
199 if (ttype(r) == LUA_T_NIL) 187 if (ttype(r) == LUA_T_NIL)
200 return hashnext(t, 0); 188 return hashnext(t, 0);
201 else { 189 else {
202 int i = present(t, r); 190 Node *n = present(t, r);
203 Node *n = node(t, i);
204 luaL_arg_check(ttype(ref(n))!=LUA_T_NIL && ttype(val(n))!=LUA_T_NIL, 191 luaL_arg_check(ttype(ref(n))!=LUA_T_NIL && ttype(val(n))!=LUA_T_NIL,
205 2, "key not found"); 192 2, "key not found");
206 return hashnext(t, i+1); 193 return hashnext(t, (n-(t->node))+1);
207 } 194 }
208} 195}
209 196
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-16 23:19:36 +0000