/* * bit_array.c : implement a simple packed bit array * * ==================================================================== * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. * ==================================================================== */ #include "svn_sorts.h" #include "private/svn_subr_private.h" /* We allocate our data buffer in blocks of this size (in bytes). * For performance reasons, this shall be a power of two. * It should also not exceed 80kB (to prevent APR pool fragmentation) and * not be too small (to keep the number of OS-side memory allocations low - * avoiding hitting system-specific limits). */ #define BLOCK_SIZE 0x10000 /* Number of bits in each block. */ #define BLOCK_SIZE_BITS (8 * BLOCK_SIZE) /* Initial array size (covers INITIAL_BLOCK_COUNT * BLOCK_SIZE_BITS bits). * For performance reasons, this shall be a power of two. */ #define INITIAL_BLOCK_COUNT 16 /* We store the bits in a lazily allocated two-dimensional array. * For every BLOCK_SIZE_BITS range of indexes, there is one entry in the * BLOCKS array. If index / BLOCK_SIZE_BITS exceeds BLOCK_COUNT-1, the * blocks are implicitly empty. Only if a bit will be set to 1, will the * BLOCKS array be auto-expanded. * * As long as no bit got set in a particular block, the respective entry in * BLOCKS entry will be NULL, implying that all block contents is 0. */ struct svn_bit_array__t { /* Data buffer of BLOCK_COUNT blocks, BLOCK_SIZE_BITS each. Never NULL. * Every block may be NULL, though. */ unsigned char **blocks; /* Number of bytes allocated to DATA. Never shrinks. */ apr_size_t block_count; /* Reallocate DATA form this POOL when growing. */ apr_pool_t *pool; }; /* Given that MAX shall be an actual bit index in a packed bit array, * return the number of blocks entries to allocate for the data buffer. */ static apr_size_t select_data_size(apr_size_t max) { /* We allocate a power of two of bytes but at least 16 blocks. */ apr_size_t size = INITIAL_BLOCK_COUNT; /* Caution: * MAX / BLOCK_SIZE_BITS == SIZE still means that MAX is out of bounds. * OTOH, 2 * (MAX/BLOCK_SIZE_BITS) is always within the value range of * APR_SIZE_T. */ while (size <= max / BLOCK_SIZE_BITS) size *= 2; return size; } svn_bit_array__t * svn_bit_array__create(apr_size_t max, apr_pool_t *pool) { svn_bit_array__t *array = apr_pcalloc(pool, sizeof(*array)); array->block_count = select_data_size(max); array->pool = pool; array->blocks = apr_pcalloc(pool, array->block_count * sizeof(*array->blocks)); return array; } void svn_bit_array__set(svn_bit_array__t *array, apr_size_t idx, svn_boolean_t value) { unsigned char *block; /* Index within ARRAY->BLOCKS for the block containing bit IDX. */ apr_size_t block_idx = idx / BLOCK_SIZE_BITS; /* Within that block, index of the byte containing IDX. */ apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8; /* Within that byte, index of the bit corresponding to IDX. */ apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8; /* If IDX is outside the allocated range, we _may_ have to grow it. * * Be sure to use division instead of multiplication as we need to cover * the full value range of APR_SIZE_T for the bit indexes. */ if (block_idx >= array->block_count) { apr_size_t new_count; unsigned char **new_blocks; /* Unallocated indexes are implicitly 0, so no actual allocation * required in that case. */ if (!value) return; /* Grow block list to cover IDX. * Clear the new entries to guarantee our array[idx]==0 default. */ new_count = select_data_size(idx); new_blocks = apr_pcalloc(array->pool, new_count * sizeof(*new_blocks)); memcpy(new_blocks, array->blocks, array->block_count * sizeof(*new_blocks)); array->blocks = new_blocks; array->block_count = new_count; } /* IDX is covered by ARRAY->BLOCKS now. */ /* Get the block that contains IDX. Auto-allocate it if missing. */ block = array->blocks[block_idx]; if (block == NULL) { /* Unallocated indexes are implicitly 0, so no actual allocation * required in that case. */ if (!value) return; /* Allocate the previously missing block and clear it for our * array[idx] == 0 default. */ block = apr_pcalloc(array->pool, BLOCK_SIZE); array->blocks[block_idx] = block; } /* Set / reset one bit. Be sure to use unsigned shifts. */ if (value) block[byte_idx] |= (unsigned char)(1u << bit_idx); else block[byte_idx] &= ~(unsigned char)(1u << bit_idx); } svn_boolean_t svn_bit_array__get(svn_bit_array__t *array, apr_size_t idx) { unsigned char *block; /* Index within ARRAY->BLOCKS for the block containing bit IDX. */ apr_size_t block_idx = idx / BLOCK_SIZE_BITS; /* Within that block, index of the byte containing IDX. */ apr_size_t byte_idx = (idx % BLOCK_SIZE_BITS) / 8; /* Within that byte, index of the bit corresponding to IDX. */ apr_size_t bit_idx = (idx % BLOCK_SIZE_BITS) % 8; /* Indexes outside the allocated range are implicitly 0. */ if (block_idx >= array->block_count) return 0; /* Same if the respective block has not been allocated. */ block = array->blocks[block_idx]; if (block == NULL) return 0; /* Extract one bit (get the byte, shift bit to LSB, extract it). */ return (block[byte_idx] >> bit_idx) & 1; }