1140609Sdas/* This may look like C code, but it is really -*- C++ -*- */ 2140609Sdas 3140609Sdas/* Simple lookup table abstraction implemented as an Iteration Number Array. 4140609Sdas 5140609Sdas Copyright (C) 1989-1998, 2002 Free Software Foundation, Inc. 6140609Sdas Written by Douglas C. Schmidt <schmidt@ics.uci.edu> 7140609Sdas and Bruno Haible <bruno@clisp.org>. 8140609Sdas 9140609Sdas This file is part of GNU GPERF. 10140609Sdas 11140609Sdas GNU GPERF is free software; you can redistribute it and/or modify 12140609Sdas it under the terms of the GNU General Public License as published by 13140609Sdas the Free Software Foundation; either version 2, or (at your option) 14140609Sdas any later version. 15140609Sdas 16140609Sdas GNU GPERF is distributed in the hope that it will be useful, 17140609Sdas but WITHOUT ANY WARRANTY; without even the implied warranty of 18140609Sdas MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19140609Sdas GNU General Public License for more details. 20140609Sdas 21140609Sdas You should have received a copy of the GNU General Public License 22140609Sdas along with this program; see the file COPYING. 23140609Sdas If not, write to the Free Software Foundation, Inc., 24140609Sdas 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 25140609Sdas 26140609Sdas#ifndef bool_array_h 27140609Sdas#define bool_array_h 1 28140609Sdas 29140609Sdas/* A Bool_Array instance is a bit array of fixed size, optimized for being 30140609Sdas filled sparsely and cleared frequently. For example, when processing 31140609Sdas tests/chill.gperf, the array will be: 32140609Sdas - of size 15391, 33140609Sdas - clear will be called 3509 times, 34140609Sdas - set_bit will be called 300394 times. 35192760Sattilio 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 38class Bool_Array 39{ 40public: 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 55private: 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