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