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 #define LEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
  38 #define BRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
  39
  40 #define LAYERSHIFT(r) ( (r)->layers==0 ? RAA_BLKSHIFT : RAA_LAYERSHIFT )
  41
  42 static struct RAA *real_raa_init(int layers)
  43 {
  44     struct RAA *r;
  45     int i;
  46
  47     if (layers == 0) {
  48         r = nasm_zalloc(LEAFSIZ);
  49         r->shift = 0;
  50     } else {
  51         r = nasm_malloc(BRANCHSIZ);
  52         r->layers = layers;
  53         for (i = 0; i < RAA_LAYERSIZE; i++)
  54             r->u.b.data[i] = NULL;
  55         r->shift =
  56             (RAA_BLKSHIFT - RAA_LAYERSHIFT) + layers * RAA_LAYERSHIFT;
  57     }
  58     return r;
  59 }
  60
  61 struct RAA *raa_init(void)
  62 {
  63     return real_raa_init(0);
  64 }
  65
  66 void raa_free(struct RAA *r)
  67 {
  68     if (r->layers) {
  69         struct RAA **p;
  70         for (p = r->u.b.data; p - r->u.b.data < RAA_LAYERSIZE; p++)
  71             if (*p)
  72                 raa_free(*p);
  73     }
  74     nasm_free(r);
  75 }
  76
  77 int64_t raa_read(struct RAA *r, int32_t posn)
  78 {
  79     if ((uint32_t) posn >= (UINT32_C(1) << (r->shift + LAYERSHIFT(r))))
  80         return 0;               /* Return 0 for undefined entries */
  81     while (r->layers > 0) {
  82         int32_t l = posn >> r->shift;
  83         posn &= (UINT32_C(1) << r->shift) - 1;
  84         r = r->u.b.data[l];
  85         if (!r)
  86             return 0;           /* Return 0 for undefined entries */
  87     }
  88     return r->u.l.data[posn];
  89 }
  90
  91 struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value)
  92 {
  93     struct RAA *result;
  94
  95     if (posn < 0)
  96         nasm_malloc_error(ERR_PANIC, "negative position in raa_write");
  97
  98     while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) {
  99         /*
 100          * Must add a layer.
 101          */
 102         struct RAA *s;
 103         int i;
 104
 105         s = nasm_malloc(BRANCHSIZ);
 106         for (i = 0; i < RAA_LAYERSIZE; i++)
 107             s->u.b.data[i] = NULL;
 108         s->layers = r->layers + 1;
 109         s->shift = LAYERSHIFT(r) + r->shift;
 110         s->u.b.data[0] = r;
 111         r = s;
 112     }
 113
 114     result = r;
 115
 116     while (r->layers > 0) {
 117         struct RAA **s;
 118         int32_t l = posn >> r->shift;
 119         posn &= (UINT32_C(1) << r->shift) - 1;
 120         s = &r->u.b.data[l];
 121         if (!*s)
 122             *s = real_raa_init(r->layers - 1);
 123         r = *s;
 124     }
 125
 126     r->u.l.data[posn] = value;
 127
 128     return result;
 129 }