contrib/gperf/src/bool-array.h

   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    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