bit_array.c revision 299742 
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 */
54struct 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. */
69static apr_size_t
70select_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
85svn_bit_array__t *
86svn_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
99void
100svn_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
167svn_boolean_t
168svn_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
195