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 <[email protected]> 7 and Bruno Haible <[email protected]>. 8 9 This file is part of GNU GPERF. 10 11 GNU GPERF 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 2, or (at your option) 14 any later version. 15 16 GNU GPERF 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; see the file COPYING. 23 If not, write to the Free Software Foundation, Inc., 24 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 25 26 #ifndef bool_array_h 27 #define bool_array_h 1 28 29 /* A Bool_Array instance is a bit array of fixed size, optimized for being 30 filled sparsely and cleared frequently. For example, when processing 31 tests/chill.gperf, the array will be: 32 - of size 15391, 33 - clear will be called 3509 times, 34 - set_bit will be called 300394 times. 35 With a conventional bit array implementation, clear would be too slow. 36 With a tree/hash based bit array implementation, set_bit would be slower. */ 37 38 class Bool_Array 39 { 40 public: 41 /* Initializes the bit array with room for SIZE bits, numbered from 42 0 to SIZE-1. */ 43 Bool_Array (unsigned int size); 44 45 /* Frees this object. */ 46 ~Bool_Array (); 47 48 /* Resets all bits to zero. */ 49 void clear (); 50 51 /* Sets the specified bit to true. 52 Returns its previous value (false or true). */ 53 bool set_bit (unsigned int index); 54 55 private: 56 /* Size of array. */ 57 unsigned int const _size; 58 59 /* Current iteration number. Always nonzero. Starts out as 1, and is 60 incremented each time clear() is called. */ 61 unsigned int _iteration_number; 62 63 /* For each index, we store in storage_array[index] the iteration_number at 64 the time set_bit(index) was last called. */ 65 unsigned int * const _storage_array; 66 }; 67 68 #ifdef __OPTIMIZE__ /* efficiency hack! */ 69 70 #include <stdio.h> 71 #include <string.h> 72 #include "options.h" 73 #define INLINE inline 74 #include "bool-array.icc" 75 #undef INLINE 76 77 #endif 78 79 #endif 80