ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

ltable.cpp

Go to the documentation of this file.
00001 /*
00002 ** Lua tables (hash)
00003 ** See Copyright Notice in lua.h
00004 */
00005 
00006 #define FORBIDDEN_SYMBOL_EXCEPTION_setjmp
00007 #define FORBIDDEN_SYMBOL_EXCEPTION_longjmp
00008 
00009 #include "engines/grim/lua/lauxlib.h"
00010 #include "engines/grim/lua/lmem.h"
00011 #include "engines/grim/lua/lobject.h"
00012 #include "engines/grim/lua/lstate.h"
00013 #include "engines/grim/lua/ltable.h"
00014 #include "engines/grim/lua/lua.h"
00015 
00016 namespace Grim {
00017 
00018 #define gcsize(n)       (1 + (n / 16))
00019 #define nuse(t)         ((t)->nuse)
00020 #define nodevector(t)   ((t)->node)
00021 #define REHASH_LIMIT    0.70    // avoid more than this % full
00022 #define TagDefault      LUA_T_ARRAY;
00023 
00024 static uintptr hashindex(TObject *ref) {
00025     uintptr h;
00026 
00027     switch (ttype(ref)) {
00028     case LUA_T_NUMBER:
00029         h = (uintptr)nvalue(ref);
00030         break;
00031     case LUA_T_USERDATA:
00032         h = (uintptr)ref->value.ud.id;
00033         break;
00034     case LUA_T_STRING:
00035         h = (uintptr)tsvalue(ref);
00036         break;
00037     case LUA_T_ARRAY:
00038         h = (uintptr)avalue(ref);
00039         break;
00040     case LUA_T_PROTO:
00041         h = (uintptr)tfvalue(ref);
00042         break;
00043     case LUA_T_CPROTO:
00044         h = (uintptr)fvalue(ref);
00045         break;
00046     case LUA_T_CLOSURE:
00047         h = (uintptr)clvalue(ref);
00048         break;
00049     case LUA_T_TASK:
00050         h = (uintptr)nvalue(ref);
00051         break;
00052     default:
00053         lua_error("unexpected type to index table");
00054         h = 0;  // to avoid warnings
00055     }
00056     return h;
00057 }
00058 
00059 int32 present(Hash *t, TObject *key) {
00060     int32 tsize = nhash(t);
00061     uintptr h = hashindex(key);
00062     int32 h1 = int32(h % tsize);
00063     TObject *rf = ref(node(t, h1));
00064     if (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf)) {
00065         int32 h2 = int32(h % (tsize - 2) + 1);
00066         do {
00067             h1 += h2;
00068             if (h1 >= tsize)
00069                 h1 -= tsize;
00070             rf = ref(node(t, h1));
00071         } while (ttype(rf) != LUA_T_NIL && !luaO_equalObj(key, rf));
00072     }
00073     return h1;
00074 }
00075 
00076 
00077 /*
00078 ** Alloc a vector node
00079 */
00080 Node *hashnodecreate(int32 nhash) {
00081     Node *v = luaM_newvector(nhash, Node);
00082     int32 i;
00083     for (i = 0; i < nhash; i++)
00084         ttype(ref(&v[i])) = LUA_T_NIL;
00085     return v;
00086 }
00087 
00088 /*
00089 ** Delete a hash
00090 */
00091 static void hashdelete(Hash *t) {
00092     luaM_free(nodevector(t));
00093     luaM_free(t);
00094 }
00095 
00096 void luaH_free(Hash *frees) {
00097     while (frees) {
00098         Hash *next = (Hash *)frees->head.next;
00099         nblocks -= gcsize(frees->nhash);
00100         hashdelete(frees);
00101         frees = next;
00102     }
00103 }
00104 
00105 Hash *luaH_new(int32 nhash) {
00106     Hash *t = luaM_new(Hash);
00107     nhash = luaO_redimension((int32)((float)nhash / REHASH_LIMIT));
00108     nodevector(t) = hashnodecreate(nhash);
00109     nhash(t) = nhash;
00110     nuse(t) = 0;
00111     t->htag = TagDefault;
00112     luaO_insertlist(&roottable, (GCnode *)t);
00113     nblocks += gcsize(nhash);
00114     return t;
00115 }
00116 
00117 /*
00118 ** Rehash:
00119 ** Check if table has deleted slots. It it has, it does not need to
00120 ** grow, since rehash will reuse them.
00121 */
00122 static int emptyslots(Hash *t) {
00123     int i;
00124 
00125     for (i = nhash(t) - 1; i >= 0; i--) {
00126         Node *n = node(t, i);
00127         if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) == LUA_T_NIL)
00128             return 1;
00129     }
00130     return 0;
00131 }
00132 
00133 static void rehash(Hash *t) {
00134     int32 nold = nhash(t);
00135     Node *vold = nodevector(t);
00136     int32 i;
00137     if (!emptyslots(t))
00138         nhash(t) = luaO_redimension(nhash(t));
00139     nodevector(t) = hashnodecreate(nhash(t));
00140     for (i = 0; i < nold; i++) {
00141         Node *n = vold + i;
00142         if (ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL)
00143             *node(t, present(t, ref(n))) = *n;  // copy old node to luaM_new hash
00144     }
00145     nblocks += gcsize(t->nhash) - gcsize(nold);
00146     luaM_free(vold);
00147 }
00148 
00149 /*
00150 ** If the hash node is present, return its pointer, otherwise return
00151 ** null.
00152 */
00153 TObject *luaH_get(Hash *t, TObject *r) {
00154     int32 h = present(t, r);
00155     if (ttype(ref(node(t, h))) != LUA_T_NIL)
00156         return val(node(t, h));
00157     else
00158         return nullptr;
00159 }
00160 
00161 /*
00162 ** If the hash node is present, return its pointer, otherwise create a luaM_new
00163 ** node for the given reference and also return its pointer.
00164 */
00165 TObject *luaH_set(Hash *t, TObject *r) {
00166     Node *n = node(t, present(t, r));
00167     if (ttype(ref(n)) == LUA_T_NIL) {
00168         nuse(t)++;
00169         if ((float)nuse(t) > (float)nhash(t) * REHASH_LIMIT) {
00170             rehash(t);
00171             n = node(t, present(t, r));
00172         }
00173         *ref(n) = *r;
00174         ttype(val(n)) = LUA_T_NIL;
00175     }
00176     return (val(n));
00177 }
00178 
00179 static Node *hashnext(Hash *t, int32 i) {
00180     Node *n;
00181     int32 tsize = nhash(t);
00182     if (i >= tsize)
00183         return nullptr;
00184     n = node(t, i);
00185     while (ttype(ref(n)) == LUA_T_NIL || ttype(val(n)) == LUA_T_NIL) {
00186         if (++i >= tsize)
00187             return nullptr;
00188         n = node(t, i);
00189     }
00190     return node(t, i);
00191 }
00192 
00193 Node *luaH_next(TObject *o, TObject *r) {
00194     Hash *t = avalue(o);
00195     if (ttype(r) == LUA_T_NIL)
00196         return hashnext(t, 0);
00197     else {
00198         int32 i = present(t, r);
00199         Node *n = node(t, i);
00200         luaL_arg_check(ttype(ref(n)) != LUA_T_NIL && ttype(val(n)) != LUA_T_NIL, 2, "key not found");
00201         return hashnext(t, i + 1);
00202     }
00203 }
00204 
00205 } // end of namespace Grim


Generated on Sat Mar 16 2019 05:01:43 for ResidualVM by doxygen 1.7.1
curved edge   curved edge