158551Skris/* This may look like C code, but it is really -*- C++ -*- */ 258551Skris 358551Skris/* Simple lookup table abstraction implemented as an Iteration Number Array. 458551Skris 5228060Sbapt Copyright (C) 1989-1998, 2002 Free Software Foundation, Inc. 6228060Sbapt Written by Douglas C. Schmidt <schmidt@ics.uci.edu> 7228060Sbapt and Bruno Haible <bruno@clisp.org>. 858551Skris 9228060Sbapt This file is part of GNU GPERF. 1058551Skris 11228060Sbapt GNU GPERF is free software; you can redistribute it and/or modify 12228060Sbapt it under the terms of the GNU General Public License as published by 13228060Sbapt the Free Software Foundation; either version 2, or (at your option) 14228060Sbapt any later version. 1558551Skris 16228060Sbapt GNU GPERF is distributed in the hope that it will be useful, 17228060Sbapt but WITHOUT ANY WARRANTY; without even the implied warranty of 18228060Sbapt MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19228060Sbapt GNU General Public License for more details. 2058551Skris 21228060Sbapt You should have received a copy of the GNU General Public License 22228060Sbapt along with this program; see the file COPYING. 23228060Sbapt If not, write to the Free Software Foundation, Inc., 24228060Sbapt 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 2558551Skris 2658551Skris#ifndef bool_array_h 2758551Skris#define bool_array_h 1 2858551Skris 29228060Sbapt/* A Bool_Array instance is a bit array of fixed size, optimized for being 30228060Sbapt filled sparsely and cleared frequently. For example, when processing 31228060Sbapt tests/chill.gperf, the array will be: 32228060Sbapt - of size 15391, 33228060Sbapt - clear will be called 3509 times, 34228060Sbapt - set_bit will be called 300394 times. 35228060Sbapt With a conventional bit array implementation, clear would be too slow. 36228060Sbapt With a tree/hash based bit array implementation, set_bit would be slower. */ 3758551Skris 3858551Skrisclass Bool_Array 3958551Skris{ 40228060Sbaptpublic: 41228060Sbapt /* Initializes the bit array with room for SIZE bits, numbered from 42228060Sbapt 0 to SIZE-1. */ 43228060Sbapt Bool_Array (unsigned int size); 44228060Sbapt 45228060Sbapt /* Frees this object. */ 46228060Sbapt ~Bool_Array (); 47228060Sbapt 48228060Sbapt /* Resets all bits to zero. */ 49228060Sbapt void clear (); 50228060Sbapt 51228060Sbapt /* Sets the specified bit to true. 52228060Sbapt Returns its previous value (false or true). */ 53228060Sbapt bool set_bit (unsigned int index); 54228060Sbapt 5558551Skrisprivate: 56228060Sbapt /* Size of array. */ 57228060Sbapt unsigned int const _size; 5858551Skris 59228060Sbapt /* Current iteration number. Always nonzero. Starts out as 1, and is 60228060Sbapt incremented each time clear() is called. */ 61228060Sbapt unsigned int _iteration_number; 62228060Sbapt 63228060Sbapt /* For each index, we store in storage_array[index] the iteration_number at 64228060Sbapt the time set_bit(index) was last called. */ 65228060Sbapt unsigned int * const _storage_array; 6658551Skris}; 6758551Skris 6858551Skris#ifdef __OPTIMIZE__ /* efficiency hack! */ 6958551Skris 7058551Skris#include <stdio.h> 7158551Skris#include <string.h> 7258551Skris#include "options.h" 7358551Skris#define INLINE inline 7458551Skris#include "bool-array.icc" 7558551Skris#undef INLINE 7658551Skris 7758551Skris#endif 7858551Skris 7958551Skris#endif 80