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     nasm_assert(posn >= 0);
  96
  97     while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) {
  98         /*
  99          * Must add a layer.
 100          */
 101         struct RAA *s;
 102         int i;
 103
 104         s = nasm_malloc(BRANCHSIZ);
 105         for (i = 0; i < RAA_LAYERSIZE; i++)
 106             s->u.b.data[i] = NULL;
 107         s->layers = r->layers + 1;
 108         s->shift = LAYERSHIFT(r) + r->shift;
 109         s->u.b.data[0] = r;
 110         r = s;
 111     }
 112
 113     result = r;
 114
 115     while (r->layers > 0) {
 116         struct RAA **s;
 117         int32_t l = posn >> r->shift;
 118         posn &= (UINT32_C(1) << r->shift) - 1;
 119         s = &r->u.b.data[l];
 120         if (!*s)
 121             *s = real_raa_init(r->layers - 1);
 122         r = *s;
 123     }
 124
 125     r->u.l.data[posn] = value;
 126
 127     return result;
 128 }