1309260Scognet/* 2309260Scognet * Copyright 2013-2015 Samy Al Bahra 3309260Scognet * Copyright 2013-2014 AppNexus, Inc. 4309260Scognet * All rights reserved. 5309260Scognet * 6309260Scognet * Redistribution and use in source and binary forms, with or without 7309260Scognet * modification, are permitted provided that the following conditions 8309260Scognet * are met: 9309260Scognet * 1. Redistributions of source code must retain the above copyright 10309260Scognet * notice, this list of conditions and the following disclaimer. 11309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 12309260Scognet * notice, this list of conditions and the following disclaimer in the 13309260Scognet * documentation and/or other materials provided with the distribution. 14309260Scognet * 15309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25309260Scognet * SUCH DAMAGE. 26309260Scognet */ 27309260Scognet 28309260Scognet#include <ck_array.h> 29309260Scognet#include <ck_cc.h> 30309260Scognet#include <ck_pr.h> 31309260Scognet#include <ck_stdbool.h> 32309260Scognet#include <ck_string.h> 33309260Scognet 34309260Scognetstatic struct _ck_array * 35309260Scognetck_array_create(struct ck_malloc *allocator, unsigned int length) 36309260Scognet{ 37309260Scognet struct _ck_array *active; 38309260Scognet 39309260Scognet active = allocator->malloc(sizeof(struct _ck_array) + sizeof(void *) * length); 40309260Scognet if (active == NULL) 41309260Scognet return NULL; 42309260Scognet 43309260Scognet active->n_committed = 0; 44309260Scognet active->length = length; 45309260Scognet 46309260Scognet return active; 47309260Scognet} 48309260Scognet 49309260Scognetbool 50309260Scognetck_array_init(struct ck_array *array, unsigned int mode, struct ck_malloc *allocator, unsigned int length) 51309260Scognet{ 52309260Scognet struct _ck_array *active; 53309260Scognet 54309260Scognet (void)mode; 55309260Scognet 56309260Scognet if (allocator->realloc == NULL || 57309260Scognet allocator->malloc == NULL || 58309260Scognet allocator->free == NULL || 59309260Scognet length == 0) 60309260Scognet return false; 61309260Scognet 62309260Scognet active = ck_array_create(allocator, length); 63309260Scognet if (active == NULL) 64309260Scognet return false; 65309260Scognet 66309260Scognet array->n_entries = 0; 67309260Scognet array->allocator = allocator; 68309260Scognet array->active = active; 69309260Scognet array->transaction = NULL; 70309260Scognet return true; 71309260Scognet} 72309260Scognet 73309260Scognetbool 74309260Scognetck_array_put(struct ck_array *array, void *value) 75309260Scognet{ 76309260Scognet struct _ck_array *target; 77309260Scognet unsigned int size; 78309260Scognet 79309260Scognet /* 80309260Scognet * If no transaction copy has been necessary, attempt to do in-place 81309260Scognet * modification of the array. 82309260Scognet */ 83309260Scognet if (array->transaction == NULL) { 84309260Scognet target = array->active; 85309260Scognet 86309260Scognet if (array->n_entries == target->length) { 87309260Scognet size = target->length << 1; 88309260Scognet 89309260Scognet target = array->allocator->realloc(target, 90309260Scognet sizeof(struct _ck_array) + sizeof(void *) * array->n_entries, 91309260Scognet sizeof(struct _ck_array) + sizeof(void *) * size, 92309260Scognet true); 93309260Scognet 94309260Scognet if (target == NULL) 95309260Scognet return false; 96309260Scognet 97309260Scognet ck_pr_store_uint(&target->length, size); 98309260Scognet 99309260Scognet /* Serialize with respect to contents. */ 100309260Scognet ck_pr_fence_store(); 101309260Scognet ck_pr_store_ptr(&array->active, target); 102309260Scognet } 103309260Scognet 104309260Scognet target->values[array->n_entries++] = value; 105309260Scognet return true; 106309260Scognet } 107309260Scognet 108309260Scognet target = array->transaction; 109309260Scognet if (array->n_entries == target->length) { 110309260Scognet size = target->length << 1; 111309260Scognet 112309260Scognet target = array->allocator->realloc(target, 113309260Scognet sizeof(struct _ck_array) + sizeof(void *) * array->n_entries, 114309260Scognet sizeof(struct _ck_array) + sizeof(void *) * size, 115309260Scognet true); 116309260Scognet 117309260Scognet if (target == NULL) 118309260Scognet return false; 119309260Scognet 120309260Scognet target->length = size; 121309260Scognet array->transaction = target; 122309260Scognet } 123309260Scognet 124309260Scognet target->values[array->n_entries++] = value; 125309260Scognet return false; 126309260Scognet} 127309260Scognet 128309260Scognetint 129309260Scognetck_array_put_unique(struct ck_array *array, void *value) 130309260Scognet{ 131309260Scognet unsigned int i, limit; 132309260Scognet void **v; 133309260Scognet 134309260Scognet limit = array->n_entries; 135309260Scognet if (array->transaction != NULL) { 136309260Scognet v = array->transaction->values; 137309260Scognet } else { 138309260Scognet v = array->active->values; 139309260Scognet } 140309260Scognet 141309260Scognet for (i = 0; i < limit; i++) { 142309260Scognet if (v[i] == value) 143309260Scognet return 1; 144309260Scognet } 145309260Scognet 146309260Scognet return -!ck_array_put(array, value); 147309260Scognet} 148309260Scognet 149309260Scognetbool 150309260Scognetck_array_remove(struct ck_array *array, void *value) 151309260Scognet{ 152309260Scognet struct _ck_array *target; 153309260Scognet unsigned int i; 154309260Scognet 155309260Scognet if (array->transaction != NULL) { 156309260Scognet target = array->transaction; 157309260Scognet 158309260Scognet for (i = 0; i < array->n_entries; i++) { 159309260Scognet if (target->values[i] == value) { 160309260Scognet target->values[i] = target->values[--array->n_entries]; 161309260Scognet return true; 162309260Scognet } 163309260Scognet } 164309260Scognet 165309260Scognet return false; 166309260Scognet } 167309260Scognet 168309260Scognet target = array->active; 169309260Scognet 170309260Scognet for (i = 0; i < array->n_entries; i++) { 171309260Scognet if (target->values[i] == value) 172309260Scognet break; 173309260Scognet } 174309260Scognet 175309260Scognet if (i == array->n_entries) 176309260Scognet return false; 177309260Scognet 178309260Scognet /* If there are pending additions, immediately eliminate the operation. */ 179309260Scognet if (target->n_committed != array->n_entries) { 180309260Scognet ck_pr_store_ptr(&target->values[i], target->values[--array->n_entries]); 181309260Scognet return true; 182309260Scognet } 183309260Scognet 184309260Scognet /* 185309260Scognet * The assumption is that these allocations are small to begin with. 186309260Scognet * If there is no immediate opportunity for transaction, allocate a 187309260Scognet * transactional array which will be applied upon commit time. 188309260Scognet */ 189309260Scognet target = ck_array_create(array->allocator, array->n_entries); 190309260Scognet if (target == NULL) 191309260Scognet return false; 192309260Scognet 193309260Scognet memcpy(target->values, array->active->values, sizeof(void *) * array->n_entries); 194309260Scognet target->length = array->n_entries; 195309260Scognet target->n_committed = array->n_entries; 196309260Scognet target->values[i] = target->values[--array->n_entries]; 197309260Scognet 198309260Scognet array->transaction = target; 199309260Scognet return true; 200309260Scognet} 201309260Scognet 202309260Scognetbool 203309260Scognetck_array_commit(ck_array_t *array) 204309260Scognet{ 205309260Scognet struct _ck_array *m = array->transaction; 206309260Scognet 207309260Scognet if (m != NULL) { 208309260Scognet struct _ck_array *p; 209309260Scognet 210309260Scognet m->n_committed = array->n_entries; 211309260Scognet ck_pr_fence_store(); 212309260Scognet p = array->active; 213309260Scognet ck_pr_store_ptr(&array->active, m); 214309260Scognet array->allocator->free(p, sizeof(struct _ck_array) + 215309260Scognet p->length * sizeof(void *), true); 216309260Scognet array->transaction = NULL; 217309260Scognet 218309260Scognet return true; 219309260Scognet } 220309260Scognet 221309260Scognet ck_pr_fence_store(); 222309260Scognet ck_pr_store_uint(&array->active->n_committed, array->n_entries); 223309260Scognet return true; 224309260Scognet} 225309260Scognet 226309260Scognetvoid 227309260Scognetck_array_deinit(struct ck_array *array, bool defer) 228309260Scognet{ 229309260Scognet 230309260Scognet array->allocator->free(array->active, 231309260Scognet sizeof(struct _ck_array) + sizeof(void *) * array->active->length, defer); 232309260Scognet 233309260Scognet if (array->transaction != NULL) { 234309260Scognet array->allocator->free(array->transaction, 235309260Scognet sizeof(struct _ck_array) + sizeof(void *) * array->transaction->length, defer); 236309260Scognet } 237309260Scognet 238309260Scognet array->transaction = array->active = NULL; 239309260Scognet return; 240309260Scognet} 241