nasmlib/raa.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2009 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 struct RAA RAA;
  49 typedef union RAA_UNION RAA_UNION;
  50 typedef struct RAA_LEAF RAA_LEAF;
  51 typedef struct RAA_BRANCH RAA_BRANCH;
  52
  53 struct RAA {
  54     /*
  55      * Number of layers below this one to get to the real data. 0
  56      * means this structure is a leaf, holding RAA_BLKSIZE real
  57      * data items; 1 and above mean it's a branch, holding
  58      * RAA_LAYERSIZE pointers to the next level branch or leaf
  59      * structures.
  60      */
  61     int layers;
  62
  63     /*
  64      * Number of real data items spanned by one position in the
  65      * `data' array at this level. This number is 0 trivially, for
  66      * a leaf (level 0): for a level 1 branch it should be
  67      * RAA_BLKSHIFT, and for a level 2 branch it's
  68      * RAA_LAYERSHIFT+RAA_BLKSHIFT.
  69      */
  70     int shift;
  71
  72     union RAA_UNION {
  73         struct RAA_LEAF {
  74             int64_t data[RAA_BLKSIZE];
  75         } l;
  76         struct RAA_BRANCH {
  77             struct RAA *data[RAA_LAYERSIZE];
  78         } b;
  79     } u;
  80 };
  81
  82 #define LEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
  83 #define BRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
  84
  85 #define LAYERSHIFT(r) ( (r)->layers==0 ? RAA_BLKSHIFT : RAA_LAYERSHIFT )
  86
  87 static struct RAA *real_raa_init(int layers)
  88 {
  89     struct RAA *r;
  90     int i;
  91
  92     if (layers == 0) {
  93         r = nasm_zalloc(LEAFSIZ);
  94         r->shift = 0;
  95     } else {
  96         r = nasm_malloc(BRANCHSIZ);
  97         r->layers = layers;
  98         for (i = 0; i < RAA_LAYERSIZE; i++)
  99             r->u.b.data[i] = NULL;
 100         r->shift =
 101             (RAA_BLKSHIFT - RAA_LAYERSHIFT) + layers * RAA_LAYERSHIFT;
 102     }
 103     return r;
 104 }
 105
 106 struct RAA *raa_init(void)
 107 {
 108     return real_raa_init(0);
 109 }
 110
 111 void raa_free(struct RAA *r)
 112 {
 113     if (r->layers) {
 114         struct RAA **p;
 115         for (p = r->u.b.data; p - r->u.b.data < RAA_LAYERSIZE; p++)
 116             if (*p)
 117                 raa_free(*p);
 118     }
 119     nasm_free(r);
 120 }
 121
 122 int64_t raa_read(struct RAA *r, int32_t posn)
 123 {
 124     if ((uint32_t) posn >= (UINT32_C(1) << (r->shift + LAYERSHIFT(r))))
 125         return 0;               /* Return 0 for undefined entries */
 126     while (r->layers > 0) {
 127         int32_t l = posn >> r->shift;
 128         posn &= (UINT32_C(1) << r->shift) - 1;
 129         r = r->u.b.data[l];
 130         if (!r)
 131             return 0;           /* Return 0 for undefined entries */
 132     }
 133     return r->u.l.data[posn];
 134 }
 135
 136 struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value)
 137 {
 138     struct RAA *result;
 139
 140     nasm_assert(posn >= 0);
 141
 142     while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) {
 143         /*
 144          * Must add a layer.
 145          */
 146         struct RAA *s;
 147         int i;
 148
 149         s = nasm_malloc(BRANCHSIZ);
 150         for (i = 0; i < RAA_LAYERSIZE; i++)
 151             s->u.b.data[i] = NULL;
 152         s->layers = r->layers + 1;
 153         s->shift = LAYERSHIFT(r) + r->shift;
 154         s->u.b.data[0] = r;
 155         r = s;
 156     }
 157
 158     result = r;
 159
 160     while (r->layers > 0) {
 161         struct RAA **s;
 162         int32_t l = posn >> r->shift;
 163         posn &= (UINT32_C(1) << r->shift) - 1;
 164         s = &r->u.b.data[l];
 165         if (!*s)
 166             *s = real_raa_init(r->layers - 1);
 167         r = *s;
 168     }
 169
 170     r->u.l.data[posn] = value;
 171
 172     return result;
 173 }