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 23667 : static INLINE size_t BitsToAllocWords(size_t nbits) {
30 23667 : return (nbits + kBitsPerWord - 1) >> kWordIndexShift;
31 : }
32 :
33 :
34 42853 : static INLINE size_t BitsToIndex(size_t nbits) {
35 42853 : return nbits >> kWordIndexShift;
36 : }
37 :
38 :
39 42853 : static INLINE size_t BitsToOffset(size_t nbits) {
40 42853 : return nbits & (kBitsPerWord - 1);
41 : }
42 :
43 :
44 854 : int DynArrayCtor(struct DynArray *dap,
45 854 : size_t initial_size) {
46 854 : if (initial_size == 0) {
47 261 : initial_size = 32;
48 261 : }
49 854 : dap->num_entries = 0u;
50 : /* calloc should check internally, but we're paranoid */
51 854 : if (SIZE_T_MAX / sizeof *dap->ptr_array < initial_size ||
52 854 : SIZE_T_MAX/ sizeof *dap->available < BitsToAllocWords(initial_size)) {
53 : /* would integer overflow */
54 0 : return 0;
55 : }
56 854 : dap->ptr_array = calloc(initial_size, sizeof *dap->ptr_array);
57 854 : if (NULL == dap->ptr_array) {
58 0 : return 0;
59 : }
60 854 : dap->available = calloc(BitsToAllocWords(initial_size),
61 : sizeof *dap->available);
62 854 : if (NULL == dap->available) {
63 0 : free(dap->ptr_array);
64 0 : dap->ptr_array = NULL;
65 0 : return 0;
66 : }
67 854 : dap->avail_ix = 0; /* hint */
68 :
69 854 : dap->ptr_array_space = initial_size;
70 854 : return 1;
71 854 : }
72 :
73 :
74 254 : void DynArrayDtor(struct DynArray *dap) {
75 254 : dap->num_entries = 0; /* assume user has freed entries */
76 254 : free(dap->ptr_array);
77 254 : dap->ptr_array = NULL;
78 254 : dap->ptr_array_space = 0;
79 254 : free(dap->available);
80 254 : dap->available = NULL;
81 254 : }
82 :
83 :
84 129005 : void *DynArrayGet(struct DynArray *dap,
85 129005 : size_t idx) {
86 129005 : if (idx < dap->num_entries) {
87 128073 : return dap->ptr_array[idx];
88 : }
89 932 : return NULL;
90 129004 : }
91 :
92 :
93 42853 : int DynArraySet(struct DynArray *dap,
94 42853 : size_t idx,
95 42853 : void *ptr) {
96 42853 : size_t desired_space;
97 42853 : size_t tmp;
98 42853 : size_t ix;
99 :
100 86073 : for (desired_space = dap->ptr_array_space;
101 : idx >= desired_space;
102 367 : desired_space = tmp) {
103 367 : tmp = 2 * desired_space;
104 367 : if (tmp < desired_space) {
105 0 : return 0; /* failed */
106 : }
107 367 : }
108 42853 : if (desired_space != dap->ptr_array_space) {
109 : /* need to grow */
110 :
111 357 : void **new_space;
112 357 : uint32_t *new_avail;
113 357 : size_t new_avail_nwords;
114 357 : size_t old_avail_nwords;
115 :
116 357 : new_space = realloc(dap->ptr_array, desired_space * sizeof *new_space);
117 357 : if (NULL == new_space) {
118 0 : return 0;
119 : }
120 1071 : memset((void *) (new_space + dap->ptr_array_space),
121 : 0,
122 : (desired_space - dap->ptr_array_space) * sizeof *new_space);
123 357 : dap->ptr_array = new_space;
124 :
125 357 : old_avail_nwords = BitsToAllocWords(dap->ptr_array_space);
126 357 : new_avail_nwords = BitsToAllocWords(desired_space);
127 :
128 357 : new_avail = realloc(dap->available,
129 : new_avail_nwords * sizeof *new_avail);
130 357 : if (NULL == new_avail) {
131 0 : return 0;
132 : }
133 1071 : memset((void *) &new_avail[old_avail_nwords],
134 : 0,
135 : (new_avail_nwords - old_avail_nwords) * sizeof *new_avail);
136 357 : dap->available = new_avail;
137 :
138 357 : dap->ptr_array_space = desired_space;
139 357 : }
140 42853 : dap->ptr_array[idx] = ptr;
141 42853 : ix = BitsToIndex(idx);
142 : #if DYN_ARRAY_DEBUG
143 42853 : NaClLog(4, "Set(%"NACL_PRIuS",%p) @ix %"NACL_PRIuS": 0x%08x\n",
144 : idx, ptr, ix, dap->available[ix]);
145 : #endif
146 42853 : if (NULL != ptr) {
147 22278 : dap->available[ix] |= (1 << BitsToOffset(idx));
148 22278 : } else {
149 20575 : dap->available[ix] &= ~(1 << BitsToOffset(idx));
150 20575 : if (ix < dap->avail_ix) {
151 10 : dap->avail_ix = ix;
152 10 : }
153 : }
154 : #if DYN_ARRAY_DEBUG
155 42853 : NaClLog(4, "After @ix %"NACL_PRIuS": 0x%08x, avail_ix %"NACL_PRIuS"\n",
156 : ix, dap->available[ix], dap->avail_ix);
157 : #endif
158 42853 : if (dap->num_entries <= idx) {
159 4798 : dap->num_entries = idx + 1;
160 4798 : }
161 42853 : return 1;
162 42853 : }
163 :
164 :
165 21245 : size_t DynArrayFirstAvail(struct DynArray *dap) {
166 21245 : size_t ix;
167 21245 : size_t last_ix;
168 21245 : size_t avail_pos;
169 :
170 21245 : last_ix = BitsToAllocWords(dap->ptr_array_space);
171 :
172 : #if DYN_ARRAY_DEBUG
173 292894 : for (ix = 0; ix < last_ix; ++ix) {
174 125202 : NaClLog(4, "ix %"NACL_PRIuS": 0x%08x\n", ix, dap->available[ix]);
175 125202 : }
176 : #endif
177 42730 : for (ix = dap->avail_ix; ix < last_ix; ++ix) {
178 21352 : if (0U != ~dap->available[ix]) {
179 : #if DYN_ARRAY_DEBUG
180 21232 : NaClLog(4, "found first not-all-ones ix %"NACL_PRIuS"\n", ix);
181 : #endif
182 21232 : dap->avail_ix = ix;
183 21232 : break;
184 : }
185 120 : }
186 21245 : if (ix < last_ix) {
187 21232 : avail_pos = ffs(~dap->available[ix]) - 1;
188 21232 : avail_pos += ix << kWordIndexShift;
189 21232 : } else {
190 13 : avail_pos = dap->ptr_array_space;
191 : }
192 21245 : return avail_pos;
193 : }
|
