|
10554
|
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 /*
|
|
|
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 struct RAA RAA;
|
|
|
49 typedef union RAA_UNION RAA_UNION;
|
|
|
50 typedef struct RAA_LEAF RAA_LEAF;
|
|
|
51 typedef struct RAA_BRANCH RAA_BRANCH;
|
|
|
52
|
|
|
53 struct RAA {
|
|
|
54 /*
|
|
|
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.
|
|
|
60 */
|
|
|
61 int layers;
|
|
|
62
|
|
|
63 /*
|
|
|
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.
|
|
|
69 */
|
|
|
70 int shift;
|
|
|
71
|
|
|
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;
|
|
|
80 };
|
|
|
81
|
|
|
82 #define LEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
|
|
|
83 #define BRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))
|
|
|
84
|
|
|
85 #define LAYERSHIFT(r) ( (r)->layers==0 ? RAA_BLKSHIFT : RAA_LAYERSHIFT )
|
|
|
86
|
|
|
87 static struct RAA *real_raa_init(int layers)
|
|
|
88 {
|
|
|
89 struct RAA *r;
|
|
|
90 int i;
|
|
|
91
|
|
|
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;
|
|
|
102 }
|
|
|
103 return r;
|
|
|
104 }
|
|
|
105
|
|
|
106 struct RAA *raa_init(void)
|
|
|
107 {
|
|
|
108 return real_raa_init(0);
|
|
|
109 }
|
|
|
110
|
|
|
111 void raa_free(struct RAA *r)
|
|
|
112 {
|
|
|
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);
|
|
|
118 }
|
|
|
119 nasm_free(r);
|
|
|
120 }
|
|
|
121
|
|
|
122 int64_t raa_read(struct RAA *r, int32_t posn)
|
|
|
123 {
|
|
|
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 */
|
|
|
132 }
|
|
|
133 return r->u.l.data[posn];
|
|
|
134 }
|
|
|
135
|
|
|
136 struct RAA *raa_write(struct RAA *r, int32_t posn, int64_t value)
|
|
|
137 {
|
|
|
138 struct RAA *result;
|
|
|
139
|
|
|
140 nasm_assert(posn >= 0);
|
|
|
141
|
|
|
142 while ((UINT32_C(1) << (r->shift + LAYERSHIFT(r))) <= (uint32_t) posn) {
|
|
|
143 /*
|
|
|
144 * Must add a layer.
|
|
|
145 */
|
|
|
146 struct RAA *s;
|
|
|
147 int i;
|
|
|
148
|
|
|
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;
|
|
|
156 }
|
|
|
157
|
|
|
158 result = r;
|
|
|
159
|
|
|
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;
|
|
|
168 }
|
|
|
169
|
|
|
170 r->u.l.data[posn] = value;
|
|
|
171
|
|
|
172 return result;
|
|
|
173 }
|
