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