libvtv/vtv_set.h

   1 /* Copyright (C) 2012-2015 Free Software Foundation, Inc.
   2
   3    This file is part of GCC.
   4
   5    GCC is free software; you can redistribute it and/or modify it
   6    under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3, or (at your option)
   8    any later version.
   9
  10    GCC is distributed in the hope that it will be useful, but WITHOUT
  11    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  13    License for more details.
  14
  15    Under Section 7 of GPL version 3, you are granted additional
  16    permissions described in the GCC Runtime Library Exception, version
  17    3.1, as published by the Free Software Foundation.
  18
  19    You should have received a copy of the GNU General Public License
  20    and a copy of the GCC Runtime Library Exception along with this
  21    program; see the files COPYING3 and COPYING.RUNTIME respectively.
  22    If not, see <http://www.gnu.org/licenses/>.  */
  23
  24 #ifndef _VTV_SET_H
  25 #define _VTV_SET_H 1
  26
  27 /* Code in this file manages a collection of insert-only sets.  We
  28    have only tested the case where Key is uintptr_t, though it
  29    theoretically should work for some other cases.  All odd keys are
  30    reserved, and must not be inserted into any of the sets.  This code
  31    is intended primarily for sets of pointers, and the code is
  32    optimized for small sets (including size 0 and 1), but regardless
  33    of the set size, insert() and contains() have close to O(1) speed
  34    in practice.
  35
  36    TODO(gpike): fix this comment.
  37
  38    Recommended multithreaded use of a set:
  39
  40    For speed, we want to use a lock-free test for set membership.  The
  41    code handles simultaneous reads and inserts, as long as at most one
  42    insertion is in progress at a time.  After an insert, other threads
  43    may not immediately "see" the inserted key if they perform a
  44    lock-free read, so we recommend retrying, as explained below.
  45
  46    Also, to make data corruption less likely, we recommend using a
  47    "normal" RW page as well as one or pages that are typically RO
  48    but that can be switched to RW and back as needed.  The latter
  49    pages should contain sets.  The former should contain a lock, L,
  50    and an int or similar, num_writers.  Then, to insert, something
  51    like this would be safe:
  52     o Acquire L.
  53     o Increment num_writers; if that made it 1, change pages to RW.
  54     o Release L.
  55     o while (there are insertions to do in some set, S) {
  56         acquire L;
  57         do some insertions in S;
  58         release L;
  59       }
  60     o Acquire L.
  61     o Decrement num_writers; if that made it 0, change pages to RO.
  62     o Release L.
  63
  64    And to check if the set contains some key, one could use
  65      set.contains(key) ||
  66        ({ Acquire L; bool b = set.contains(key); Release L; b; })
  67
  68    In this scheme, the number of threads with reads in progress isn't
  69    tracked, so old sets can never be deleted.  In addition, on some
  70    architectures the intentionally racy reads might cause contains()
  71    to return true when it should have returned false.  This should be
  72    no problem on x86, and most other machines, where reading or
  73    writing an aligned uintptr_t is atomic.  E.g., on those machines,
  74    if *p is 0 and one thread does *p = x while another reads *p, the
  75    read will see either 0 or x.
  76
  77    To make the above easier, the insert_only_hash_sets class provides
  78    an interface to manipulate any number of hash sets.  One shouldn't
  79    create objects of that class, as it has no member data and its
  80    methods are static.
  81
  82    So the recommended model is to have a single lock, a single
  83    num_writers variable, and some number of sets.  If lock contention
  84    becomes a problem then the sets can be divided into k groups, each
  85    of which has a lock and a num_writers variable; or each set can be
  86    represented as a set of values that equal 0 mod m, a set of values
  87    that equal 1 mod m, ..., plus a set of values that equal m-1 mod m.
  88
  89    However, we expect most or all uses of this code to call contains()
  90    much more frequently than anything else, so lock contention is
  91    likely to be low.  */
  92
  93 #include <algorithm>
  94
  95 #ifndef HASHTABLE_STATS
  96 #define HASHTABLE_STATS 0
  97 #endif
  98
  99 #ifndef HASHTABLE_STATS_ATOMIC
 100 #define HASHTABLE_STATS_ATOMIC 0
 101 #endif
 102
 103 #if HASHTABLE_STATS
 104 #if HASHTABLE_STATS_ATOMIC
 105 /* Stat counters, with atomics. */
 106 #include <bits/atomic_word.h>
 107
 108 typedef _Atomic_word _AtomicStatCounter;
 109
 110 void
 111 inc_by (_AtomicStatCounter &stat, int amount)
 112 {
 113   __atomic_add_fetch (&stat, amount,  __ATOMIC_ACQ_REL);
 114 }
 115
 116 #else
 117
 118 /* Stat counters, but without atomics. */
 119 typedef int _AtomicStatCounter;
 120
 121 void
 122 inc_by (_AtomicStatCounter& stat, int amount)
 123 {
 124   stat += amount;
 125 }
 126
 127 #endif
 128
 129
 130 /* Number of calls to contains(), insert(), etc. */
 131 extern _AtomicStatCounter stat_insert;
 132 extern _AtomicStatCounter stat_contains;
 133 extern _AtomicStatCounter stat_resize;
 134 extern _AtomicStatCounter stat_create;
 135
 136 /* Sum of set size over all calls to contains().  */
 137 extern _AtomicStatCounter stat_contains_sizes;
 138
 139 /* contains() calls in a set whose capacity is more than 1. */
 140 extern _AtomicStatCounter stat_contains_in_non_trivial_set;
 141
 142 /* Probes in a set whose capacity is more than 1.  Ideally, this will
 143    be pretty close to stat_contains_in_non_trivial_set.  That will
 144    happen if our hash function is good and/or important keys were
 145    inserted before unimportant keys.  */
 146 extern _AtomicStatCounter stat_probes_in_non_trivial_set;
 147
 148 /* number of calls to contains() with size=0, 1, etc. */
 149 extern _AtomicStatCounter stat_contains_size0;
 150 extern _AtomicStatCounter stat_contains_size1;
 151 extern _AtomicStatCounter stat_contains_size2;
 152 extern _AtomicStatCounter stat_contains_size3;
 153 extern _AtomicStatCounter stat_contains_size4;
 154 extern _AtomicStatCounter stat_contains_size5;
 155 extern _AtomicStatCounter stat_contains_size6;
 156 extern _AtomicStatCounter stat_contains_size7;
 157 extern _AtomicStatCounter stat_contains_size8;
 158 extern _AtomicStatCounter stat_contains_size9;
 159 extern _AtomicStatCounter stat_contains_size10;
 160 extern _AtomicStatCounter stat_contains_size11;
 161 extern _AtomicStatCounter stat_contains_size12;
 162 extern _AtomicStatCounter stat_contains_size13_or_more;
 163 extern _AtomicStatCounter stat_grow_from_size0_to_1;
 164 extern _AtomicStatCounter stat_grow_from_size1_to_2;
 165 extern _AtomicStatCounter stat_double_the_number_of_buckets;
 166 extern _AtomicStatCounter stat_insert_key_that_was_already_present;
 167
 168 /* Hash collisions detected during insert_no_resize().  Only counts
 169    hasher(k) == hasher(k'); hasher(k) % tablesize == hasher(k') %
 170    tablesize is not sufficient.  Will count collisions that are
 171    detected during table resizes etc., so the same two keys may add to
 172    this stat multiple times.  */
 173 extern _AtomicStatCounter stat_insert_found_hash_collision;
 174
 175 #include <string>
 176
 177 struct insert_only_hash_sets_logger
 178 {
 179   static char *
 180   log (char c, char *buf)
 181   {
 182     *buf++ = c;
 183     return buf;
 184   }
 185
 186   static char *
 187   log (const char *s, char *buf)
 188   { return strcpy (buf, s) + strlen (s); }
 189
 190   static char *
 191   log (_AtomicStatCounter i, char *buf)
 192   {
 193     if (i < 10)
 194       return log ((char) ('0' + i), buf);
 195     else
 196       return log ((char) ('0' + i % 10), log (i / 10, buf));
 197   }
 198
 199   static char *
 200   log (const char *label, _AtomicStatCounter i, char *buf)
 201   {
 202     buf = log (label, buf);
 203     buf = log (": ", buf);
 204     buf = log (i, buf);
 205     return log ('\n', buf);
 206   }
 207 };
 208
 209 // Write stats to the given buffer, which should be at least 4000 bytes.
 210 static inline void
 211 insert_only_hash_tables_stats (char *buf)
 212 {
 213   buf = insert_only_hash_sets_logger::log ("insert", stat_insert, buf);
 214   buf = insert_only_hash_sets_logger::log ("contains", stat_contains, buf);
 215   buf = insert_only_hash_sets_logger::log ("resize", stat_resize, buf);
 216   buf = insert_only_hash_sets_logger::log ("create", stat_create, buf);
 217   buf = insert_only_hash_sets_logger::log ("insert_key_that_was_already_"
 218                                       "present",
 219                                       stat_insert_key_that_was_already_present,
 220                                       buf);
 221   buf = insert_only_hash_sets_logger::log ("contains_sizes",
 222                                            stat_contains_sizes, buf);
 223   buf = insert_only_hash_sets_logger::log ("contains_in_non_trivial_set",
 224                                            stat_contains_in_non_trivial_set,
 225                                            buf);
 226   buf = insert_only_hash_sets_logger::log ("probes_in_non_trivial_set",
 227                                            stat_probes_in_non_trivial_set,
 228                                            buf);
 229   buf = insert_only_hash_sets_logger::log ("contains_size0",
 230                                            stat_contains_size0, buf);
 231   buf = insert_only_hash_sets_logger::log ("contains_size1",
 232                                            stat_contains_size1, buf);
 233   buf = insert_only_hash_sets_logger::log ("contains_size2",
 234                                            stat_contains_size2, buf);
 235   buf = insert_only_hash_sets_logger::log ("contains_size3",
 236                                            stat_contains_size3, buf);
 237   buf = insert_only_hash_sets_logger::log ("contains_size4",
 238                                            stat_contains_size4, buf);
 239   buf = insert_only_hash_sets_logger::log ("contains_size5",
 240                                            stat_contains_size5, buf);
 241   buf = insert_only_hash_sets_logger::log ("contains_size6",
 242                                            stat_contains_size6, buf);
 243   buf = insert_only_hash_sets_logger::log ("contains_size7",
 244                                            stat_contains_size7, buf);
 245   buf = insert_only_hash_sets_logger::log ("contains_size8",
 246                                            stat_contains_size8, buf);
 247   buf = insert_only_hash_sets_logger::log ("contains_size9",
 248                                            stat_contains_size9, buf);
 249   buf = insert_only_hash_sets_logger::log ("contains_size10",
 250                                            stat_contains_size10, buf);
 251   buf = insert_only_hash_sets_logger::log ("contains_size11",
 252                                            stat_contains_size11, buf);
 253   buf = insert_only_hash_sets_logger::log ("contains_size12",
 254                                            stat_contains_size12, buf);
 255   buf = insert_only_hash_sets_logger::log ("contains_size13_or_more",
 256                                            stat_contains_size13_or_more, buf);
 257   buf = insert_only_hash_sets_logger::log ("grow_from_size0_to_1",
 258                                            stat_grow_from_size0_to_1, buf);
 259   buf = insert_only_hash_sets_logger::log ("grow_from_size1_to_2",
 260                                            stat_grow_from_size1_to_2, buf);
 261   buf = insert_only_hash_sets_logger::log ("insert_found_hash_collision",
 262                                            stat_insert_found_hash_collision,
 263                                            buf);
 264   buf = insert_only_hash_sets_logger::log ("double_the_number_of_buckets",
 265                                            stat_double_the_number_of_buckets,
 266                                            buf);
 267   *buf = '\0';
 268 }
 269
 270 #else
 271
 272 /* No stats. */
 273 #define inc_by(statname, amount) do { } while (false && (amount))
 274
 275 #endif
 276
 277 #define inc(statname) inc_by (statname, 1)
 278
 279 template <typename Key, class HashFcn, class Alloc>
 280 class insert_only_hash_sets
 281 {
 282  public:
 283   typedef Key key_type;
 284   typedef size_t size_type;
 285   typedef Alloc alloc_type;
 286   enum { illegal_key = 1 };
 287   enum { min_capacity = 4 };
 288 #if HASHTABLE_STATS
 289   enum { stats = true };
 290 #else
 291   enum { stats = false };
 292 #endif
 293
 294   /* Do not directly use insert_only_hash_set.  Instead, use the
 295      static methods below to create and manipulate objects of the
 296      following class.
 297
 298      Implementation details: each set is represented by a pointer
 299      plus, perhaps, out-of-line data, which would be an object of type
 300      insert_only_hash_set.  For a pointer, s, the interpretation is: s
 301      == NULL means empty set, lsb(s) == 1 means a set with one
 302      element, which is (uintptr_t)s - 1, and otherwise s is a pointer
 303      of type insert_only_hash_set*.  So, to increase the size of a set
 304      we have to change s and/or *s.  To check if a set contains some
 305      key we have to examine s and possibly *s.  */
 306   class insert_only_hash_set
 307   {
 308    public:
 309     /* Insert a key.  The key must not be a reserved key.  */
 310     static inline insert_only_hash_set *insert (key_type key,
 311                                                 insert_only_hash_set *s);
 312
 313
 314     /* Create an empty set.  */
 315     static inline insert_only_hash_set *create (size_type capacity);
 316
 317     /* Return whether the given key is present.  If key is illegal_key
 318        then either true or false may be returned, but for all other
 319        reserved keys false will be returned.  */
 320     static bool
 321     contains (key_type key, const insert_only_hash_set *s)
 322     {
 323       if (stats)
 324         {
 325           inc (stat_contains);
 326           switch (size (s))
 327             {
 328               case 0: inc (stat_contains_size0); break;
 329               case 1: inc (stat_contains_size1); break;
 330               case 2: inc (stat_contains_size2); break;
 331               case 3: inc (stat_contains_size3); break;
 332               case 4: inc (stat_contains_size4); break;
 333               case 5: inc (stat_contains_size5); break;
 334               case 6: inc (stat_contains_size6); break;
 335               case 7: inc (stat_contains_size7); break;
 336               case 8: inc (stat_contains_size8); break;
 337               case 9: inc (stat_contains_size9); break;
 338               case 10: inc (stat_contains_size10); break;
 339               case 11: inc (stat_contains_size11); break;
 340               case 12: inc (stat_contains_size12); break;
 341               default: inc (stat_contains_size13_or_more); break;
 342             }
 343           inc_by (stat_contains_sizes, size (s));
 344         }
 345
 346       return (singleton (s) ?
 347               singleton_key (key) == s :
 348               ((s != NULL) && s->contains (key)));
 349     }
 350
 351     /* Return a set's size.  */
 352     static size_type
 353     size (const insert_only_hash_set *s)
 354     { return (s == NULL) ? 0 : (singleton (s) ? 1 : s->num_entries); }
 355
 356     static inline insert_only_hash_set *resize (size_type target_num_buckets,
 357                                                 insert_only_hash_set *s);
 358
 359
 360    private:
 361     /* Return whether a set has size 1. */
 362     static bool
 363     singleton (const insert_only_hash_set *s)
 364     { return (uintptr_t) s & 1; }
 365
 366     /* Return the representation of a singleton set containing the
 367        given key.  */
 368     static insert_only_hash_set *
 369     singleton_key (key_type key)
 370     { return (insert_only_hash_set *) ((uintptr_t) key + 1); }
 371
 372     /* Given a singleton set, what key does it contain?  */
 373     static key_type
 374     extract_singleton_key (const insert_only_hash_set *s)
 375     {
 376       VTV_DEBUG_ASSERT (singleton (s));
 377       return (key_type) ((uintptr_t) s - 1);
 378     }
 379
 380     volatile key_type &
 381     key_at_index (size_type index)
 382     { return buckets[index]; }
 383
 384     key_type
 385     key_at_index (size_type index) const
 386     { return buckets[index]; }
 387
 388     size_type
 389     next_index (size_type index, size_type indices_examined) const
 390     { return (index + indices_examined) & (num_buckets - 1); }
 391
 392     inline void insert_no_resize (key_type key);
 393
 394     inline bool contains (key_type key) const;
 395
 396     inline insert_only_hash_set *resize_if_necessary (void);
 397
 398     size_type num_buckets;  /* Must be a power of 2 not less than
 399                                min_capacity.  */
 400     volatile size_type num_entries;
 401     volatile key_type buckets[0];  /* Actual array size is num_buckets.  */
 402   };
 403
 404   /* Create an empty set with the given capacity.  Requires that n be
 405      0 or a power of 2.  If 1 < n < min_capacity then treat n as
 406      min_capacity.  Sets *handle.  Returns true unless the allocator
 407      fails.  Subsequent operations on this set should use the same
 408      handle. */
 409
 410   static inline bool create (size_type n, insert_only_hash_set **handle);
 411
 412   /* Force the capacity of a set to be n, unless it was more than n
 413      already.  Requires that n be 0 or a power of 2.  Sets *handle
 414      unless the current capacity is n or more.  Returns true unless
 415      the allocator fails.  */
 416
 417   static inline bool resize (size_type n, insert_only_hash_set **handle);
 418
 419   /* Insert a key.  *handle is unmodified unless (1) a resize occurs,
 420      or (2) the set was initially empty. Returns true unless the
 421      allocator fails during a resize.  If the allocator fails during a
 422      resize then the set is reset to be the empty set.  The key must
 423      not be a reserved key.  */
 424
 425   static inline bool insert (key_type key, insert_only_hash_set **handle);
 426
 427   /* Check for the presence of a key.  If key is illegal_key then
 428      either true or false may be returned, but for all other reserved
 429      keys false will be returned.  */
 430
 431   static inline bool
 432   contains (key_type key, /* const */ insert_only_hash_set **handle)
 433   { return insert_only_hash_set::contains (key, *handle); }
 434
 435   /* Return the size of the given set.  */
 436   static size_type
 437   size (const insert_only_hash_set **handle)
 438   { return insert_only_hash_set::size (*handle); }
 439
 440   static bool
 441   is_reserved_key (key_type key)
 442   { return ((uintptr_t) key % 2) == 1; }
 443 };
 444
 445 template <typename Key, class HashFcn, class Alloc>
 446 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
 447 insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::resize
 448                                          (size_type n, insert_only_hash_set *s)
 449 {
 450   if (s == NULL)
 451     return create (n);
 452
 453   size_type capacity = singleton (s) ? 1 : s->num_buckets;
 454
 455   if (n <= capacity)
 456     return s;
 457
 458   insert_only_hash_set *result =
 459                                 create (std::max<size_type> (n, min_capacity));
 460   if (result != NULL)
 461     {
 462       if (singleton (s))
 463         {
 464           result->insert_no_resize (extract_singleton_key (s));
 465         }
 466       else
 467         {
 468           for (size_type i = 0; i < s->num_buckets; i++)
 469             if (s->buckets[i] != (key_type) illegal_key)
 470               result->insert_no_resize (s->buckets[i]);
 471         }
 472       VTV_DEBUG_ASSERT (size (result) == size (s));
 473     }
 474   return result;
 475 }
 476
 477 template <typename Key, class HashFcn, class Alloc>
 478 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
 479 insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::insert
 480                                         (key_type key, insert_only_hash_set *s)
 481 {
 482   VTV_DEBUG_ASSERT (!is_reserved_key (key));
 483
 484   inc_by (stat_grow_from_size0_to_1, s == NULL);
 485
 486   if (s == NULL)
 487     return singleton_key (key);
 488
 489   if (singleton (s))
 490     {
 491       const key_type old_key = extract_singleton_key (s);
 492       if (old_key == key)
 493         return s;
 494
 495       /* Grow from size 1 to size 2.  */
 496       inc (stat_grow_from_size1_to_2);
 497       s = create (2);
 498       if (s == NULL)
 499         return NULL;
 500
 501       s->insert_no_resize (old_key);
 502       s->insert_no_resize (key);
 503       VTV_DEBUG_ASSERT (size (s) == 2);
 504       return s;
 505     }
 506   s = s->resize_if_necessary();
 507   if (s != NULL)
 508     s->insert_no_resize (key);
 509   return s;
 510 }
 511
 512 template <typename Key, class HashFcn, class Alloc>
 513 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
 514 insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::create
 515                                                            (size_type capacity)
 516 {
 517   if (capacity <= 1)
 518     return NULL;
 519
 520   VTV_DEBUG_ASSERT (capacity > 1 && (capacity & (capacity - 1)) == 0);
 521   VTV_DEBUG_ASSERT (sizeof (insert_only_hash_set) == 2 * sizeof (size_type));
 522   capacity = std::max <size_type> (capacity, min_capacity);
 523   const size_t num_bytes = sizeof (insert_only_hash_set) +
 524                                                   sizeof (key_type) * capacity;
 525   alloc_type alloc;
 526   insert_only_hash_set *result = (insert_only_hash_set *) alloc (num_bytes);
 527   result->num_buckets = capacity;
 528   result->num_entries = 0;
 529   for (size_type i = 0; i < capacity; i++)
 530     result->buckets[i] = (key_type) illegal_key;
 531   return result;
 532 }
 533
 534 template <typename Key, class HashFcn, class Alloc>
 535 void
 536 insert_only_hash_sets<Key, HashFcn,
 537                                  Alloc>::insert_only_hash_set::insert_no_resize
 538                                                                  (key_type key)
 539 {
 540   HashFcn hasher;
 541   const size_type capacity = num_buckets;
 542   VTV_DEBUG_ASSERT (capacity >= min_capacity);
 543   VTV_DEBUG_ASSERT (!is_reserved_key (key));
 544   size_type index = hasher (key) & (capacity - 1);
 545   key_type k = key_at_index (index);
 546   size_type indices_examined = 0;
 547   while (k != key)
 548     {
 549       ++indices_examined;
 550       if (k == (key_type) illegal_key)
 551         {
 552           key_at_index (index) = key;
 553           ++num_entries;
 554           return;
 555         }
 556       else
 557         {
 558           inc_by (stat_insert_found_hash_collision,
 559                   hasher (k) == hasher (key));
 560         }
 561       VTV_DEBUG_ASSERT (indices_examined < capacity);
 562       index = next_index (index, indices_examined);
 563       k = key_at_index (index);
 564     }
 565 }
 566
 567 template<typename Key, class HashFcn, class Alloc>
 568 bool
 569 insert_only_hash_sets<Key, HashFcn, Alloc>::insert_only_hash_set::contains
 570                                                            (key_type key) const
 571 {
 572   inc (stat_contains_in_non_trivial_set);
 573   HashFcn hasher;
 574   const size_type capacity = num_buckets;
 575   size_type index = hasher (key) & (capacity - 1);
 576   key_type k = key_at_index (index);
 577   size_type indices_examined = 0;
 578   inc (stat_probes_in_non_trivial_set);
 579   while (k != key)
 580     {
 581       ++indices_examined;
 582       if (/*UNLIKELY*/(k == (key_type) illegal_key
 583                        || indices_examined == capacity))
 584         return false;
 585
 586       index = next_index (index, indices_examined);
 587       k = key_at_index (index);
 588       inc (stat_probes_in_non_trivial_set);
 589     }
 590   return true;
 591 }
 592
 593 template <typename Key, class HashFcn, class Alloc>
 594 typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set *
 595    insert_only_hash_sets<Key, HashFcn,
 596                        Alloc>::insert_only_hash_set::resize_if_necessary (void)
 597 {
 598   VTV_DEBUG_ASSERT (num_buckets >= min_capacity);
 599   size_type unused = num_buckets - num_entries;
 600   if (unused < (num_buckets >> 2))
 601     {
 602       inc (stat_double_the_number_of_buckets);
 603       size_type new_num_buckets = num_buckets * 2;
 604       insert_only_hash_set *s = create (new_num_buckets);
 605       for (size_type i = 0; i < num_buckets; i++)
 606         if (buckets[i] != (key_type) illegal_key)
 607           s->insert_no_resize (buckets[i]);
 608       VTV_DEBUG_ASSERT (size (this) == size (s));
 609       return s;
 610     }
 611   else
 612     return this;
 613 }
 614
 615 template<typename Key, class HashFcn, class Alloc>
 616 bool
 617 insert_only_hash_sets<Key, HashFcn, Alloc>::create (size_type n,
 618                                                  insert_only_hash_set **handle)
 619
 620 {
 621   inc (stat_create);
 622   *handle = insert_only_hash_set::create (n);
 623   return (n <= 1) || (*handle != NULL);
 624 }
 625
 626 template<typename Key, class HashFcn, class Alloc>
 627 bool
 628 insert_only_hash_sets<Key, HashFcn, Alloc>::resize (size_type n,
 629                                                  insert_only_hash_set **handle)
 630 {
 631   inc (stat_resize);
 632   *handle = insert_only_hash_set::resize (n, *handle);
 633   return (n <= 1) || (*handle != NULL);
 634 }
 635
 636 template<typename Key, class HashFcn, class Alloc>
 637 bool
 638 insert_only_hash_sets<Key, HashFcn, Alloc>::insert (key_type key,
 639                                                  insert_only_hash_set **handle)
 640 {
 641   inc (stat_insert);
 642   const size_type old_size = insert_only_hash_set::size (*handle);
 643   *handle = insert_only_hash_set::insert (key, *handle);
 644   if (*handle != NULL)
 645     {
 646       const size_type delta = insert_only_hash_set::size (*handle) - old_size;
 647       inc_by (stat_insert_key_that_was_already_present, delta == 0);
 648     }
 649   return *handle != NULL;
 650 }
 651
 652 #endif /* VTV_SET_H  */