1/* This may look like C code, but it is really -*- C++ -*- */ 2 3/* Simple lookup table abstraction implemented as an Iteration Number Array. 4 5 Copyright (C) 1989-1998, 2002 Free Software Foundation, Inc. 6 Written by Douglas C. Schmidt <schmidt@ics.uci.edu> 7 and Bruno Haible <bruno@clisp.org>. 8 9 This file is part of GNU GPERF. 10 11 This program is free software: you can redistribute it and/or modify 12 it under the terms of the GNU General Public License as published by 13 the Free Software Foundation; either version 3 of the License, or 14 (at your option) any later version. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License for more details. 20 21 You should have received a copy of the GNU General Public License 22 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 23 24#ifndef bool_array_h 25#define bool_array_h 1 26 27/* A Bool_Array instance is a bit array of fixed size, optimized for being 28 filled sparsely and cleared frequently. For example, when processing 29 tests/chill.gperf, the array will be: 30 - of size 15391, 31 - clear will be called 3509 times, 32 - set_bit will be called 300394 times. 33 With a conventional bit array implementation, clear would be too slow. 34 With a tree/hash based bit array implementation, set_bit would be slower. */ 35 36class Bool_Array 37{ 38public: 39 /* Initializes the bit array with room for SIZE bits, numbered from 40 0 to SIZE-1. */ 41 Bool_Array (unsigned int size); 42 43 /* Frees this object. */ 44 ~Bool_Array (); 45 46 /* Resets all bits to zero. */ 47 void clear (); 48 49 /* Sets the specified bit to true. 50 Returns its previous value (false or true). */ 51 bool set_bit (unsigned int index); 52 53private: 54 /* Size of array. */ 55 unsigned int const _size; 56 57 /* Current iteration number. Always nonzero. Starts out as 1, and is 58 incremented each time clear() is called. */ 59 unsigned int _iteration_number; 60 61 /* For each index, we store in storage_array[index] the iteration_number at 62 the time set_bit(index) was last called. */ 63 unsigned int * const _storage_array; 64}; 65 66#ifdef __OPTIMIZE__ /* efficiency hack! */ 67 68#include <stdio.h> 69#include <string.h> 70#include "options.h" 71#define INLINE inline 72#include "bool-array.icc" 73#undef INLINE 74 75#endif 76 77#endif 78