aboutsummaryrefslogtreecommitdiffstats
path: root/src/bool-array.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/bool-array.h')
-rw-r--r--src/bool-array.h83
1 files changed, 48 insertions, 35 deletions
diff --git a/src/bool-array.h b/src/bool-array.h
index 8330fcd22019..ddfbd869b501 100644
--- a/src/bool-array.h
+++ b/src/bool-array.h
@@ -2,54 +2,67 @@
/* Simple lookup table abstraction implemented as an Iteration Number Array.
- Copyright (C) 1989-1998 Free Software Foundation, Inc.
- written by Douglas C. Schmidt (schmidt@ics.uci.edu)
+ Copyright (C) 1989-1998, 2002 Free Software Foundation, Inc.
+ Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
+ and Bruno Haible <bruno@clisp.org>.
-This file is part of GNU GPERF.
+ This file is part of GNU GPERF.
-GNU GPERF is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 1, or (at your option)
-any later version.
+ GNU GPERF is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
-GNU GPERF is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+ GNU GPERF is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
-You should have received a copy of the GNU General Public License
-along with GNU GPERF; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
-
-/* Define and implement a simple boolean array abstraction,
- uses an Iteration Numbering implementation to save on initialization time. */
+ You should have received a copy of the GNU General Public License
+ along with this program; see the file COPYING.
+ If not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
#ifndef bool_array_h
#define bool_array_h 1
-#include "trace.h"
-
-#ifdef LO_CAL
-/* If we are on a memory diet then we'll only make these use a limited
- amount of storage space. */
-typedef unsigned short STORAGE_TYPE;
-#else
-typedef unsigned int STORAGE_TYPE;
-#endif
+/* A Bool_Array instance is a bit array of fixed size, optimized for being
+ filled sparsely and cleared frequently. For example, when processing
+ tests/chill.gperf, the array will be:
+ - of size 15391,
+ - clear will be called 3509 times,
+ - set_bit will be called 300394 times.
+ With a conventional bit array implementation, clear would be too slow.
+ With a tree/hash based bit array implementation, set_bit would be slower. */
class Bool_Array
{
+public:
+ /* Initializes the bit array with room for SIZE bits, numbered from
+ 0 to SIZE-1. */
+ Bool_Array (unsigned int size);
+
+ /* Frees this object. */
+ ~Bool_Array ();
+
+ /* Resets all bits to zero. */
+ void clear ();
+
+ /* Sets the specified bit to true.
+ Returns its previous value (false or true). */
+ bool set_bit (unsigned int index);
+
private:
- static STORAGE_TYPE *storage_array; /* Initialization of the index space. */
- static STORAGE_TYPE iteration_number; /* Keep track of the current iteration. */
- static unsigned int size; /* Keep track of array size. */
+ /* Size of array. */
+ unsigned int const _size;
-public:
- Bool_Array (void);
- ~Bool_Array (void);
- static void init (STORAGE_TYPE *buffer, unsigned int s);
- static int find (int hash_value);
- static void reset (void);
+ /* Current iteration number. Always nonzero. Starts out as 1, and is
+ incremented each time clear() is called. */
+ unsigned int _iteration_number;
+
+ /* For each index, we store in storage_array[index] the iteration_number at
+ the time set_bit(index) was last called. */
+ unsigned int * const _storage_array;
};
#ifdef __OPTIMIZE__ /* efficiency hack! */