Small optimization in size of charset trees

Got a byte that was wasted for padding to be used in the bitmap.

3 files changed, 35 insertions, 29 deletions

diff --git a/lptree.c b/lptree.c
index c61a5db..ff5cb9d 100644
--- a/lptree.c
+++ b/lptree.c
@@ -335,7 +335,7 @@ static Pattern *getpattern (lua_State *L, int idx) {
 
 
 static int getsize (lua_State *L, int idx) {
-  return (lua_rawlen(L, idx) - sizeof(Pattern)) / sizeof(TTree) + 1;
+  return (lua_rawlen(L, idx) - offsetof(Pattern, tree)) / sizeof(TTree);
 }
 
 
@@ -348,12 +348,12 @@ static TTree *gettree (lua_State *L, int idx, int *len) {
 
 
 /*
-** create a pattern. Set its uservalue (the 'ktable') equal to its
-** metatable. (It could be any empty sequence; the metatable is at
-** hand here, so we use it.)
+** create a pattern followed by a tree with 'len' nodes. Set its
+** uservalue (the 'ktable') equal to its metatable. (It could be any
+** empty sequence; the metatable is at hand here, so we use it.)
 */
 static TTree *newtree (lua_State *L, int len) {
-  size_t size = (len - 1) * sizeof(TTree) + sizeof(Pattern);
+  size_t size = offsetof(Pattern, tree) + len * sizeof(TTree);
   Pattern *p = (Pattern *)lua_newuserdata(L, size);
   luaL_getmetatable(L, PATTERN_T);
   lua_pushvalue(L, -1);
@@ -371,40 +371,44 @@ static TTree *newleaf (lua_State *L, int tag) {
 }
 
 
-static TTree *newccharset (lua_State *L, byte *cs, charsetinfo *info) {
-  int i;
-  TTree *tree = newtree(L, bytes2slots(info->size) + 1);
-  tree->tag = TSet;
-  tree->u.set.offset = info->offset;
-  tree->u.set.size = info->size;
-  tree->u.set.deflt = info->deflt;
-  for (i = 0; i < info->size; i++)
-    treebuffer(tree)[i] = cs[info->offset + i];
-  return tree;
-}
-
-
+/*
+** Create a tree for a charset, optimizing for special cases: empty set,
+** full set, and singleton set.
+*/
 static TTree *newcharset (lua_State *L, byte *cs) {
   charsetinfo info;
   Opcode op = charsettype(cs, &info);
   switch (op) {
-    case IFail: return newleaf(L, TFalse);
-    case IAny: return newleaf(L, TAny);
-    case IChar: {
+    case IFail: return newleaf(L, TFalse);  /* empty set */
+    case IAny: return newleaf(L, TAny);  /* full set */
+    case IChar: {  /* singleton set */
       TTree *tree =newleaf(L, TChar);
       tree->u.n = info.offset;
       return tree;
     }
-    default:
+    default: {  /* regular set */
+      int i;
+      int bsize =  /* tree size in bytes */
+                  (int)offsetof(TTree, u.set.bitmap) + info.size;
+      TTree *tree = newtree(L, bytes2slots(bsize));
       assert(op == ISet);
-      return newccharset(L, cs, &info);
+      tree->tag = TSet;
+      tree->u.set.offset = info.offset;
+      tree->u.set.size = info.size;
+      tree->u.set.deflt = info.deflt;
+      for (i = 0; i < info.size; i++) {
+        assert(&treebuffer(tree)[i] < (byte*)tree + bsize);
+        treebuffer(tree)[i] = cs[info.offset + i];
+      }
+      return tree;
+    }
   }
 }
 
 
 /*
-** add to tree a sequence where first sibling is 'sib' (with size
-** 'sibsize'); returns position for second sibling
+** Add to tree a sequence where first sibling is 'sib' (with size
+** 'sibsize'); return position for second sibling.
 */
 static TTree *seqaux (TTree *tree, TTree *sib, int sibsize) {
   tree->tag = TSeq; tree->u.ps = sibsize + 1;
diff --git a/lptree.h b/lptree.h
index b76c235..7dab362 100644
--- a/lptree.h
+++ b/lptree.h
@@ -56,11 +56,16 @@ typedef struct TTree {
       byte offset;  /* compact set offset (in bytes) */
       byte size;  /* compact set size (in bytes) */
       byte deflt;  /* default value */
+      byte bitmap[1];  /* bitmap (open array) */
     } set;  /* for compact sets */
   } u;
 } TTree;
 
 
+/* access to charset */
+#define treebuffer(t)      ((t)->u.set.bitmap)
+
+
 /*
 ** A complete pattern has its tree plus, if already compiled,
 ** its corresponding code
diff --git a/lptypes.h b/lptypes.h
index 17d406e..e10d88b 100644
--- a/lptypes.h
+++ b/lptypes.h
@@ -101,11 +101,8 @@ typedef struct Charset {
 #define fillset(s,c)    memset(s,c,CHARSETSIZE)
 #define clearset(s)     fillset(s,0)
 
-/* access to charset */
-#define treebuffer(t)      ((byte *)((t) + 1))
-
 /* number of slots needed for 'n' bytes */
-#define bytes2slots(n)  (((n) - 1) / sizeof(TTree) + 1)
+#define bytes2slots(n)  (((n) - 1u) / (unsigned int)sizeof(TTree) + 1u)
 
 /* set 'b' bit in charset 'cs' */
 #define setchar(cs,b)   ((cs)[(b) >> 3] |= (1 << ((b) & 7)))