RAA: clean up the RAA infrastructure, make it support larger indicies

Make the RAA infrastructure a bit cleaner, make it support 64-bit
indicies, and reduce the memory overhead of a sparse or small RAA --
the old code would allocate a *minimum* of 256K for each RAA.  The new
code reduces that to 16K, and will not mandatorily allocate an entry
in the zero position.

The new shift, 11, was chosen so that a 32-bit RAA value will need 3
layers and a 64-bit value 6 layers, without excessive waste.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>

1 files changed, 59 insertions, 61 deletions

diff --git a/nasmlib/raa.c b/nasmlib/raa.c
index dd510dfb..feb86970 100644
--- a/nasmlib/raa.c
+++ b/nasmlib/raa.c
@@ -33,6 +33,7 @@
 
 #include "nasmlib.h"
 #include "raa.h"
+#include "ilog2.h"
 
 /*
  * Routines to manage a dynamic random access array of int64_ts which
@@ -40,10 +41,9 @@
  * chunk.
  */
 
-#define RAA_BLKSHIFT	15      /* 2**this many longs allocated at once */
-#define RAA_BLKSIZE	(1 << RAA_BLKSHIFT)
-#define RAA_LAYERSHIFT	15      /* 2**this many _pointers_ allocated */
-#define RAA_LAYERSIZE	(1 << RAA_LAYERSHIFT)
+#define RAA_LAYERSHIFT	11      /* 2^this many items per layer */
+#define RAA_LAYERSIZE	((size_t)1 << RAA_LAYERSHIFT)
+#define RAA_LAYERMASK	(RAA_LAYERSIZE-1)
 
 typedef struct RAA RAA;
 typedef union RAA_UNION RAA_UNION;
