contrib/subversion/subversion/libsvn_subr/bit_array.c

   1 /*
   2  * bit_array.c :  implement a simple packed bit array
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24
  25 #include "svn_sorts.h"
  26 #include "private/svn_subr_private.h"
  27
  28 /* We allocate our data buffer in blocks of this size (in bytes).
  29  * For performance reasons, this shall be a power of two.
  30  * It should also not exceed 80kB (to prevent APR pool fragmentation) and
  31  * not be too small (to keep the number of OS-side memory allocations low -
  32  * avoiding hitting system-specific limits).
  33  */
  34 #define BLOCK_SIZE          0x10000
  35
  36 /* Number of bits in each block.
  37  */
  38 #define BLOCK_SIZE_BITS     (8 * BLOCK_SIZE)
  39
  40 /* Initial array size (covers INITIAL_BLOCK_COUNT * BLOCK_SIZE_BITS bits).
  41  * For performance reasons, this shall be a power of two.
  42  */
  43 #define INITIAL_BLOCK_COUNT 16
  44
  45 /* We store the bits in a lazily allocated two-dimensional array.
  46  * For every BLOCK_SIZE_BITS range of indexes, there is one entry in the
  47  * BLOCKS array.  If index / BLOCK_SIZE_BITS exceeds BLOCK_COUNT-1, the
  48  * blocks are implicitly empty.  Only if a bit will be set to 1, will the
  49  * BLOCKS array be auto-expanded.
  50  *
  51  * As long as no bit got set in a particular block, the respective entry in
  52  * BLOCKS entry will be NULL, implying that all block contents is 0.
  53  */
  54 struct svn_bit_array__t
  55 {
  56   /* Data buffer of BLOCK_COUNT blocks, BLOCK_SIZE_BITS each.  Never NULL.
  57    * Every block may be NULL, though. */
  58   unsigned char **blocks;
  59
  60   /* Number of bytes allocated to DATA.  Never shrinks. */
  61   apr_size_t block_count;
  62
  63   /* Reallocate DATA form this POOL when growing. */
  64   apr_pool_t *pool;
  65 };
  66
  67 /* Given that MAX shall be an actual bit index in a packed bit array,
  68  * return the number of blocks entries to allocate for the data buffer. */
  69 static apr_size_t
  70 select_data_size(apr_size_t max)
  71 {
  72   /* We allocate a power of two of bytes but at least 16 blocks. */
  73   apr_size_t size = INITIAL_BLOCK_COUNT;
  74
  75   /* Caution:
  76    * MAX / BLOCK_SIZE_BITS == SIZE still means that MAX is out of bounds.
  77    * OTOH, 2 * (MAX/BLOCK_SIZE_BITS) is always within the value range of
  78    * APR_SIZE_T. */
  79   while (size <= max / BLOCK_SIZE_BITS)
  80     size *= 2;
  81
  82   return size;
  83 }
  84
  85 svn_bit_array__t *
  86 svn_bit_array__create(apr_size_t max,
  87                       apr_pool_t *pool)
  88 {
  89   svn_bit_array__t *array = apr_pcalloc(pool, sizeof(*array));
  90
  91   array->block_count = select_data_size(max);
  92   array->pool = pool;
  93   array->blocks = apr_pcalloc(pool,
  94                               array->block_count * sizeof(*array->blocks));
  95
  96   return array;
  97 }
  98
  99 void
 100 svn_bit_array__set(svn_bit_array__t *array,
 101                    apr_size_t idx,
 102                    svn_boolean_t value)
 103 {
 104   unsigned char *block;
 105
 106   /* Index within ARRAY->BLOCKS for the block containing bit IDX. */
 107   apr_size_t block_idx = idx / BLOCK_SIZE_BITS;
 108
 109   /* Within that block, index of the byte containing IDX. */
 110   apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8;
 111
 112   /* Within that byte, index of the bit corresponding to IDX. */
 113   apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8;
 114
 115   /* If IDX is outside the allocated range, we _may_ have to grow it.
 116    *
 117    * Be sure to use division instead of multiplication as we need to cover
 118    * the full value range of APR_SIZE_T for the bit indexes.
 119    */
 120   if (block_idx >= array->block_count)
 121     {
 122       apr_size_t new_count;
 123       unsigned char **new_blocks;
 124
 125       /* Unallocated indexes are implicitly 0, so no actual allocation
 126        * required in that case.
 127        */
 128       if (!value)
 129         return;
 130
 131       /* Grow block list to cover IDX.
 132        * Clear the new entries to guarantee our array[idx]==0 default.
 133        */
 134       new_count = select_data_size(idx);
 135       new_blocks = apr_pcalloc(array->pool, new_count * sizeof(*new_blocks));
 136       memcpy(new_blocks, array->blocks,
 137              array->block_count * sizeof(*new_blocks));
 138       array->blocks = new_blocks;
 139       array->block_count = new_count;
 140     }
 141
 142   /* IDX is covered by ARRAY->BLOCKS now. */
 143
 144   /* Get the block that contains IDX.  Auto-allocate it if missing. */
 145   block = array->blocks[block_idx];
 146   if (block == NULL)
 147     {
 148       /* Unallocated indexes are implicitly 0, so no actual allocation
 149        * required in that case.
 150        */
 151       if (!value)
 152         return;
 153
 154       /* Allocate the previously missing block and clear it for our
 155        * array[idx] == 0 default. */
 156       block = apr_pcalloc(array->pool, BLOCK_SIZE);
 157       array->blocks[block_idx] = block;
 158     }
 159
 160   /* Set / reset one bit.  Be sure to use unsigned shifts. */
 161   if (value)
 162     block[byte_idx] |=  (unsigned char)(1u << bit_idx);
 163   else
 164     block[byte_idx] &= ~(unsigned char)(1u << bit_idx);
 165 }
 166
 167 svn_boolean_t
 168 svn_bit_array__get(svn_bit_array__t *array,
 169                    apr_size_t idx)
 170 {
 171   unsigned char *block;
 172
 173   /* Index within ARRAY->BLOCKS for the block containing bit IDX. */
 174   apr_size_t block_idx = idx / BLOCK_SIZE_BITS;
 175
 176   /* Within that block, index of the byte containing IDX. */
 177   apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8;
 178
 179   /* Within that byte, index of the bit corresponding to IDX. */
 180   apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8;
 181
 182   /* Indexes outside the allocated range are implicitly 0. */
 183   if (block_idx >= array->block_count)
 184     return 0;
 185
 186   /* Same if the respective block has not been allocated. */
 187   block = array->blocks[block_idx];
 188   if (block == NULL)
 189     return 0;
 190
 191   /* Extract one bit (get the byte, shift bit to LSB, extract it). */
 192   return (block[byte_idx] >> bit_idx) & 1;
 193 }
 194