From b6f87491afe32140563fe3c546b8812c28a63410 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 9 Jun 2017 13:48:44 -0300 Subject: in hash nodes, keys are stored in separate pieces to avoid wasting space with alignments --- lobject.h | 98 +++++++++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 76 insertions(+), 22 deletions(-) (limited to 'lobject.h') diff --git a/lobject.h b/lobject.h index 2bef659a..97afa143 100644 --- a/lobject.h +++ b/lobject.h @@ -1,5 +1,5 @@ /* -** $Id: lobject.h,v 2.120 2017/04/30 20:43:26 roberto Exp roberto $ +** $Id: lobject.h,v 2.121 2017/06/01 20:24:05 roberto Exp roberto $ ** Type definitions for Lua objects ** See Copyright Notice in lua.h */ @@ -122,6 +122,7 @@ typedef struct lua_TValue { #define val_(o) ((o)->value_) +#define valraw(o) (&val_(o)) /* raw type tag of a TValue */ @@ -131,7 +132,8 @@ typedef struct lua_TValue { #define novariant(x) ((x) & 0x0F) /* type tag of a TValue (bits 0-3 for tags + variant bits 4-5) */ -#define ttype(o) (rttype(o) & 0x3F) +#define ttyperaw(t) ((t) & 0x3F) +#define ttype(o) ttyperaw(rttype(o)) /* type tag of a TValue with no variants (bits 0-3) */ #define ttnov(o) (novariant(rttype(o))) @@ -157,7 +159,19 @@ typedef struct lua_TValue { #define ttislcf(o) checktag((o), LUA_TLCF) #define ttisfulluserdata(o) checktag((o), ctb(LUA_TUSERDATA)) #define ttisthread(o) checktag((o), ctb(LUA_TTHREAD)) -#define ttisdeadkey(o) checktag((o), LUA_TDEADKEY) + + +/* +** Macros to access unstructured values (may come both from +** 'TValue's and table keys) +*/ +#define ivalueraw(v) ((v).i) +#define fltvalueraw(v) ((v).n) +#define gcvalueraw(v) ((v).gc) +#define pvalueraw(v) ((v).p) +#define tsvalueraw(v) (gco2ts((v).gc)) +#define fvalueraw(v) ((v).f) +#define bvalueraw(v) ((v).b) /* Macros to access values */ @@ -176,8 +190,6 @@ typedef struct lua_TValue { #define hvalue(o) check_exp(ttistable(o), gco2t(val_(o).gc)) #define bvalue(o) check_exp(ttisboolean(o), val_(o).b) #define thvalue(o) check_exp(ttisthread(o), gco2th(val_(o).gc)) -/* a dead value may get the 'gc' field, but cannot access its contents */ -#define deadvalue(o) check_exp(ttisdeadkey(o), cast(void *, val_(o).gc)) #define l_isfalse(o) (ttisnil(o) || (ttisboolean(o) && bvalue(o) == 0)) @@ -185,6 +197,12 @@ typedef struct lua_TValue { #define iscollectable(o) (rttype(o) & BIT_ISCOLLECTABLE) +/* +** Protected access to objects in values +*/ +#define gcvalueN(o) (iscollectable(o) ? gcvalue(o) : NULL) + + /* Macros for internal tests */ #define righttt(obj) (ttype(obj) == gcvalue(obj)->tt) @@ -253,8 +271,6 @@ typedef struct lua_TValue { val_(io).gc = obj2gco(x_); settt_(io, ctb(LUA_TTABLE)); \ checkliveness(L,io); } -#define setdeadvalue(obj) settt_(obj, LUA_TDEADKEY) - #define setobj(L,obj1,obj2) \ @@ -485,26 +501,37 @@ typedef union Closure { ** Tables */ -typedef union TKey { - struct { - TValuefields; - int next; /* for chaining (offset for next node) */ - } nk; - TValue tvk; -} TKey; + +/* +** Nodes for Hash tables. A pack of two TValue's (key-value pairs) +** plus a 'next' field to link colliding entries. The distribuition +** of the key's fields ('key_tt' and 'key_val') not forming a proper +** 'TValue' allows for a smaller size for 'Node' both in 4-byte +** and 8-byte alignments. +*/ +typedef union Node { + struct NodeKey { + TValuefields; /* fields for value */ + lu_byte key_tt; /* key type */ + int next; /* for chaining */ + Value key_val; /* key value */ + } u; + TValue i_val; /* direct access to node's value as a proper 'TValue' */ +} Node; -/* copy a value into a key without messing up field 'next' */ -#define setnodekey(L,key,obj) \ - { TKey *k_=(key); const TValue *io_=(obj); \ - k_->nk.value_ = io_->value_; k_->nk.tt_ = io_->tt_; \ +/* copy a value into a key */ +#define setnodekey(L,node,obj) \ + { Node *n_=(node); const TValue *io_=(obj); \ + n_->u.key_val = io_->value_; n_->u.key_tt = io_->tt_; \ (void)L; checkliveness(L,io_); } -typedef struct Node { - TValue i_val; - TKey i_key; -} Node; +/* copy a value from a key */ +#define getnodekey(L,obj,node) \ + { TValue *io_=(obj); const Node *n_=(node); \ + io_->value_ = n_->u.key_val; io_->tt_ = n_->u.key_tt; \ + (void)L; checkliveness(L,io_); } typedef struct Table { @@ -520,6 +547,33 @@ typedef struct Table { } Table; +/* +** Macros to manipulate keys inserted in nodes +*/ +#define keytt(node) ((node)->u.key_tt) +#define keyval(node) ((node)->u.key_val) + +#define keyisnil(node) (keytt(node) == LUA_TNIL) +#define keyisinteger(node) (keytt(node) == LUA_TNUMINT) +#define keyival(node) (keyval(node).i) +#define keyisshrstr(node) (keytt(node) == ctb(LUA_TSHRSTR)) +#define keystrval(node) (gco2ts(keyval(node).gc)) + +#define keyisdead(node) (keytt(node) == LUA_TDEADKEY) + +#define setnilkey(node) (keytt(node) = LUA_TNIL) +#define setdeadkey(node) (keytt(node) = LUA_TDEADKEY) + +/* a dead value may get the 'gc' field, but cannot access its contents */ +#define deadkey(n) \ + check_exp(keytt(n) == LUA_TDEADKEY, cast(void *, keyval(n).gc)) + +#define keyiscollectable(n) (keytt(n) & BIT_ISCOLLECTABLE) + +#define gckey(n) (keyval(n).gc) +#define gckeyN(n) (keyiscollectable(n) ? gckey(n) : NULL) + + /* ** 'module' operation for hashing (size is always a power of 2) -- cgit v1.2.3-55-g6feb