lua

A copy of the Lua development repository
Log | Files | Refs | README

ltable.h (6435B)


      1 /*
      2 ** $Id: ltable.h $
      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 
     13 #define gnode(t,i)	(&(t)->node[i])
     14 #define gval(n)		(&(n)->i_val)
     15 #define gnext(n)	((n)->u.next)
     16 
     17 
     18 /*
     19 ** Clear all bits of fast-access metamethods, which means that the table
     20 ** may have any of these metamethods. (First access that fails after the
     21 ** clearing will set the bit again.)
     22 */
     23 #define invalidateTMcache(t)	((t)->flags &= cast_byte(~maskflags))
     24 
     25 
     26 /*
     27 ** Bit BITDUMMY set in 'flags' means the table is using the dummy node
     28 ** for its hash part.
     29 */
     30 
     31 #define BITDUMMY		(1 << 6)
     32 #define NOTBITDUMMY		cast_byte(~BITDUMMY)
     33 #define isdummy(t)		((t)->flags & BITDUMMY)
     34 
     35 #define setnodummy(t)		((t)->flags &= NOTBITDUMMY)
     36 #define setdummy(t)		((t)->flags |= BITDUMMY)
     37 
     38 
     39 
     40 /* allocated size for hash nodes */
     41 #define allocsizenode(t)	(isdummy(t) ? 0 : sizenode(t))
     42 
     43 
     44 /* returns the Node, given the value of a table entry */
     45 #define nodefromval(v)	cast(Node *, (v))
     46 
     47 
     48 
     49 #define luaH_fastgeti(t,k,res,tag) \
     50   { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \
     51     if ((u < h->asize)) { \
     52       tag = *getArrTag(h, u); \
     53       if (!tagisempty(tag)) { farr2val(h, u, tag, res); }} \
     54     else { tag = luaH_getint(h, (k), res); }}
     55 
     56 
     57 #define luaH_fastseti(t,k,val,hres) \
     58   { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \
     59     if ((u < h->asize)) { \
     60       lu_byte *tag = getArrTag(h, u); \
     61       if (checknoTM(h->metatable, TM_NEWINDEX) || !tagisempty(*tag)) \
     62         { fval2arr(h, u, tag, val); hres = HOK; } \
     63       else hres = ~cast_int(u); } \
     64     else { hres = luaH_psetint(h, k, val); }}
     65 
     66 
     67 /* results from pset */
     68 #define HOK		0
     69 #define HNOTFOUND	1
     70 #define HNOTATABLE	2
     71 #define HFIRSTNODE	3
     72 
     73 /*
     74 ** 'luaH_get*' operations set 'res', unless the value is absent, and
     75 ** return the tag of the result.
     76 ** The 'luaH_pset*' (pre-set) operations set the given value and return
     77 ** HOK, unless the original value is absent. In that case, if the key
     78 ** is really absent, they return HNOTFOUND. Otherwise, if there is a
     79 ** slot with that key but with no value, 'luaH_pset*' return an encoding
     80 ** of where the key is (usually called 'hres'). (pset cannot set that
     81 ** value because there might be a metamethod.) If the slot is in the
     82 ** hash part, the encoding is (HFIRSTNODE + hash index); if the slot is
     83 ** in the array part, the encoding is (~array index), a negative value.
     84 ** The value HNOTATABLE is used by the fast macros to signal that the
     85 ** value being indexed is not a table.
     86 ** (The size for the array part is limited by the maximum power of two
     87 ** that fits in an unsigned integer; that is INT_MAX+1. So, the C-index
     88 ** ranges from 0, which encodes to -1, to INT_MAX, which encodes to
     89 ** INT_MIN. The size of the hash part is limited by the maximum power of
     90 ** two that fits in a signed integer; that is (INT_MAX+1)/2. So, it is
     91 ** safe to add HFIRSTNODE to any index there.)
     92 */
     93 
     94 
     95 /*
     96 ** The array part of a table is represented by an inverted array of
     97 ** values followed by an array of tags, to avoid wasting space with
     98 ** padding. In between them there is an unsigned int, explained later.
     99 ** The 'array' pointer points between the two arrays, so that values are
    100 ** indexed with negative indices and tags with non-negative indices.
    101 
    102              Values                              Tags
    103   --------------------------------------------------------
    104   ...  |   Value 1     |   Value 0     |unsigned|0|1|...
    105   --------------------------------------------------------
    106                                        ^ t->array
    107 
    108 ** All accesses to 't->array' should be through the macros 'getArrTag'
    109 ** and 'getArrVal'.
    110 */
    111 
    112 /* Computes the address of the tag for the abstract C-index 'k' */
    113 #define getArrTag(t,k)	(cast(lu_byte*, (t)->array) + sizeof(unsigned) + (k))
    114 
    115 /* Computes the address of the value for the abstract C-index 'k' */
    116 #define getArrVal(t,k)	((t)->array - 1 - (k))
    117 
    118 
    119 /*
    120 ** The unsigned between the two arrays is used as a hint for #t;
    121 ** see luaH_getn. It is stored there to avoid wasting space in
    122 ** the structure Table for tables with no array part.
    123 */
    124 #define lenhint(t)	cast(unsigned*, (t)->array)
    125 
    126 
    127 /*
    128 ** Move TValues to/from arrays, using C indices
    129 */
    130 #define arr2obj(h,k,val)  \
    131   ((val)->tt_ = *getArrTag(h,(k)), (val)->value_ = *getArrVal(h,(k)))
    132 
    133 #define obj2arr(h,k,val)  \
    134   (*getArrTag(h,(k)) = (val)->tt_, *getArrVal(h,(k)) = (val)->value_)
    135 
    136 
    137 /*
    138 ** Often, we need to check the tag of a value before moving it. The
    139 ** following macros also move TValues to/from arrays, but receive the
    140 ** precomputed tag value or address as an extra argument.
    141 */
    142 #define farr2val(h,k,tag,res)  \
    143   ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,(k)))
    144 
    145 #define fval2arr(h,k,tag,val)  \
    146   (*tag = (val)->tt_, *getArrVal(h,(k)) = (val)->value_)
    147 
    148 
    149 LUAI_FUNC lu_byte luaH_get (Table *t, const TValue *key, TValue *res);
    150 LUAI_FUNC lu_byte luaH_getshortstr (Table *t, TString *key, TValue *res);
    151 LUAI_FUNC lu_byte luaH_getstr (Table *t, TString *key, TValue *res);
    152 LUAI_FUNC lu_byte luaH_getint (Table *t, lua_Integer key, TValue *res);
    153 
    154 /* Special get for metamethods */
    155 LUAI_FUNC const TValue *luaH_Hgetshortstr (Table *t, TString *key);
    156 
    157 LUAI_FUNC int luaH_psetint (Table *t, lua_Integer key, TValue *val);
    158 LUAI_FUNC int luaH_psetshortstr (Table *t, TString *key, TValue *val);
    159 LUAI_FUNC int luaH_psetstr (Table *t, TString *key, TValue *val);
    160 LUAI_FUNC int luaH_pset (Table *t, const TValue *key, TValue *val);
    161 
    162 LUAI_FUNC void luaH_setint (lua_State *L, Table *t, lua_Integer key,
    163                                                     TValue *value);
    164 LUAI_FUNC void luaH_set (lua_State *L, Table *t, const TValue *key,
    165                                                  TValue *value);
    166 
    167 LUAI_FUNC void luaH_finishset (lua_State *L, Table *t, const TValue *key,
    168                                               TValue *value, int hres);
    169 LUAI_FUNC Table *luaH_new (lua_State *L);
    170 LUAI_FUNC void luaH_resize (lua_State *L, Table *t, unsigned nasize,
    171                                                     unsigned nhsize);
    172 LUAI_FUNC void luaH_resizearray (lua_State *L, Table *t, unsigned nasize);
    173 LUAI_FUNC lu_mem luaH_size (Table *t);
    174 LUAI_FUNC void luaH_free (lua_State *L, Table *t);
    175 LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key);
    176 LUAI_FUNC lua_Unsigned luaH_getn (Table *t);
    177 
    178 
    179 #if defined(LUA_DEBUG)
    180 LUAI_FUNC Node *luaH_mainposition (const Table *t, const TValue *key);
    181 #endif
    182 
    183 
    184 #endif