2 * bit_array.c : implement a simple packed bit array
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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
21 * ====================================================================
25 #include "svn_sorts.h"
26 #include "private/svn_subr_private.h"
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).
34 #define BLOCK_SIZE 0x10000
36 /* Number of bits in each block.
38 #define BLOCK_SIZE_BITS (8 * BLOCK_SIZE)
40 /* Initial array size (covers INITIAL_BLOCK_COUNT * BLOCK_SIZE_BITS bits).
41 * For performance reasons, this shall be a power of two.
43 #define INITIAL_BLOCK_COUNT 16
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.
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.
54 struct svn_bit_array__t
56 /* Data buffer of BLOCK_COUNT blocks, BLOCK_SIZE_BITS each. Never NULL.
57 * Every block may be NULL, though. */
58 unsigned char **blocks;
60 /* Number of bytes allocated to DATA. Never shrinks. */
61 apr_size_t block_count;
63 /* Reallocate DATA form this POOL when growing. */
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. */
70 select_data_size(apr_size_t max)
72 /* We allocate a power of two of bytes but at least 16 blocks. */
73 apr_size_t size = INITIAL_BLOCK_COUNT;
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
79 while (size <= max / BLOCK_SIZE_BITS)
86 svn_bit_array__create(apr_size_t max,
89 svn_bit_array__t *array = apr_pcalloc(pool, sizeof(*array));
91 array->block_count = select_data_size(max);
93 array->blocks = apr_pcalloc(pool,
94 array->block_count * sizeof(*array->blocks));
100 svn_bit_array__set(svn_bit_array__t *array,
104 unsigned char *block;
106 /* Index within ARRAY->BLOCKS for the block containing bit IDX. */
107 apr_size_t block_idx = idx / BLOCK_SIZE_BITS;
109 /* Within that block, index of the byte containing IDX. */
110 apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8;
112 /* Within that byte, index of the bit corresponding to IDX. */
113 apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8;
115 /* If IDX is outside the allocated range, we _may_ have to grow it.
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.
120 if (block_idx >= array->block_count)
122 apr_size_t new_count;
123 unsigned char **new_blocks;
125 /* Unallocated indexes are implicitly 0, so no actual allocation
126 * required in that case.
131 /* Grow block list to cover IDX.
132 * Clear the new entries to guarantee our array[idx]==0 default.
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;
142 /* IDX is covered by ARRAY->BLOCKS now. */
144 /* Get the block that contains IDX. Auto-allocate it if missing. */
145 block = array->blocks[block_idx];
148 /* Unallocated indexes are implicitly 0, so no actual allocation
149 * required in that case.
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;
160 /* Set / reset one bit. Be sure to use unsigned shifts. */
162 block[byte_idx] |= (unsigned char)(1u << bit_idx);
164 block[byte_idx] &= ~(unsigned char)(1u << bit_idx);
168 svn_bit_array__get(svn_bit_array__t *array,
171 unsigned char *block;
173 /* Index within ARRAY->BLOCKS for the block containing bit IDX. */
174 apr_size_t block_idx = idx / BLOCK_SIZE_BITS;
176 /* Within that block, index of the byte containing IDX. */
177 apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8;
179 /* Within that byte, index of the bit corresponding to IDX. */
180 apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8;
182 /* Indexes outside the allocated range are implicitly 0. */
183 if (block_idx >= array->block_count)
186 /* Same if the respective block has not been allocated. */
187 block = array->blocks[block_idx];
191 /* Extract one bit (get the byte, shift bit to LSB, extract it). */
192 return (block[byte_idx] >> bit_idx) & 1;