diff options
author | Bruno Haible <bruno@clisp.org> | 2002-10-30 12:36:40 +0000 |
---|---|---|
committer | Bruno Haible <bruno@clisp.org> | 2002-10-30 12:36:40 +0000 |
commit | a07f46bd1d8e30fd1969da7119c95d88ed2054ce (patch) | |
tree | dd3c89e18604af52110caa217678f17dd5101086 | |
parent | c7f32d582f25b14e852ae157299caf4df5ecad01 (diff) | |
download | gperf-a07f46bd1d8e30fd1969da7119c95d88ed2054ce.tar.gz |
Rework Bool_Array.
-rw-r--r-- | ChangeLog | 8 | ||||
-rw-r--r-- | src/bool-array.cc | 8 | ||||
-rw-r--r-- | src/bool-array.h | 39 | ||||
-rw-r--r-- | src/bool-array.icc | 37 | ||||
-rw-r--r-- | src/gen-perf.cc | 28 | ||||
-rw-r--r-- | src/gen-perf.h | 5 |
6 files changed, 59 insertions, 66 deletions
@@ -1,5 +1,13 @@ 2002-10-03 Bruno Haible <bruno@clisp.org> + * src/bool-array.h (Bool_Array): Make all members non-static. + Add an argument to the constructor. Remove init(), rename reset() to + clear(), rename find() to set_bit(). + * src/bool-array.icc: Move init() code into the constructor. + Rename reset() to clear(), rename find() to set_bit(). + * src/gen-perf.h (Gen_Perf): Add collision_detector member. + * src/gen-perf.cc: Update. + * src/gen-perf.h (Gen_Perf::doit_all): Renamed from Gen_Perf::operator (). * src/gen-perf.cc (Gen_Perf::doit_all): Renamed from diff --git a/src/bool-array.cc b/src/bool-array.cc index 83e15b0..b6bf158 100644 --- a/src/bool-array.cc +++ b/src/bool-array.cc @@ -24,14 +24,10 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA. */ #include <string.h> #include "options.h" -unsigned int * Bool_Array::storage_array; -unsigned int Bool_Array::iteration_number; -unsigned int Bool_Array::size; - -/* Prints out debugging diagnostics. */ - +/* Frees this object. */ Bool_Array::~Bool_Array (void) { + /* Print out debugging diagnostics. */ if (option[DEBUG]) fprintf (stderr, "\ndumping boolean array information\n" "size = %d\niteration number = %d\nend of array dump\n", diff --git a/src/bool-array.h b/src/bool-array.h index c91e08e..6450723 100644 --- a/src/bool-array.h +++ b/src/bool-array.h @@ -21,25 +21,38 @@ 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. */ - #ifndef bool_array_h #define bool_array_h 1 +/* 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 { -private: - static unsigned int *storage_array; /* Initialization of the index space. */ - static unsigned int iteration_number; /* Keep track of the current iteration. */ - static unsigned int size; /* Keep track of array size. */ - public: - Bool_Array (void); - ~Bool_Array (void); - static void init (unsigned int *buffer, unsigned int s); - static int find (int hash_value); - static void reset (void); + /* Initializes the bit array with room for s bits, numbered from 0 to s-1. */ + Bool_Array (unsigned int s); + + /* Frees this object. */ + ~Bool_Array (void); + + /* Resets all bits to zero. */ + void clear (void); + + /* Sets the specified bit to one. Returns its previous value (0 or 1). */ + int set_bit (unsigned int index); + +private: + unsigned int size; /* Size of array. */ + unsigned int iteration_number; /* Number of times clear() was called + 1. */ + /* For each index, we store in storage_array[index] the iteration_number at + the time set_bit(index) was last called. */ + unsigned int *storage_array; }; #ifdef __OPTIMIZE__ /* efficiency hack! */ diff --git a/src/bool-array.icc b/src/bool-array.icc index 6c5859e..389be31 100644 --- a/src/bool-array.icc +++ b/src/bool-array.icc @@ -24,56 +24,47 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ //#include <string.h> //#include "options.h" +/* Initializes the bit array with room for s bits, numbered from 0 to s-1. */ INLINE -Bool_Array::Bool_Array (void) +Bool_Array::Bool_Array (unsigned int s) + : size (s), iteration_number (1), storage_array (new unsigned int [s]) { - storage_array = 0; - iteration_number = size = 0; -} - -INLINE void -Bool_Array::init (unsigned int *buffer, unsigned int s) -{ - size = s; - iteration_number = 1; - storage_array = buffer; - memset (storage_array, 0, s * sizeof (*storage_array)); + memset (storage_array, 0, s * sizeof (unsigned int)); if (option[DEBUG]) fprintf (stderr, "\nbool array size = %d, total bytes = %d\n", size, (unsigned int) (size * sizeof (*storage_array))); } +/* Sets the specified bit to one. Returns its previous value (0 or 1). */ INLINE int -Bool_Array::find (int index) +Bool_Array::set_bit (unsigned int index) { if (storage_array[index] == iteration_number) + /* The bit was set since the last clear() call. */ return 1; else { + /* The last operation on this bit was clear(). Set it now. */ storage_array[index] = iteration_number; return 0; } } +/* Resets all bits to zero. */ INLINE void -Bool_Array::reset (void) +Bool_Array::clear (void) { /* If we wrap around it's time to zero things out again! However, this only - occurs once about every 2^31 or 2^15 iterations, so it should probably - never happen! */ + occurs once about every 2^32 iterations, so it will not happen more + frequently than once per second. */ if (++iteration_number == 0) { - if (option[DEBUG]) - { - fprintf (stderr, "(re-initializing bool_array)..."); - fflush (stderr); - } iteration_number = 1; - memset (storage_array, 0, size * sizeof (*storage_array)); + memset (storage_array, 0, size * sizeof (unsigned int)); if (option[DEBUG]) { - fprintf (stderr, "done\n"); + fprintf (stderr, "(re-initialized bool_array)\n"); fflush (stderr); } } diff --git a/src/gen-perf.cc b/src/gen-perf.cc index ea04d59..6d84b21 100644 --- a/src/gen-perf.cc +++ b/src/gen-perf.cc @@ -71,6 +71,7 @@ Gen_Perf::Gen_Perf (void) } max_hash_value = Key_List::max_key_length () + option.get_asso_max () * option.get_max_keysig_size (); + collision_detector = new Bool_Array (max_hash_value + 1); if (option[DEBUG]) fprintf (stderr, "total non-linked keys = %d\nmaximum associated value is %d" @@ -183,13 +184,13 @@ Gen_Perf::affects_prev (char c, List_Node *curr) & (option.get_asso_max () - 1); /* Iteration Number array is a win, O(1) intialization time! */ - reset (); + collision_detector->clear (); /* See how this asso_value change affects previous keywords. If it does better than before we'll take it! */ for (List_Node *ptr = head; - !Bool_Array::find (hash (ptr)) || ++collisions < fewest_collisions; + !collision_detector->set_bit (hash (ptr)) || ++collisions < fewest_collisions; ptr = ptr->next) if (ptr == curr) { @@ -274,18 +275,6 @@ Gen_Perf::change (List_Node *prior, List_Node *curr) int Gen_Perf::doit_all (void) { -#if LARGE_STACK_ARRAYS - unsigned int buffer[max_hash_value + 1]; -#else - // Note: we don't use new, because that invokes a custom operator new. - unsigned int *buffer - = (unsigned int*) malloc (sizeof(unsigned int) * (max_hash_value + 1)); - if (buffer == NULL) - abort (); -#endif - - Bool_Array::init (buffer, max_hash_value + 1); - List_Node *curr; for (curr = head; curr; curr = curr->next) { @@ -302,19 +291,16 @@ Gen_Perf::doit_all (void) /* Make one final check, just to make sure nothing weird happened.... */ - Bool_Array::reset (); + collision_detector->clear (); for (curr = head; curr; curr = curr->next) - if (Bool_Array::find (hash (curr))) + if (collision_detector->set_bit (hash (curr))) if (option[DUP]) /* Keep track of this number... */ total_duplicates++; else /* Yow, big problems. we're outta here! */ { fprintf (stderr, "\nInternal error, duplicate value %d:\n" "try options -D or -r, or use new key positions.\n\n", hash (curr)); -#if !LARGE_STACK_ARRAYS - free ((char *) buffer); -#endif return 1; } @@ -324,9 +310,6 @@ Gen_Perf::doit_all (void) sort (); output (); -#if !LARGE_STACK_ARRAYS - free ((char *) buffer); -#endif return 0; } @@ -346,5 +329,6 @@ Gen_Perf::~Gen_Perf (void) fprintf (stderr, "end table dumping\n"); } + delete collision_detector; } diff --git a/src/gen-perf.h b/src/gen-perf.h index 4cf10ce..144020b 100644 --- a/src/gen-perf.h +++ b/src/gen-perf.h @@ -3,7 +3,7 @@ /* Provides high-level routines to manipulate the keyword list structures the code generation output. - Copyright (C) 1989-1998, 2000 Free Software Foundation, Inc. + Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc. written by Douglas C. Schmidt (schmidt@ics.uci.edu) This file is part of GNU GPERF. @@ -28,12 +28,13 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA. */ #include "key-list.h" #include "bool-array.h" -class Gen_Perf : private Key_List, private Bool_Array +class Gen_Perf : private Key_List { private: int max_hash_value; /* Maximum possible hash value. */ int fewest_collisions; /* Records fewest # of collisions for asso value. */ int num_done; /* Number of keywords processed without a collision. */ + Bool_Array *collision_detector; void change (List_Node *prior, List_Node *curr); int affects_prev (char c, List_Node *curr); |