1 : /*
2 : * Copyright 2008 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can
4 : * be found in the LICENSE file.
5 : */
6 :
7 : /*
8 : * Implementation of dynamic arrays.
9 : */
10 :
11 : #include "native_client/src/include/portability.h"
12 :
13 : #define DYN_ARRAY_DEBUG 1
14 :
15 : #include <stdlib.h>
16 : #include <string.h>
17 :
18 : #if DYN_ARRAY_DEBUG
19 : # include "native_client/src/shared/platform/nacl_log.h"
20 : #endif
21 :
22 : #include "native_client/src/trusted/service_runtime/dyn_array.h"
23 :
24 :
25 : static int const kBitsPerWord = 32;
26 : static int const kWordIndexShift = 5; /* 2**kWordIndexShift==kBitsPerWord */
27 :
28 :
29 32319 : static INLINE size_t BitsToAllocWords(size_t nbits) {
30 32319 : return (nbits + kBitsPerWord - 1) >> kWordIndexShift;
31 : }
32 :
33 :
34 61194 : static INLINE size_t BitsToIndex(size_t nbits) {
35 61194 : return nbits >> kWordIndexShift;
36 : }
37 :
38 :
39 61194 : static INLINE size_t BitsToOffset(size_t nbits) {
40 61194 : return nbits & (kBitsPerWord - 1);
41 : }
42 :
43 :
44 902 : int DynArrayCtor(struct DynArray *dap,
45 : size_t initial_size) {
46 902 : if (initial_size == 0) {
47 279 : initial_size = 32;
48 : }
49 902 : dap->num_entries = 0u;
50 : /* calloc should check internally, but we're paranoid */
51 1804 : if (SIZE_T_MAX / sizeof *dap->ptr_array < initial_size ||
52 902 : SIZE_T_MAX/ sizeof *dap->available < BitsToAllocWords(initial_size)) {
53 : /* would integer overflow */
54 0 : return 0;
55 : }
56 902 : dap->ptr_array = calloc(initial_size, sizeof *dap->ptr_array);
57 902 : if (NULL == dap->ptr_array) {
58 0 : return 0;
59 : }
60 902 : dap->available = calloc(BitsToAllocWords(initial_size),
61 : sizeof *dap->available);
62 902 : if (NULL == dap->available) {
63 0 : free(dap->ptr_array);
64 0 : dap->ptr_array = NULL;
65 0 : return 0;
66 : }
67 902 : dap->avail_ix = 0; /* hint */
68 :
69 902 : dap->ptr_array_space = initial_size;
70 902 : return 1;
71 : }
72 :
73 :
74 268 : void DynArrayDtor(struct DynArray *dap) {
75 268 : dap->num_entries = 0; /* assume user has freed entries */
76 268 : free(dap->ptr_array);
77 268 : dap->ptr_array = NULL;
78 268 : dap->ptr_array_space = 0;
79 268 : free(dap->available);
80 268 : dap->available = NULL;
81 268 : }
82 :
83 :
84 138375 : void *DynArrayGet(struct DynArray *dap,
85 : size_t idx) {
86 138375 : if (idx < dap->num_entries) {
87 137388 : return dap->ptr_array[idx];
88 : }
89 987 : return NULL;
90 : }
91 :
92 :
93 61194 : int DynArraySet(struct DynArray *dap,
94 : size_t idx,
95 : void *ptr) {
96 : size_t desired_space;
97 : size_t tmp;
98 : size_t ix;
99 :
100 122766 : for (desired_space = dap->ptr_array_space;
101 : idx >= desired_space;
102 378 : desired_space = tmp) {
103 378 : tmp = 2 * desired_space;
104 378 : if (tmp < desired_space) {
105 0 : return 0; /* failed */
106 : }
107 : }
108 61194 : if (desired_space != dap->ptr_array_space) {
109 : /* need to grow */
110 :
111 : void **new_space;
112 : uint32_t *new_avail;
113 : size_t new_avail_nwords;
114 : size_t old_avail_nwords;
115 :
116 368 : new_space = realloc(dap->ptr_array, desired_space * sizeof *new_space);
117 368 : if (NULL == new_space) {
118 0 : return 0;
119 : }
120 368 : memset((void *) (new_space + dap->ptr_array_space),
121 : 0,
122 368 : (desired_space - dap->ptr_array_space) * sizeof *new_space);
123 368 : dap->ptr_array = new_space;
124 :
125 368 : old_avail_nwords = BitsToAllocWords(dap->ptr_array_space);
126 368 : new_avail_nwords = BitsToAllocWords(desired_space);
127 :
128 368 : new_avail = realloc(dap->available,
129 : new_avail_nwords * sizeof *new_avail);
130 368 : if (NULL == new_avail) {
131 0 : return 0;
132 : }
133 368 : memset((void *) &new_avail[old_avail_nwords],
134 : 0,
135 368 : (new_avail_nwords - old_avail_nwords) * sizeof *new_avail);
136 368 : dap->available = new_avail;
137 :
138 368 : dap->ptr_array_space = desired_space;
139 : }
140 61194 : dap->ptr_array[idx] = ptr;
141 61194 : ix = BitsToIndex(idx);
142 : #if DYN_ARRAY_DEBUG
143 61194 : NaClLog(4, "Set(%"NACL_PRIuS",%p) @ix %"NACL_PRIuS": 0x%08x\n",
144 61194 : idx, ptr, ix, dap->available[ix]);
145 : #endif
146 61194 : if (NULL != ptr) {
147 30874 : dap->available[ix] |= (1 << BitsToOffset(idx));
148 : } else {
149 30320 : dap->available[ix] &= ~(1 << BitsToOffset(idx));
150 30320 : if (ix < dap->avail_ix) {
151 5 : dap->avail_ix = ix;
152 : }
153 : }
154 : #if DYN_ARRAY_DEBUG
155 122388 : NaClLog(4, "After @ix %"NACL_PRIuS": 0x%08x, avail_ix %"NACL_PRIuS"\n",
156 61194 : ix, dap->available[ix], dap->avail_ix);
157 : #endif
158 61194 : if (dap->num_entries <= idx) {
159 10161 : dap->num_entries = idx + 1;
160 : }
161 61194 : return 1;
162 : }
163 :
164 :
165 29779 : size_t DynArrayFirstAvail(struct DynArray *dap) {
166 : size_t ix;
167 : size_t last_ix;
168 : size_t avail_pos;
169 :
170 29779 : last_ix = BitsToAllocWords(dap->ptr_array_space);
171 :
172 : #if DYN_ARRAY_DEBUG
173 1447100 : for (ix = 0; ix < last_ix; ++ix) {
174 1417321 : NaClLog(4, "ix %"NACL_PRIuS": 0x%08x\n", ix, dap->available[ix]);
175 : }
176 : #endif
177 30055 : for (ix = dap->avail_ix; ix < last_ix; ++ix) {
178 30044 : if (0U != ~dap->available[ix]) {
179 : #if DYN_ARRAY_DEBUG
180 29768 : NaClLog(4, "found first not-all-ones ix %"NACL_PRIuS"\n", ix);
181 : #endif
182 29768 : dap->avail_ix = ix;
183 29768 : break;
184 : }
185 : }
186 29779 : if (ix < last_ix) {
187 29768 : avail_pos = ffs(~dap->available[ix]) - 1;
188 29768 : avail_pos += ix << kWordIndexShift;
189 : } else {
190 11 : avail_pos = dap->ptr_array_space;
191 : }
192 29779 : return avail_pos;
193 : }
|