@@ -56,27 +56,32 @@ union intorptr {
 };
 
 struct RAA {
+    /* Last position in this RAA */
+    raaindex endposn;
+
     /*
      * Number of layers below this one to get to the real data. 0
-     * means this structure is a leaf, holding RAA_BLKSIZE real
+     * means this structure is a leaf, holding RAA_LAYERSIZE real
      * data items; 1 and above mean it's a branch, holding
      * RAA_LAYERSIZE pointers to the next level branch or leaf
      * structures.
      */
-    int layers;
+    unsigned int layers;
 
     /*
      * Number of real data items spanned by one position in the
      * `data' array at this level. This number is 0 trivially, for
-     * a leaf (level 0): for a level 1 branch it should be
-     * RAA_BLKSHIFT, and for a level 2 branch it's
-     * RAA_LAYERSHIFT+RAA_BLKSHIFT.
+     * a leaf (level 0): for a level n branch it should be
+     * n*RAA_LAYERSHIFT.
      */
-    int shift;
+    unsigned int shift;
 
+    /*
+     * The actual data
+     */
     union RAA_UNION {
         struct RAA_LEAF {
-            union intorptr data[RAA_BLKSIZE];
+            union intorptr data[RAA_LAYERSIZE];
         } l;
         struct RAA_BRANCH {
             struct RAA *data[RAA_LAYERSIZE];
@@ -87,54 +92,50 @@ struct RAA {
 #define LEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
 #define BRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
 
-#define LAYERSHIFT(r) ( (r)->layers==0 ? RAA_BLKSHIFT : RAA_LAYERSHIFT )
-
-static struct RAA *real_raa_init(int layers)
+static struct RAA *raa_init_layer(raaindex posn, unsigned int layers)
 {
     struct RAA *r;
+    raaindex posmask;
 
-    if (layers == 0) {
-        r = nasm_zalloc(LEAFSIZ);
-        r->shift = 0;
-    } else {
-        r = nasm_zalloc(BRANCHSIZ);
-        r->layers = layers;
-        r->shift = (RAA_BLKSHIFT - RAA_LAYERSHIFT) + layers * RAA_LAYERSHIFT;
-    }
+    r = nasm_zalloc((layers == 0) ? LEAFSIZ : BRANCHSIZ);
+    r->shift = layers * RAA_LAYERSHIFT;
+    r->layers    = layers;
+    posmask = ((raaindex)RAA_LAYERSIZE << r->shift) - 1;
+    r->endposn   = posn | posmask;
     return r;
 }
 
-struct RAA *raa_init(void)
-{
-    return real_raa_init(0);
-}
-
 void raa_free(struct RAA *r)
 {
+    if (!r)
+        return;
+
     if (r->layers) {
-        struct RAA **p;
-        for (p = r->u.b.data; p - r->u.b.data < RAA_LAYERSIZE; p++)
-            if (*p)
-                raa_free(*p);
+        struct RAA **p = r->u.b.data;
+        size_t i;
+        for (i = 0; i < RAA_LAYERSIZE; i++)
+            raa_free(*p++);
     }
     nasm_free(r);
 }
 
-static const union intorptr *real_raa_read(struct RAA *r, int32_t posn)
+static const union intorptr *real_raa_read(struct RAA *r, raaindex posn)
 {
-    if ((uint32_t) posn >= (UINT32_C(1) << (r->shift + LAYERSHIFT(r))))
+    nasm_assert(posn <= (~(raaindex)0 >> 1));
+
+    if (unlikely(!r || posn > r->endposn))
         return NULL;            /* Beyond the end */
-    while (r->layers > 0) {
-        int32_t l = posn >> r->shift;
-        posn &= (UINT32_C(1) << r->shift) - 1;
+
+    while (r->layers) {
+        size_t l = (posn >> r->shift) & RAA_LAYERMASK;
         r = r->u.b.data[l];
         if (!r)
             return NULL;        /* Not present */
     }
-    return &r->u.l.data[posn];
+    return &r->u.l.data[posn & RAA_LAYERMASK];
 }
 
-int64_t raa_read(struct RAA *r, int32_t pos)
+int64_t raa_read(struct RAA *r, raaindex pos)
 {
     const union intorptr *ip;
 
@@ -142,7 +143,7 @@ int64_t raa_read(struct RAA *r, int32_t pos)
     return ip ? ip->i : 0;
 }
 
-void *raa_read_ptr(struct RAA *r, int32_t pos)
+void *raa_read_ptr(struct RAA *r, raaindex pos)
 {
     const union intorptr *ip;
 
@@ -152,43 +153,40 @@ void *raa_read_ptr(struct RAA *r, int32_t pos)
 
 
 static struct RAA *
-real_raa_write(struct RAA *r, int32_t posn, union intorptr value)
+real_raa_write(struct RAA *r, raaindex posn, union intorptr value)
 {
     struct RAA *result;
 
-    nasm_assert(posn >= 0);
+    nasm_assert(posn <= (~(raaindex)0 >> 1));
 
-    while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) {
-        /*
-         * Must add a layer.
-         */
-        struct RAA *s;
-
-        s = nasm_zalloc(BRANCHSIZ);
-        s->layers = r->layers + 1;
-        s->shift = LAYERSHIFT(r) + r->shift;
-        s->u.b.data[0] = r;
-        r = s;
+    if (unlikely(!r)) {
+        /* Create a new top-level RAA */
+        r = raa_init_layer(posn, ilog2_64(posn)/RAA_LAYERSHIFT);
+    } else {
+        while (unlikely(r->endposn < posn)) {
+            /* We need to add layers to an existing RAA */
+            struct RAA *s = raa_init_layer(r->endposn, r->layers + 1);
+            s->u.b.data[0] = r;
+            r = s;
+        }
     }
 
     result = r;
 
-    while (r->layers > 0) {
+    while (r->layers) {
         struct RAA **s;
-        int32_t l = posn >> r->shift;
-        posn &= (UINT32_C(1) << r->shift) - 1;
+        size_t l = (posn >> r->shift) & RAA_LAYERMASK;
         s = &r->u.b.data[l];
-        if (!*s)
-            *s = real_raa_init(r->layers - 1);
+        if (unlikely(!*s))
+            *s = raa_init_layer(posn, r->layers - 1);
         r = *s;
     }
-
-    r->u.l.data[posn] = value;
+    r->u.l.data[posn & RAA_LAYERMASK] = value;
 
     return result;
 }
 
-struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value)
+struct RAA *raa_write(struct RAA *r, raaindex posn, int64_t value)
 {
     union intorptr ip;
 
@@ -196,7 +194,7 @@ struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value)
     return real_raa_write(r, posn, ip);
 }
 
-struct RAA *raa_write_ptr(struct RAA *r, int32_t posn, void *value)
+struct RAA *raa_write_ptr(struct RAA *r, raaindex posn, void *value)
 {
     union intorptr ip;