preproc: add dummy %pragma directive
[nasm.git] / raa.c
bloba9ed830b220c603e1ac8b4e2a31a0d2d535d5c47
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.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following
9 * conditions are met:
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.
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.
32 * ----------------------------------------------------------------------- */
34 #include "nasmlib.h"
35 #include "raa.h"
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.
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)
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;
53 struct RAA {
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.
61 int layers;
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.
70 int shift;
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;
82 #define LEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
83 #define BRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
85 #define LAYERSHIFT(r) ( (r)->layers==0 ? RAA_BLKSHIFT : RAA_LAYERSHIFT )
87 static struct RAA *real_raa_init(int layers)
89 struct RAA *r;
90 int i;
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;
103 return r;
106 struct RAA *raa_init(void)
108 return real_raa_init(0);
111 void raa_free(struct RAA *r)
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);
119 nasm_free(r);
122 int64_t raa_read(struct RAA *r, int32_t posn)
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 */
133 return r->u.l.data[posn];
136 struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value)
138 struct RAA *result;
140 nasm_assert(posn >= 0);
142 while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) {
144 * Must add a layer.
146 struct RAA *s;
147 int i;
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;
158 result = r;
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;
170 r->u.l.data[posn] = value;
172 return result;