nasmlib/raa.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2018 The NASM Authors - All Rights Reserved
   4  *   See the file AUTHORS included with the NASM distribution for
   5  *   the specific copyright holders.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following
   9  *   conditions are met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following
  15  *     disclaimer in the documentation and/or other materials provided
  16  *     with the distribution.
  17  *
  18  *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  19  *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21  *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  29  *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  30  *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  *
  32  * ----------------------------------------------------------------------- */
  33
  34 #include "nasmlib.h"
  35 #include "raa.h"
  36
  37 /*
  38  * Routines to manage a dynamic random access array of int64_ts which
  39  * may grow in size to be more than the largest single malloc'able
  40  * chunk.
  41  */
  42
  43 #define RAA_BLKSHIFT    15      /* 2**this many longs allocated at once */
  44 #define RAA_BLKSIZE     (1 << RAA_BLKSHIFT)
  45 #define RAA_LAYERSHIFT  15      /* 2**this many _pointers_ allocated */
  46 #define RAA_LAYERSIZE   (1 << RAA_LAYERSHIFT)
  47
  48 typedef union RAA_UNION RAA_UNION;
  49 typedef struct RAA_LEAF RAA_LEAF;
  50 typedef struct RAA_BRANCH RAA_BRANCH;
  51
  52 struct real_raa {
  53     /*
  54      * Number of layers below this one to get to the real data. 0
  55      * means this structure is a leaf, holding RAA_BLKSIZE real
  56      * data items; 1 and above mean it's a branch, holding
  57      * RAA_LAYERSIZE pointers to the next level branch or leaf
  58      * structures.
  59      */
  60     int layers;
  61
  62     /*
  63      * Number of real data items spanned by one position in the
  64      * `data' array at this level. This number is 0 trivially, for
  65      * a leaf (level 0): for a level 1 branch it should be
  66      * RAA_BLKSHIFT, and for a level 2 branch it's
  67      * RAA_LAYERSHIFT+RAA_BLKSHIFT.
  68      */
  69     int shift;
  70
  71     union RAA_UNION {
  72         struct RAA_LEAF {
  73             union intorptr data[RAA_BLKSIZE];
  74         } l;
  75         struct RAA_BRANCH {
  76             struct real_raa *data[RAA_LAYERSIZE];
  77         } b;
  78     } u;
  79 };
  80
  81 struct RAA {
  82     struct real_raa raa;
  83 };
  84 struct RAAPTR {
  85     struct real_raa raa;
  86 };
  87
  88 #define LEAFSIZ (sizeof(struct real_raa)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
  89 #define BRANCHSIZ (sizeof(struct real_raa)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
  90
  91 #define LAYERSHIFT(r) ( (r)->layers==0 ? RAA_BLKSHIFT : RAA_LAYERSHIFT )
  92
  93 static struct real_raa *raa_init_layer(int layers)
  94 {
  95     struct real_raa *r;
  96
  97     if (layers == 0) {
  98         r = nasm_zalloc(LEAFSIZ);
  99         r->shift = 0;
 100     } else {
 101         r = nasm_zalloc(BRANCHSIZ);
 102         r->layers = layers;
 103         r->shift = (RAA_BLKSHIFT - RAA_LAYERSHIFT) + layers * RAA_LAYERSHIFT;
 104     }
 105     return r;
 106 }
 107
 108 struct real_raa *real_raa_init(void)
 109 {
 110     return raa_init_layer(0);
 111 }
 112
 113 void real_raa_free(struct real_raa *r)
 114 {
 115     if (r->layers) {
 116         struct real_raa **p;
 117         for (p = r->u.b.data; p - r->u.b.data < RAA_LAYERSIZE; p++)
 118             if (*p)
 119                 real_raa_free(*p);
 120     }
 121     nasm_free(r);
 122 }
 123
 124 static const union intorptr *real_raa_read(struct real_raa *r, int32_t posn)
 125 {
 126     if ((uint32_t) posn >= (UINT32_C(1) << (r->shift + LAYERSHIFT(r))))
 127         return NULL;            /* Beyond the end */
 128     while (r->layers > 0) {
 129         int32_t l = posn >> r->shift;
 130         posn &= (UINT32_C(1) << r->shift) - 1;
 131         r = r->u.b.data[l];
 132         if (!r)
 133             return NULL;        /* Not present */
 134     }
 135     return &r->u.l.data[posn];
 136 }
 137
 138 int64_t raa_read(struct RAA *r, int32_t pos)
 139 {
 140     const union intorptr *ip;
 141
 142     ip = real_raa_read((struct real_raa *)r, pos);
 143     return ip ? ip->i : 0;
 144 }
 145
 146 void *raa_read_ptr(struct RAAPTR *r, int32_t pos)
 147 {
 148     const union intorptr *ip;
 149
 150     ip = real_raa_read((struct real_raa *)r, pos);
 151     return ip ? ip->p : NULL;
 152 }
 153
 154
 155 struct real_raa *
 156 real_raa_write(struct real_raa *r, int32_t posn, union intorptr value)
 157 {
 158     struct real_raa *result;
 159
 160     nasm_assert(posn >= 0);
 161
 162     while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) {
 163         /*
 164          * Must add a layer.
 165          */
 166         struct real_raa *s;
 167
 168         s = nasm_zalloc(BRANCHSIZ);
 169         s->layers = r->layers + 1;
 170         s->shift = LAYERSHIFT(r) + r->shift;
 171         s->u.b.data[0] = r;
 172         r = s;
 173     }
 174
 175     result = r;
 176
 177     while (r->layers > 0) {
 178         struct real_raa **s;
 179         int32_t l = posn >> r->shift;
 180         posn &= (UINT32_C(1) << r->shift) - 1;
 181         s = &r->u.b.data[l];
 182         if (!*s)
 183             *s = raa_init_layer(r->layers - 1);
 184         r = *s;
 185     }
 186
 187     r->u.l.data[posn] = value;
 188
 189     return result;
 190 }