1 /* 2 * Copyright 2013-2015 Samy Al Bahra 3 * Copyright 2013-2014 AppNexus, Inc. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 28 #include <ck_array.h> 29 #include <ck_cc.h> 30 #include <ck_pr.h> 31 #include <ck_stdbool.h> 32 #include <ck_string.h> 33 34 static struct _ck_array * 35 ck_array_create(struct ck_malloc *allocator, unsigned int length) 36 { 37 struct _ck_array *active; 38 39 active = allocator->malloc(sizeof(struct _ck_array) + sizeof(void *) * length); 40 if (active == NULL) 41 return NULL; 42 43 active->n_committed = 0; 44 active->length = length; 45 46 return active; 47 } 48 49 bool 50 ck_array_init(struct ck_array *array, unsigned int mode, struct ck_malloc *allocator, unsigned int length) 51 { 52 struct _ck_array *active; 53 54 (void)mode; 55 56 if (allocator->realloc == NULL || 57 allocator->malloc == NULL || 58 allocator->free == NULL || 59 length == 0) 60 return false; 61 62 active = ck_array_create(allocator, length); 63 if (active == NULL) 64 return false; 65 66 array->n_entries = 0; 67 array->allocator = allocator; 68 array->active = active; 69 array->transaction = NULL; 70 return true; 71 } 72 73 bool 74 ck_array_put(struct ck_array *array, void *value) 75 { 76 struct _ck_array *target; 77 unsigned int size; 78 79 /* 80 * If no transaction copy has been necessary, attempt to do in-place 81 * modification of the array. 82 */ 83 if (array->transaction == NULL) { 84 target = array->active; 85 86 if (array->n_entries == target->length) { 87 size = target->length << 1; 88 89 target = array->allocator->realloc(target, 90 sizeof(struct _ck_array) + sizeof(void *) * array->n_entries, 91 sizeof(struct _ck_array) + sizeof(void *) * size, 92 true); 93 94 if (target == NULL) 95 return false; 96 97 ck_pr_store_uint(&target->length, size); 98 99 /* Serialize with respect to contents. */ 100 ck_pr_fence_store(); 101 ck_pr_store_ptr(&array->active, target); 102 } 103 104 target->values[array->n_entries++] = value; 105 return true; 106 } 107 108 target = array->transaction; 109 if (array->n_entries == target->length) { 110 size = target->length << 1; 111 112 target = array->allocator->realloc(target, 113 sizeof(struct _ck_array) + sizeof(void *) * array->n_entries, 114 sizeof(struct _ck_array) + sizeof(void *) * size, 115 true); 116 117 if (target == NULL) 118 return false; 119 120 target->length = size; 121 array->transaction = target; 122 } 123 124 target->values[array->n_entries++] = value; 125 return false; 126 } 127 128 int 129 ck_array_put_unique(struct ck_array *array, void *value) 130 { 131 unsigned int i, limit; 132 void **v; 133 134 limit = array->n_entries; 135 if (array->transaction != NULL) { 136 v = array->transaction->values; 137 } else { 138 v = array->active->values; 139 } 140 141 for (i = 0; i < limit; i++) { 142 if (v[i] == value) 143 return 1; 144 } 145 146 return -!ck_array_put(array, value); 147 } 148 149 bool 150 ck_array_remove(struct ck_array *array, void *value) 151 { 152 struct _ck_array *target; 153 unsigned int i; 154 155 if (array->transaction != NULL) { 156 target = array->transaction; 157 158 for (i = 0; i < array->n_entries; i++) { 159 if (target->values[i] == value) { 160 target->values[i] = target->values[--array->n_entries]; 161 return true; 162 } 163 } 164 165 return false; 166 } 167 168 target = array->active; 169 170 for (i = 0; i < array->n_entries; i++) { 171 if (target->values[i] == value) 172 break; 173 } 174 175 if (i == array->n_entries) 176 return false; 177 178 /* If there are pending additions, immediately eliminate the operation. */ 179 if (target->n_committed != array->n_entries) { 180 ck_pr_store_ptr(&target->values[i], target->values[--array->n_entries]); 181 return true; 182 } 183 184 /* 185 * The assumption is that these allocations are small to begin with. 186 * If there is no immediate opportunity for transaction, allocate a 187 * transactional array which will be applied upon commit time. 188 */ 189 target = ck_array_create(array->allocator, array->n_entries); 190 if (target == NULL) 191 return false; 192 193 memcpy(target->values, array->active->values, sizeof(void *) * array->n_entries); 194 target->length = array->n_entries; 195 target->n_committed = array->n_entries; 196 target->values[i] = target->values[--array->n_entries]; 197 198 array->transaction = target; 199 return true; 200 } 201 202 bool 203 ck_array_commit(ck_array_t *array) 204 { 205 struct _ck_array *m = array->transaction; 206 207 if (m != NULL) { 208 struct _ck_array *p; 209 210 m->n_committed = array->n_entries; 211 ck_pr_fence_store(); 212 p = array->active; 213 ck_pr_store_ptr(&array->active, m); 214 array->allocator->free(p, sizeof(struct _ck_array) + 215 p->length * sizeof(void *), true); 216 array->transaction = NULL; 217 218 return true; 219 } 220 221 ck_pr_fence_store(); 222 ck_pr_store_uint(&array->active->n_committed, array->n_entries); 223 return true; 224 } 225 226 void 227 ck_array_deinit(struct ck_array *array, bool defer) 228 { 229 230 array->allocator->free(array->active, 231 sizeof(struct _ck_array) + sizeof(void *) * array->active->length, defer); 232 233 if (array->transaction != NULL) { 234 array->allocator->free(array->transaction, 235 sizeof(struct _ck_array) + sizeof(void *) * array->transaction->length, defer); 236 } 237 238 array->transaction = array->active = NULL; 239 return; 240 } 241