source: arduino-1-6-7/trunk/fuentes/arduino-ide-amd64/hardware/tools/avr/lib/gcc/avr/4.9.2/plugin/include/hash-table.h @ 4837

Last change on this file since 4837 was 4837, checked in by daduve, 2 years ago

Adding new version

File size: 28.9 KB
Line 
1/* A type-safe hash table template.
2   Copyright (C) 2012-2014 Free Software Foundation, Inc.
3   Contributed by Lawrence Crowl <crowl@google.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21
22/* This file implements a typed hash table.
23   The implementation borrows from libiberty's htab_t in hashtab.h.
24
25
26   INTRODUCTION TO TYPES
27
28   Users of the hash table generally need to be aware of three types.
29
30      1. The type being placed into the hash table.  This type is called
31      the value type.
32
33      2. The type used to describe how to handle the value type within
34      the hash table.  This descriptor type provides the hash table with
35      several things.
36
37         - A typedef named 'value_type' to the value type (from above).
38
39         - A static member function named 'hash' that takes a value_type
40         pointer and returns a hashval_t value.
41
42         - A typedef named 'compare_type' that is used to test when an value
43         is found.  This type is the comparison type.  Usually, it will be the
44         same as value_type.  If it is not the same type, you must generally
45         explicitly compute hash values and pass them to the hash table.
46
47         - A static member function named 'equal' that takes a value_type
48         pointer and a compare_type pointer, and returns a bool.
49
50         - A static function named 'remove' that takes an value_type pointer
51         and frees the memory allocated by it.  This function is used when
52         individual elements of the table need to be disposed of (e.g.,
53         when deleting a hash table, removing elements from the table, etc).
54
55      3. The type of the hash table itself.  (More later.)
56
57   In very special circumstances, users may need to know about a fourth type.
58
59      4. The template type used to describe how hash table memory
60      is allocated.  This type is called the allocator type.  It is
61      parameterized on the value type.  It provides four functions.
62
63         - A static member function named 'control_alloc'.  This function
64         allocates the control data blocks for the table.
65
66         - A static member function named 'control_free'.  This function
67         frees the control data blocks for the table.
68
69         - A static member function named 'data_alloc'.  This function
70         allocates the data elements in the table.
71
72         - A static member function named 'data_free'.  This function
73         deallocates the data elements in the table.
74
75   Hash table are instantiated with two type arguments.
76
77      * The descriptor type, (2) above.
78
79      * The allocator type, (4) above.  In general, you will not need to
80      provide your own allocator type.  By default, hash tables will use
81      the class template xcallocator, which uses malloc/free for allocation.
82
83
84   DEFINING A DESCRIPTOR TYPE
85
86   The first task in using the hash table is to describe the element type.
87   We compose this into a few steps.
88
89      1. Decide on a removal policy for values stored in the table.
90         This header provides class templates for the two most common
91         policies.
92
93         * typed_free_remove implements the static 'remove' member function
94         by calling free().
95
96         * typed_noop_remove implements the static 'remove' member function
97         by doing nothing.
98
99         You can use these policies by simply deriving the descriptor type
100         from one of those class template, with the appropriate argument.
101
102         Otherwise, you need to write the static 'remove' member function
103         in the descriptor class.
104
105      2. Choose a hash function.  Write the static 'hash' member function.
106
107      3. Choose an equality testing function.  In most cases, its two
108      arguments will be value_type pointers.  If not, the first argument must
109      be a value_type pointer, and the second argument a compare_type pointer.
110
111
112   AN EXAMPLE DESCRIPTOR TYPE
113
114   Suppose you want to put some_type into the hash table.  You could define
115   the descriptor type as follows.
116
117      struct some_type_hasher : typed_noop_remove <some_type>
118      // Deriving from typed_noop_remove means that we get a 'remove' that does
119      // nothing.  This choice is good for raw values.
120      {
121        typedef some_type value_type;
122        typedef some_type compare_type;
123        static inline hashval_t hash (const value_type *);
124        static inline bool equal (const value_type *, const compare_type *);
125      };
126
127      inline hashval_t
128      some_type_hasher::hash (const value_type *e)
129      { ... compute and return a hash value for E ... }
130
131      inline bool
132      some_type_hasher::equal (const value_type *p1, const compare_type *p2)
133      { ... compare P1 vs P2.  Return true if they are the 'same' ... }
134
135
136   AN EXAMPLE HASH_TABLE DECLARATION
137
138   To instantiate a hash table for some_type:
139
140      hash_table <some_type_hasher> some_type_hash_table;
141
142   There is no need to mention some_type directly, as the hash table will
143   obtain it using some_type_hasher::value_type.
144
145   You can then used any of the functions in hash_table's public interface.
146   See hash_table for details.  The interface is very similar to libiberty's
147   htab_t.
148
149
150   EASY DESCRIPTORS FOR POINTERS
151
152   The class template pointer_hash provides everything you need to hash
153   pointers (as opposed to what they point to).  So, to instantiate a hash
154   table over pointers to whatever_type,
155
156      hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
157
158
159   HASH TABLE ITERATORS
160
161   The hash table provides standard C++ iterators.  For example, consider a
162   hash table of some_info.  We wish to consume each element of the table:
163
164      extern void consume (some_info *);
165
166   We define a convenience typedef and the hash table:
167
168      typedef hash_table <some_info_hasher> info_table_type;
169      info_table_type info_table;
170
171   Then we write the loop in typical C++ style:
172
173      for (info_table_type::iterator iter = info_table.begin ();
174           iter != info_table.end ();
175           ++iter)
176        if ((*iter).status == INFO_READY)
177          consume (&*iter);
178
179   Or with common sub-expression elimination:
180
181      for (info_table_type::iterator iter = info_table.begin ();
182           iter != info_table.end ();
183           ++iter)
184        {
185          some_info &elem = *iter;
186          if (elem.status == INFO_READY)
187            consume (&elem);
188        }
189
190   One can also use a more typical GCC style:
191
192      typedef some_info *some_info_p;
193      some_info *elem_ptr;
194      info_table_type::iterator iter;
195      FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
196        if (elem_ptr->status == INFO_READY)
197          consume (elem_ptr);
198
199*/
200
201
202#ifndef TYPED_HASHTAB_H
203#define TYPED_HASHTAB_H
204
205#include "hashtab.h"
206
207
208/* The ordinary memory allocator.  */
209/* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
210
211template <typename Type>
212struct xcallocator
213{
214  static Type *control_alloc (size_t count);
215  static Type *data_alloc (size_t count);
216  static void control_free (Type *memory);
217  static void data_free (Type *memory);
218};
219
220
221/* Allocate memory for COUNT control blocks.  */
222
223template <typename Type>
224inline Type *
225xcallocator <Type>::control_alloc (size_t count)
226{
227  return static_cast <Type *> (xcalloc (count, sizeof (Type)));
228}
229
230
231/* Allocate memory for COUNT data blocks.  */
232
233template <typename Type>
234inline Type *
235xcallocator <Type>::data_alloc (size_t count)
236{
237  return static_cast <Type *> (xcalloc (count, sizeof (Type)));
238}
239
240
241/* Free memory for control blocks.  */
242
243template <typename Type>
244inline void
245xcallocator <Type>::control_free (Type *memory)
246{
247  return ::free (memory);
248}
249
250
251/* Free memory for data blocks.  */
252
253template <typename Type>
254inline void
255xcallocator <Type>::data_free (Type *memory)
256{
257  return ::free (memory);
258}
259
260
261/* Helpful type for removing with free.  */
262
263template <typename Type>
264struct typed_free_remove
265{
266  static inline void remove (Type *p);
267};
268
269
270/* Remove with free.  */
271
272template <typename Type>
273inline void
274typed_free_remove <Type>::remove (Type *p)
275{
276  free (p);
277}
278
279
280/* Helpful type for a no-op remove.  */
281
282template <typename Type>
283struct typed_noop_remove
284{
285  static inline void remove (Type *p);
286};
287
288
289/* Remove doing nothing.  */
290
291template <typename Type>
292inline void
293typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
294{
295}
296
297
298/* Pointer hash with a no-op remove method.  */
299
300template <typename Type>
301struct pointer_hash : typed_noop_remove <Type>
302{
303  typedef Type value_type;
304  typedef Type compare_type;
305
306  static inline hashval_t
307  hash (const value_type *);
308
309  static inline int
310  equal (const value_type *existing, const compare_type *candidate);
311};
312
313template <typename Type>
314inline hashval_t
315pointer_hash <Type>::hash (const value_type *candidate)
316{
317  /* This is a really poor hash function, but it is what the current code uses,
318     so I am reusing it to avoid an additional axis in testing.  */
319  return (hashval_t) ((intptr_t)candidate >> 3);
320}
321
322template <typename Type>
323inline int
324pointer_hash <Type>::equal (const value_type *existing,
325                           const compare_type *candidate)
326{
327  return existing == candidate;
328}
329
330
331/* Table of primes and their inversion information.  */
332
333struct prime_ent
334{
335  hashval_t prime;
336  hashval_t inv;
337  hashval_t inv_m2;     /* inverse of prime-2 */
338  hashval_t shift;
339};
340
341extern struct prime_ent const prime_tab[];
342
343
344/* Functions for computing hash table indexes.  */
345
346extern unsigned int hash_table_higher_prime_index (unsigned long n);
347extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
348extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
349
350
351/* Internal implementation type.  */
352
353template <typename T>
354struct hash_table_control
355{
356  /* Table itself.  */
357  T **entries;
358
359  /* Current size (in entries) of the hash table.  */
360  size_t size;
361
362  /* Current number of elements including also deleted elements.  */
363  size_t n_elements;
364
365  /* Current number of deleted elements in the table.  */
366  size_t n_deleted;
367
368  /* The following member is used for debugging. Its value is number
369     of all calls of `htab_find_slot' for the hash table. */
370  unsigned int searches;
371
372  /* The following member is used for debugging.  Its value is number
373     of collisions fixed for time of work with the hash table. */
374  unsigned int collisions;
375
376  /* Current size (in entries) of the hash table, as an index into the
377     table of primes.  */
378  unsigned int size_prime_index;
379};
380
381
382/* User-facing hash table type.
383
384   The table stores elements of type Descriptor::value_type.
385
386   It hashes values with the hash member function.
387     The table currently works with relatively weak hash functions.
388     Use typed_pointer_hash <Value> when hashing pointers instead of objects.
389
390   It compares elements with the equal member function.
391     Two elements with the same hash may not be equal.
392     Use typed_pointer_equal <Value> when hashing pointers instead of objects.
393
394   It removes elements with the remove member function.
395     This feature is useful for freeing memory.
396     Derive from typed_null_remove <Value> when not freeing objects.
397     Derive from typed_free_remove <Value> when doing a simple object free.
398
399   Specify the template Allocator to allocate and free memory.
400     The default is xcallocator.
401
402*/
403
404template <typename Descriptor,
405          template <typename Type> class Allocator = xcallocator>
406class hash_table
407{
408public:
409  typedef typename Descriptor::value_type value_type;
410  typedef typename Descriptor::compare_type compare_type;
411
412  class iterator
413  {
414  public:
415    inline iterator ();
416    inline iterator (value_type **, value_type **);
417    inline value_type &operator * ();
418    void slide ();
419    inline iterator &operator ++ ();
420    inline bool operator != (const iterator &) const;
421  private:
422    value_type **m_slot;
423    value_type **m_limit;
424  };
425
426private:
427  hash_table_control <value_type> *htab;
428
429  value_type **find_empty_slot_for_expand (hashval_t hash);
430  void expand ();
431
432public:
433  hash_table ();
434  void create (size_t initial_slots);
435  bool is_created ();
436  void dispose ();
437  value_type *find (const value_type *value);
438  value_type *find_with_hash (const compare_type *comparable, hashval_t hash);
439  value_type **find_slot (const value_type *value, enum insert_option insert);
440  value_type **find_slot_with_hash (const compare_type *comparable,
441                                    hashval_t hash, enum insert_option insert);
442  void empty ();
443  void clear_slot (value_type **slot);
444  void remove_elt (const value_type *value);
445  void remove_elt_with_hash (const compare_type *comparable, hashval_t hash);
446  size_t size ();
447  size_t elements ();
448  size_t elements_with_deleted ();
449  double collisions ();
450
451  template <typename Argument,
452            int (*Callback) (value_type **slot, Argument argument)>
453  void traverse_noresize (Argument argument);
454
455  template <typename Argument,
456            int (*Callback) (value_type **slot, Argument argument)>
457  void traverse (Argument argument);
458
459  iterator begin ();
460  iterator end ();
461};
462
463
464/* Construct the hash table.  The only useful operation next is create.  */
465
466template <typename Descriptor,
467          template <typename Type> class Allocator>
468inline
469hash_table <Descriptor, Allocator>::hash_table ()
470: htab (NULL)
471{
472}
473
474
475/* See if the table has been created, as opposed to constructed.  */
476
477template <typename Descriptor,
478          template <typename Type> class Allocator>
479inline bool
480hash_table <Descriptor, Allocator>::is_created ()
481{
482  return htab != NULL;
483}
484
485
486/* Like find_with_hash, but compute the hash value from the element.  */
487
488template <typename Descriptor,
489          template <typename Type> class Allocator>
490inline typename Descriptor::value_type *
491hash_table <Descriptor, Allocator>::find (const value_type *value)
492{
493  return find_with_hash (value, Descriptor::hash (value));
494}
495
496
497/* Like find_slot_with_hash, but compute the hash value from the element.  */
498
499template <typename Descriptor,
500          template <typename Type> class Allocator>
501inline typename Descriptor::value_type **
502hash_table <Descriptor, Allocator>
503::find_slot (const value_type *value, enum insert_option insert)
504{
505  return find_slot_with_hash (value, Descriptor::hash (value), insert);
506}
507
508
509/* Like remove_elt_with_hash, but compute the hash value from the element.  */
510
511template <typename Descriptor,
512          template <typename Type> class Allocator>
513inline void
514hash_table <Descriptor, Allocator>::remove_elt (const value_type *value)
515{
516  remove_elt_with_hash (value, Descriptor::hash (value));
517}
518
519
520/* Return the current size of this hash table.  */
521
522template <typename Descriptor,
523          template <typename Type> class Allocator>
524inline size_t
525hash_table <Descriptor, Allocator>::size ()
526{
527  return htab->size;
528}
529
530
531/* Return the current number of elements in this hash table. */
532
533template <typename Descriptor,
534          template <typename Type> class Allocator>
535inline size_t
536hash_table <Descriptor, Allocator>::elements ()
537{
538  return htab->n_elements - htab->n_deleted;
539}
540
541
542/* Return the current number of elements in this hash table. */
543
544template <typename Descriptor,
545          template <typename Type> class Allocator>
546inline size_t
547hash_table <Descriptor, Allocator>::elements_with_deleted ()
548{
549  return htab->n_elements;
550}
551
552
553  /* Return the fraction of fixed collisions during all work with given
554     hash table. */
555
556template <typename Descriptor,
557          template <typename Type> class Allocator>
558inline double
559hash_table <Descriptor, Allocator>::collisions ()
560{
561  if (htab->searches == 0)
562    return 0.0;
563
564  return static_cast <double> (htab->collisions) / htab->searches;
565}
566
567
568/* Create a hash table with at least the given number of INITIAL_SLOTS.  */
569
570template <typename Descriptor,
571          template <typename Type> class Allocator>
572void
573hash_table <Descriptor, Allocator>::create (size_t size)
574{
575  unsigned int size_prime_index;
576
577  size_prime_index = hash_table_higher_prime_index (size);
578  size = prime_tab[size_prime_index].prime;
579
580  htab = Allocator <hash_table_control <value_type> > ::control_alloc (1);
581  gcc_assert (htab != NULL);
582  htab->entries = Allocator <value_type*> ::data_alloc (size);
583  gcc_assert (htab->entries != NULL);
584  htab->size = size;
585  htab->size_prime_index = size_prime_index;
586}
587
588
589/* Dispose of a hash table.  Free all memory and return this hash table to
590   the non-created state.  Naturally the hash table must already exist.  */
591
592template <typename Descriptor,
593          template <typename Type> class Allocator>
594void
595hash_table <Descriptor, Allocator>::dispose ()
596{
597  size_t size = htab->size;
598  value_type **entries = htab->entries;
599
600  for (int i = size - 1; i >= 0; i--)
601    if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
602      Descriptor::remove (entries[i]);
603
604  Allocator <value_type *> ::data_free (entries);
605  Allocator <hash_table_control <value_type> > ::control_free (htab);
606  htab = NULL;
607}
608
609
610/* Similar to find_slot, but without several unwanted side effects:
611    - Does not call equal when it finds an existing entry.
612    - Does not change the count of elements/searches/collisions in the
613      hash table.
614   This function also assumes there are no deleted entries in the table.
615   HASH is the hash value for the element to be inserted.  */
616
617template <typename Descriptor,
618          template <typename Type> class Allocator>
619typename Descriptor::value_type **
620hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
621{
622  hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
623  size_t size = htab->size;
624  value_type **slot = htab->entries + index;
625  hashval_t hash2;
626
627  if (*slot == HTAB_EMPTY_ENTRY)
628    return slot;
629  else if (*slot == HTAB_DELETED_ENTRY)
630    abort ();
631
632  hash2 = hash_table_mod2 (hash, htab->size_prime_index);
633  for (;;)
634    {
635      index += hash2;
636      if (index >= size)
637        index -= size;
638
639      slot = htab->entries + index;
640      if (*slot == HTAB_EMPTY_ENTRY)
641        return slot;
642      else if (*slot == HTAB_DELETED_ENTRY)
643        abort ();
644    }
645}
646
647
648/* The following function changes size of memory allocated for the
649   entries and repeatedly inserts the table elements.  The occupancy
650   of the table after the call will be about 50%.  Naturally the hash
651   table must already exist.  Remember also that the place of the
652   table entries is changed.  If memory allocation fails, this function
653   will abort.  */
654
655template <typename Descriptor,
656          template <typename Type> class Allocator>
657void
658hash_table <Descriptor, Allocator>::expand ()
659{
660  value_type **oentries;
661  value_type **olimit;
662  value_type **p;
663  value_type **nentries;
664  size_t nsize, osize, elts;
665  unsigned int oindex, nindex;
666
667  oentries = htab->entries;
668  oindex = htab->size_prime_index;
669  osize = htab->size;
670  olimit = oentries + osize;
671  elts = elements ();
672
673  /* Resize only when table after removal of unused elements is either
674     too full or too empty.  */
675  if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
676    {
677      nindex = hash_table_higher_prime_index (elts * 2);
678      nsize = prime_tab[nindex].prime;
679    }
680  else
681    {
682      nindex = oindex;
683      nsize = osize;
684    }
685
686  nentries = Allocator <value_type *> ::data_alloc (nsize);
687  gcc_assert (nentries != NULL);
688  htab->entries = nentries;
689  htab->size = nsize;
690  htab->size_prime_index = nindex;
691  htab->n_elements -= htab->n_deleted;
692  htab->n_deleted = 0;
693
694  p = oentries;
695  do
696    {
697      value_type *x = *p;
698
699      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
700        {
701          value_type **q = find_empty_slot_for_expand (Descriptor::hash (x));
702
703          *q = x;
704        }
705
706      p++;
707    }
708  while (p < olimit);
709
710  Allocator <value_type *> ::data_free (oentries);
711}
712
713
714/* This function searches for a hash table entry equal to the given
715   COMPARABLE element starting with the given HASH value.  It cannot
716   be used to insert or delete an element. */
717
718template <typename Descriptor,
719          template <typename Type> class Allocator>
720typename Descriptor::value_type *
721hash_table <Descriptor, Allocator>
722::find_with_hash (const compare_type *comparable, hashval_t hash)
723{
724  hashval_t index, hash2;
725  size_t size;
726  value_type *entry;
727
728  htab->searches++;
729  size = htab->size;
730  index = hash_table_mod1 (hash, htab->size_prime_index);
731
732  entry = htab->entries[index];
733  if (entry == HTAB_EMPTY_ENTRY
734      || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable)))
735    return entry;
736
737  hash2 = hash_table_mod2 (hash, htab->size_prime_index);
738  for (;;)
739    {
740      htab->collisions++;
741      index += hash2;
742      if (index >= size)
743        index -= size;
744
745      entry = htab->entries[index];
746      if (entry == HTAB_EMPTY_ENTRY
747          || (entry != HTAB_DELETED_ENTRY
748              && Descriptor::equal (entry, comparable)))
749        return entry;
750    }
751}
752
753
754/* This function searches for a hash table slot containing an entry
755   equal to the given COMPARABLE element and starting with the given
756   HASH.  To delete an entry, call this with insert=NO_INSERT, then
757   call clear_slot on the slot returned (possibly after doing some
758   checks).  To insert an entry, call this with insert=INSERT, then
759   write the value you want into the returned slot.  When inserting an
760   entry, NULL may be returned if memory allocation fails. */
761
762template <typename Descriptor,
763          template <typename Type> class Allocator>
764typename Descriptor::value_type **
765hash_table <Descriptor, Allocator>
766::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
767                       enum insert_option insert)
768{
769  value_type **first_deleted_slot;
770  hashval_t index, hash2;
771  size_t size;
772  value_type *entry;
773
774  size = htab->size;
775  if (insert == INSERT && size * 3 <= htab->n_elements * 4)
776    {
777      expand ();
778      size = htab->size;
779    }
780
781  index = hash_table_mod1 (hash, htab->size_prime_index);
782
783  htab->searches++;
784  first_deleted_slot = NULL;
785
786  entry = htab->entries[index];
787  if (entry == HTAB_EMPTY_ENTRY)
788    goto empty_entry;
789  else if (entry == HTAB_DELETED_ENTRY)
790    first_deleted_slot = &htab->entries[index];
791  else if (Descriptor::equal (entry, comparable))
792    return &htab->entries[index];
793
794  hash2 = hash_table_mod2 (hash, htab->size_prime_index);
795  for (;;)
796    {
797      htab->collisions++;
798      index += hash2;
799      if (index >= size)
800        index -= size;
801
802      entry = htab->entries[index];
803      if (entry == HTAB_EMPTY_ENTRY)
804        goto empty_entry;
805      else if (entry == HTAB_DELETED_ENTRY)
806        {
807          if (!first_deleted_slot)
808            first_deleted_slot = &htab->entries[index];
809        }
810      else if (Descriptor::equal (entry, comparable))
811        return &htab->entries[index];
812    }
813
814 empty_entry:
815  if (insert == NO_INSERT)
816    return NULL;
817
818  if (first_deleted_slot)
819    {
820      htab->n_deleted--;
821      *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY);
822      return first_deleted_slot;
823    }
824
825  htab->n_elements++;
826  return &htab->entries[index];
827}
828
829
830/* This function clears all entries in the given hash table.  */
831
832template <typename Descriptor,
833          template <typename Type> class Allocator>
834void
835hash_table <Descriptor, Allocator>::empty ()
836{
837  size_t size = htab->size;
838  value_type **entries = htab->entries;
839  int i;
840
841  for (i = size - 1; i >= 0; i--)
842    if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
843      Descriptor::remove (entries[i]);
844
845  /* Instead of clearing megabyte, downsize the table.  */
846  if (size > 1024*1024 / sizeof (PTR))
847    {
848      int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
849      int nsize = prime_tab[nindex].prime;
850
851      Allocator <value_type *> ::data_free (htab->entries);
852      htab->entries = Allocator <value_type *> ::data_alloc (nsize);
853      htab->size = nsize;
854      htab->size_prime_index = nindex;
855    }
856  else
857    memset (entries, 0, size * sizeof (value_type *));
858  htab->n_deleted = 0;
859  htab->n_elements = 0;
860}
861
862
863/* This function clears a specified SLOT in a hash table.  It is
864   useful when you've already done the lookup and don't want to do it
865   again. */
866
867template <typename Descriptor,
868          template <typename Type> class Allocator>
869void
870hash_table <Descriptor, Allocator>::clear_slot (value_type **slot)
871{
872  if (slot < htab->entries || slot >= htab->entries + htab->size
873      || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
874    abort ();
875
876  Descriptor::remove (*slot);
877
878  *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
879  htab->n_deleted++;
880}
881
882
883/* This function deletes an element with the given COMPARABLE value
884   from hash table starting with the given HASH.  If there is no
885   matching element in the hash table, this function does nothing. */
886
887template <typename Descriptor,
888          template <typename Type> class Allocator>
889void
890hash_table <Descriptor, Allocator>
891::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
892{
893  value_type **slot;
894
895  slot = find_slot_with_hash (comparable, hash, NO_INSERT);
896  if (*slot == HTAB_EMPTY_ENTRY)
897    return;
898
899  Descriptor::remove (*slot);
900
901  *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
902  htab->n_deleted++;
903}
904
905
906/* This function scans over the entire hash table calling CALLBACK for
907   each live entry.  If CALLBACK returns false, the iteration stops.
908   ARGUMENT is passed as CALLBACK's second argument. */
909
910template <typename Descriptor,
911          template <typename Type> class Allocator>
912template <typename Argument,
913          int (*Callback) (typename Descriptor::value_type **slot, Argument argument)>
914void
915hash_table <Descriptor, Allocator>::traverse_noresize (Argument argument)
916{
917  value_type **slot;
918  value_type **limit;
919
920  slot = htab->entries;
921  limit = slot + htab->size;
922
923  do
924    {
925      value_type *x = *slot;
926
927      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
928        if (! Callback (slot, argument))
929          break;
930    }
931  while (++slot < limit);
932}
933
934
935/* Like traverse_noresize, but does resize the table when it is too empty
936   to improve effectivity of subsequent calls.  */
937
938template <typename Descriptor,
939          template <typename Type> class Allocator>
940template <typename Argument,
941          int (*Callback) (typename Descriptor::value_type **slot,
942                           Argument argument)>
943void
944hash_table <Descriptor, Allocator>::traverse (Argument argument)
945{
946  size_t size = htab->size;
947  if (elements () * 8 < size && size > 32)
948    expand ();
949
950  traverse_noresize <Argument, Callback> (argument);
951}
952
953
954/* Iterator definitions.  */
955
956/* The default constructor produces the end value.  */
957
958template <typename Descriptor,
959          template <typename Type> class Allocator>
960inline
961hash_table <Descriptor, Allocator>::iterator::iterator ()
962: m_slot (NULL), m_limit (NULL)
963{
964}
965
966/* The parameterized constructor produces the begin value.  */
967
968template <typename Descriptor,
969          template <typename Type> class Allocator>
970inline
971hash_table <Descriptor, Allocator>::iterator::iterator
972   (value_type **slot, value_type **limit)
973: m_slot (slot), m_limit (limit)
974{
975}
976
977/* Obtain the element.  */
978
979template <typename Descriptor,
980          template <typename Type> class Allocator>
981inline typename hash_table <Descriptor, Allocator>::value_type &
982hash_table <Descriptor, Allocator>::iterator::operator * ()
983{
984  return **m_slot;
985}
986
987/* Slide down the iterator slots until an active entry is found.  */
988
989template <typename Descriptor,
990          template <typename Type> class Allocator>
991void
992hash_table <Descriptor, Allocator>::iterator::slide ()
993{
994  for ( ; m_slot < m_limit; ++m_slot )
995    {
996      value_type *x = *m_slot;
997      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
998        return;
999    }
1000  m_slot = NULL;
1001  m_limit = NULL;
1002}
1003
1004/* Bump the iterator.  */
1005
1006template <typename Descriptor,
1007          template <typename Type> class Allocator>
1008inline typename hash_table <Descriptor, Allocator>::iterator &
1009hash_table <Descriptor, Allocator>::iterator::operator ++ ()
1010{
1011  ++m_slot;
1012  slide ();
1013  return *this;
1014}
1015
1016/* Compare iterators.  */
1017
1018template <typename Descriptor,
1019          template <typename Type> class Allocator>
1020inline bool
1021hash_table <Descriptor, Allocator>::iterator::
1022  operator != (const iterator &other) const
1023{
1024  return m_slot != other.m_slot || m_limit != other.m_limit;
1025}
1026
1027/* Hash table iterator producers.  */
1028
1029/* The beginning of a hash table iteration.  */
1030
1031template <typename Descriptor,
1032          template <typename Type> class Allocator>
1033inline typename hash_table <Descriptor, Allocator>::iterator
1034hash_table <Descriptor, Allocator>::begin ()
1035{
1036  iterator hti (htab->entries, htab->entries + htab->size);
1037  hti.slide ();
1038  return hti;
1039}
1040
1041/* The end of a hash table iteration.  */
1042
1043template <typename Descriptor,
1044          template <typename Type> class Allocator>
1045inline typename hash_table <Descriptor, Allocator>::iterator
1046hash_table <Descriptor, Allocator>::end ()
1047{
1048  return iterator ();
1049}
1050
1051/* Iterate through the elements of hash_table HTAB,
1052   using hash_table <....>::iterator ITER,
1053   storing each element in RESULT, which is of type TYPE.  */
1054
1055#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1056  for ((ITER) = (HTAB).begin (); \
1057       (ITER) != (HTAB).end () ? (RESULT = &*(ITER) , true) : false; \
1058       ++(ITER))
1059
1060#endif /* TYPED_HASHTAB_H */
Note: See TracBrowser for help on using the repository browser.