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
48typedef union RAA_UNION RAA_UNION;
49typedef struct RAA_LEAF RAA_LEAF;
50typedef struct RAA_BRANCH RAA_BRANCH;
51
52struct 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
81struct RAA {
82 struct real_raa raa;
83};
84struct 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
93static 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
108struct real_raa *real_raa_init(void)
109{
110 return raa_init_layer(0);
111}
112
113void 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
124static 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
138int64_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
146void *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
155struct real_raa *
156real_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}
191