ck_array.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    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 }

Cache object: 4e26345b2af5652caf805ffb99958280

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/contrib/ck/src/ck_array.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/ck/src/ck_array.c