service_runtime/dyn_array.c

   1 /*
   2  * Copyright 2008, Google Inc.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *
   9  *     * Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *     * Redistributions in binary form must reproduce the above
  12  * copyright notice, this list of conditions and the following disclaimer
  13  * in the documentation and/or other materials provided with the
  14  * distribution.
  15  *     * Neither the name of Google Inc. nor the names of its
  16  * contributors may be used to endorse or promote products derived from
  17  * this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*
  33  * Implementation of dynamic arrays.
  34  */
  35
  36 #include "native_client/include/portability.h"
  37
  38 #define DYN_ARRAY_DEBUG 1
  39
  40 #include <stdlib.h>
  41 #include <string.h>
  42
  43 #include "native_client/service_runtime/dyn_array.h"
  44
  45 #if DYN_ARRAY_DEBUG
  46 # include "native_client/service_runtime/nacl_log.h"
  47 #endif
  48
  49 static INLINE int BitsToAllocWords(int nbits)
  50 {
  51   return (nbits + kBitsPerWord - 1) >> kWordIndexShift;
  52 }
  53
  54 static INLINE int BitsToIndex(int nbits)
  55 {
  56   return nbits >> kWordIndexShift;
  57 }
  58
  59 static INLINE int BitsToOffset(int nbits)
  60 {
  61   return nbits & (kBitsPerWord - 1);
  62 }
  63
  64 int DynArrayCtor(struct DynArray  *dap,
  65                  int              initial_size)
  66 {
  67   if (initial_size <= 0) {
  68     initial_size = 32;
  69   }
  70   dap->num_entries = 0u;
  71   dap->ptr_array = calloc(initial_size, sizeof *dap->ptr_array);
  72   if (NULL == dap->ptr_array) {
  73     return 0;
  74   }
  75   dap->available = calloc(BitsToAllocWords(initial_size),
  76                           sizeof *dap->available);
  77   if (NULL == dap->available) {
  78     free(dap->ptr_array);
  79     dap->ptr_array = NULL;
  80     return 0;
  81   }
  82   dap->avail_ix = 0;  /* hint */
  83
  84   dap->ptr_array_space = initial_size;
  85   return 1;
  86 }
  87
  88 void DynArrayDtor(struct DynArray *dap)
  89 {
  90   dap->num_entries = 0;  /* assume user has freed entries */
  91   free(dap->ptr_array);
  92   dap->ptr_array = NULL;
  93   dap->ptr_array_space = 0;
  94   free(dap->available);
  95   dap->available = NULL;
  96 }
  97
  98 void *DynArrayGet(struct DynArray *dap,
  99                   int             idx)
 100 {
 101   if ((unsigned) idx < (unsigned) dap->num_entries) {
 102     return dap->ptr_array[idx];
 103   }
 104   return NULL;
 105 }
 106
 107 int DynArraySet(struct DynArray *dap,
 108                 int             idx,
 109                 void            *ptr)
 110 {
 111   int desired_space;
 112   int tmp;
 113   int ix;
 114
 115   for (desired_space = dap->ptr_array_space;
 116        idx >= desired_space;
 117        desired_space = tmp) {
 118     tmp = 2 * desired_space;
 119     if (tmp < desired_space) {
 120       return 0;
 121     }
 122   }
 123   if (desired_space != dap->ptr_array_space) {
 124     /* need to grow */
 125
 126     void      **new_space;
 127     uint32_t  *new_avail;
 128     size_t    new_avail_nwords;
 129     size_t    old_avail_nwords;
 130
 131     new_space = realloc(dap->ptr_array, desired_space * sizeof *new_space);
 132     if (NULL == new_space) {
 133       return 0;
 134     }
 135     memset((void *) (new_space + dap->ptr_array_space),
 136            0,
 137            (desired_space - dap->ptr_array_space) * sizeof *new_space);
 138     dap->ptr_array = new_space;
 139
 140     old_avail_nwords = BitsToAllocWords(dap->ptr_array_space);
 141     new_avail_nwords = BitsToAllocWords(desired_space);
 142
 143     new_avail = realloc(dap->available,
 144                         new_avail_nwords * sizeof *new_avail);
 145     if (NULL == new_avail) {
 146       return 0;
 147     }
 148     memset((void *) &new_avail[old_avail_nwords],
 149            0,
 150            (new_avail_nwords - old_avail_nwords) * sizeof *new_avail);
 151     dap->available = new_avail;
 152
 153     dap->ptr_array_space = desired_space;
 154   }
 155   dap->ptr_array[idx] = ptr;
 156   ix = BitsToIndex(idx);
 157 #if DYN_ARRAY_DEBUG
 158   NaClLog(4, "Set(%d,%p) @ix %d: 0x%08x\n", idx, ptr, ix, dap->available[ix]);
 159 #endif
 160   if (NULL != ptr) {
 161     dap->available[ix] |= (1 << BitsToOffset(idx));
 162   } else {
 163     dap->available[ix] &= ~(1 << BitsToOffset(idx));
 164     if (ix < dap->avail_ix) {
 165       dap->avail_ix = ix;
 166     }
 167   }
 168 #if DYN_ARRAY_DEBUG
 169   NaClLog(4, "After @ix %d: 0x%08x, avail_ix %d\n",
 170           ix, dap->available[ix], dap->avail_ix);
 171 #endif
 172   if (dap->num_entries <= idx) {
 173     dap->num_entries = idx + 1;
 174   }
 175   return 1;
 176 }
 177
 178 int DynArrayFirstAvail(struct DynArray *dap)
 179 {
 180   int ix;
 181   int last_ix;
 182   int avail_pos;
 183
 184   last_ix = BitsToAllocWords(dap->ptr_array_space);
 185
 186 #if DYN_ARRAY_DEBUG
 187   for (ix = 0; ix < last_ix; ++ix) {
 188     NaClLog(4, "ix %d: 0x%08x\n", ix, dap->available[ix]);
 189   }
 190 #endif
 191   for (ix = dap->avail_ix; ix < last_ix; ++ix) {
 192     if (0U != ~dap->available[ix]) {
 193 #if DYN_ARRAY_DEBUG
 194       NaClLog(4, "found first not-all-ones ix %d\n", ix);
 195 #endif
 196       dap->avail_ix = ix;
 197       break;
 198     }
 199   }
 200   if (ix < last_ix) {
 201     avail_pos = ffs(~dap->available[ix]) - 1;
 202     avail_pos += ix << kWordIndexShift;
 203   } else {
 204     avail_pos = dap->ptr_array_space;
 205   }
 206   return avail_pos;
 207 }