service_runtime/dyn_array.h

   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 /* @file
  34  *
  35  * NaCl utility for a dynamically sized array where the first unused
  36  * position can be discovered quickly.  This is used for I/O
  37  * descriptors -- the number of elements in an array is typically not
  38  * large, and the common access is finding an entry by its index, with
  39  * occasional need to allocate the last numbered slot for a new I/O
  40  * descriptor.
  41  *
  42  * A dynamic array containing void pointers is created using
  43  * DynArrayCtor in a placement-new manner with the initial size as
  44  * paramter.  The caller is responsible for the memory.  The dynamic
  45  * array is destroyed with DynArrayDtor, which destroys the contents
  46  * of the dynamic array; again, the caller is responsible for
  47  * destroying the DynArray object itself.  Since the array contains
  48  * void pointers, if these pointers should be in turn freed or have
  49  * destructors invoked on them, it is the responsible of the user to
  50  * do so.
  51  *
  52  * Accessors DynArrayGet and DynArraySet does what you would expect.
  53  * DynArrayFirstAvail returns the index of the first slot that is
  54  * unused.  Note that DynArraySet will grow the array as needed to set
  55  * the element, even if the value is a NULL pointer.  Such an entry is
  56  * still considerd to be unused.
  57  */
  58
  59 #ifndef SERVICE_RUNTIME_DYN_ARRAY_H__
  60 #define SERVICE_RUNTIME_DYN_ARRAY_H__ 1
  61
  62 #include "native_client/include/portability.h"
  63
  64 static int const kBitsPerWord = 32;
  65 static int const kWordIndexShift = 5;  /* 2**kWordIndexShift==kBitsPerWord */
  66
  67 struct DynArray {
  68   /* public */
  69   int       num_entries;
  70   /*
  71    * note num_entries has a somewhat unusual property.  if valid
  72    * entries are written to index 10, the num_entries is 11 even if
  73    * there have never been any writes to indices 0...9.
  74    */
  75
  76   /* protected */
  77   void      **ptr_array;  /* we *could* sort/bsearch this */
  78   int       ptr_array_space;
  79   uint32_t  *available;
  80   int       avail_ix;
  81 };
  82
  83 int DynArrayCtor(struct DynArray  *dap,
  84                  int              initial_size);
  85
  86 void DynArrayDtor(struct DynArray *dap);
  87
  88 void *DynArrayGet(struct DynArray *dap,
  89                   int             idx);
  90
  91 int DynArraySet(struct DynArray *dap,
  92                 int             idx,
  93                 void            *ptr);
  94
  95 int DynArrayFirstAvail(struct DynArray *dap);
  96
  97 #endif