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