libstdc++
pat_trie_.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the terms
8 // of the GNU General Public License as published by the Free Software
9 // Foundation; either version 3, or (at your option) any later
10 // version.
11 
12 // This library is distributed in the hope that it will be useful, but
13 // WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 // General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 
28 // Permission to use, copy, modify, sell, and distribute this software
29 // is hereby granted without fee, provided that the above copyright
30 // notice appears in all copies, and that both that copyright notice
31 // and this permission notice appear in supporting documentation. None
32 // of the above authors, nor IBM Haifa Research Laboratories, make any
33 // representation about the suitability of this software for any
34 // purpose. It is provided "as is" without express or implied
35 // warranty.
36 
37 /**
38  * @file pat_trie_/pat_trie_.hpp
39  * Contains an implementation class for a patricia tree.
40  */
41 
42 #include <iterator>
43 #include <utility>
44 #include <algorithm>
45 #include <functional>
46 #include <assert.h>
47 #include <list>
48 #include <ext/pb_ds/exception.hpp>
57 #ifdef _GLIBCXX_DEBUG
59 #endif
60 #include <debug/debug.h>
61 
62 namespace __gnu_pbds
63 {
64  namespace detail
65  {
66 #ifdef PB_DS_DATA_TRUE_INDICATOR
67 #define PB_DS_PAT_TRIE_NAME pat_trie_map
68 #endif
69 
70 #ifdef PB_DS_DATA_FALSE_INDICATOR
71 #define PB_DS_PAT_TRIE_NAME pat_trie_set
72 #endif
73 
74 #define PB_DS_CLASS_T_DEC \
75  template<typename Key, typename Mapped, typename Node_And_It_Traits, \
76  typename _Alloc>
77 
78 #define PB_DS_CLASS_C_DEC \
79  PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc>
80 
81 #define PB_DS_PAT_TRIE_TRAITS_BASE \
82  types_traits<Key, Mapped, _Alloc, false>
83 
84 #ifdef _GLIBCXX_DEBUG
85 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
86  debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \
87  typename _Alloc::template rebind<Key>::other::const_reference>
88 #endif
89 
90 
91  /**
92  * @brief PATRICIA trie.
93  * @ingroup branch-detail
94  *
95  * This implementation loosely borrows ideas from:
96  * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998
97  * 2) Ptset: Sets of integers implemented as Patricia trees,
98  * Jean-Christophe Filliatr, 2000
99  */
100  template<typename Key, typename Mapped, typename Node_And_It_Traits,
101  typename _Alloc>
102  class PB_DS_PAT_TRIE_NAME :
103 #ifdef _GLIBCXX_DEBUG
104  public PB_DS_DEBUG_MAP_BASE_C_DEC,
105 #endif
106  public Node_And_It_Traits::synth_access_traits,
107  public Node_And_It_Traits::node_update,
108  public PB_DS_PAT_TRIE_TRAITS_BASE,
109  public pat_trie_base
110  {
111  private:
112  typedef pat_trie_base base_type;
113  typedef PB_DS_PAT_TRIE_TRAITS_BASE traits_base;
114  typedef Node_And_It_Traits traits_type;
115 
116  typedef typename traits_type::synth_access_traits synth_access_traits;
117  typedef typename synth_access_traits::const_iterator a_const_iterator;
118 
119  typedef typename traits_type::node node;
120  typedef typename _Alloc::template rebind<node> __rebind_n;
121  typedef typename __rebind_n::other::const_pointer node_const_pointer;
122  typedef typename __rebind_n::other::pointer node_pointer;
123 
124  typedef typename traits_type::head head;
125  typedef typename _Alloc::template rebind<head> __rebind_h;
126  typedef typename __rebind_h::other head_allocator;
127  typedef typename head_allocator::pointer head_pointer;
128 
129  typedef typename traits_type::leaf leaf;
130  typedef typename _Alloc::template rebind<leaf> __rebind_l;
131  typedef typename __rebind_l::other leaf_allocator;
132  typedef typename leaf_allocator::pointer leaf_pointer;
133  typedef typename leaf_allocator::const_pointer leaf_const_pointer;
134 
135  typedef typename traits_type::inode inode;
136  typedef typename inode::iterator inode_iterator;
137  typedef typename _Alloc::template rebind<inode> __rebind_in;
138  typedef typename __rebind_in::other __rebind_ina;
139  typedef typename __rebind_in::other inode_allocator;
140  typedef typename __rebind_ina::pointer inode_pointer;
141  typedef typename __rebind_ina::const_pointer inode_const_pointer;
142 
143 
144  /// Conditional deallocator.
145  class cond_dealtor
146  {
147  protected:
148  leaf_pointer m_p_nd;
149  bool m_no_action_dtor;
150  bool m_call_destructor;
151 
152  public:
153  cond_dealtor(leaf_pointer p_nd)
154  : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false)
155  { }
156 
157  void
158  set_no_action_dtor()
159  { m_no_action_dtor = true; }
160 
161  void
162  set_call_destructor()
163  { m_call_destructor = true; }
164 
165  ~cond_dealtor()
166  {
167  if (m_no_action_dtor)
168  return;
169 
170  if (m_call_destructor)
171  m_p_nd->~leaf();
172 
173  s_leaf_allocator.deallocate(m_p_nd, 1);
174  }
175  };
176 
177 
178  /// Branch bag, for split-join.
179  class branch_bag
180  {
181  private:
182  typedef inode_pointer __inp;
183  typedef typename _Alloc::template rebind<__inp>::other __rebind_inp;
184 
185 #ifdef _GLIBCXX_DEBUG
186  typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> bag_type;
187 #else
188  typedef std::list<__inp, __rebind_inp> bag_type;
189 #endif
190 
191  bag_type m_bag;
192  public:
193  void
194  add_branch()
195  {
196  inode_pointer p_nd = s_inode_allocator.allocate(1);
197  __try
198  {
199  m_bag.push_back(p_nd);
200  }
201  __catch(...)
202  {
203  s_inode_allocator.deallocate(p_nd, 1);
204  __throw_exception_again;
205  }
206  }
207 
208  inode_pointer
209  get_branch()
210  {
211  _GLIBCXX_DEBUG_ASSERT(!m_bag.empty());
212  inode_pointer p_nd = *m_bag.begin();
213  m_bag.pop_front();
214  return p_nd;
215  }
216 
217  ~branch_bag()
218  {
219  while (!m_bag.empty())
220  {
221  inode_pointer p_nd = *m_bag.begin();
222  s_inode_allocator.deallocate(p_nd, 1);
223  m_bag.pop_front();
224  }
225  }
226 
227  inline bool
228  empty() const
229  { return m_bag.empty(); }
230  };
231 
232 #ifdef _GLIBCXX_DEBUG
233  typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
234 #endif
235 
236  typedef typename traits_type::null_node_update_pointer null_node_update_pointer;
237 
238  public:
239  typedef pat_trie_tag container_category;
240  typedef _Alloc allocator_type;
241  typedef typename _Alloc::size_type size_type;
242  typedef typename _Alloc::difference_type difference_type;
243 
244  typedef typename traits_base::key_type key_type;
245  typedef typename traits_base::key_pointer key_pointer;
246  typedef typename traits_base::key_const_pointer key_const_pointer;
247  typedef typename traits_base::key_reference key_reference;
248  typedef typename traits_base::key_const_reference key_const_reference;
249  typedef typename traits_base::mapped_type mapped_type;
250  typedef typename traits_base::mapped_pointer mapped_pointer;
251  typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
252  typedef typename traits_base::mapped_reference mapped_reference;
253  typedef typename traits_base::mapped_const_reference mapped_const_reference;
254  typedef typename traits_base::value_type value_type;
255  typedef typename traits_base::pointer pointer;
256  typedef typename traits_base::const_pointer const_pointer;
257  typedef typename traits_base::reference reference;
258  typedef typename traits_base::const_reference const_reference;
259 
260  typedef typename traits_type::access_traits access_traits;
261  typedef typename traits_type::const_iterator point_const_iterator;
262  typedef typename traits_type::iterator point_iterator;
263  typedef point_const_iterator const_iterator;
264  typedef point_iterator iterator;
265 
266  typedef typename traits_type::reverse_iterator reverse_iterator;
267  typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
268  typedef typename traits_type::node_const_iterator node_const_iterator;
269  typedef typename traits_type::node_iterator node_iterator;
270  typedef typename traits_type::node_update node_update;
271 
272  PB_DS_PAT_TRIE_NAME();
273 
274  PB_DS_PAT_TRIE_NAME(const access_traits&);
275 
276  PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&);
277 
278  void
279  swap(PB_DS_CLASS_C_DEC&);
280 
281  ~PB_DS_PAT_TRIE_NAME();
282 
283  inline bool
284  empty() const;
285 
286  inline size_type
287  size() const;
288 
289  inline size_type
290  max_size() const;
291 
292  access_traits&
293  get_access_traits();
294 
295  const access_traits&
296  get_access_traits() const;
297 
298  node_update&
299  get_node_update();
300 
301  const node_update&
302  get_node_update() const;
303 
305  insert(const_reference);
306 
307  inline mapped_reference
308  operator[](key_const_reference r_key)
309  {
310 #ifdef PB_DS_DATA_TRUE_INDICATOR
311  return insert(std::make_pair(r_key, mapped_type())).first->second;
312 #else
313  insert(r_key);
314  return traits_base::s_null_type;
315 #endif
316  }
317 
318  inline point_iterator
319  find(key_const_reference);
320 
321  inline point_const_iterator
322  find(key_const_reference) const;
323 
324  inline point_iterator
325  lower_bound(key_const_reference);
326 
327  inline point_const_iterator
328  lower_bound(key_const_reference) const;
329 
330  inline point_iterator
331  upper_bound(key_const_reference);
332 
333  inline point_const_iterator
334  upper_bound(key_const_reference) const;
335 
336  void
337  clear();
338 
339  inline bool
340  erase(key_const_reference);
341 
342  inline const_iterator
343  erase(const_iterator);
344 
345 #ifdef PB_DS_DATA_TRUE_INDICATOR
346  inline iterator
347  erase(iterator);
348 #endif
349 
350  inline const_reverse_iterator
351  erase(const_reverse_iterator);
352 
353 #ifdef PB_DS_DATA_TRUE_INDICATOR
354  inline reverse_iterator
355  erase(reverse_iterator);
356 #endif
357 
358  template<typename Pred>
359  inline size_type
360  erase_if(Pred);
361 
362  void
363  join(PB_DS_CLASS_C_DEC&);
364 
365  void
366  split(key_const_reference, PB_DS_CLASS_C_DEC&);
367 
368  inline iterator
369  begin();
370 
371  inline const_iterator
372  begin() const;
373 
374  inline iterator
375  end();
376 
377  inline const_iterator
378  end() const;
379 
380  inline reverse_iterator
381  rbegin();
382 
383  inline const_reverse_iterator
384  rbegin() const;
385 
386  inline reverse_iterator
387  rend();
388 
389  inline const_reverse_iterator
390  rend() const;
391 
392  /// Returns a const node_iterator corresponding to the node at the
393  /// root of the tree.
394  inline node_const_iterator
395  node_begin() const;
396 
397  /// Returns a node_iterator corresponding to the node at the
398  /// root of the tree.
399  inline node_iterator
400  node_begin();
401 
402  /// Returns a const node_iterator corresponding to a node just
403  /// after a leaf of the tree.
404  inline node_const_iterator
405  node_end() const;
406 
407  /// Returns a node_iterator corresponding to a node just
408  /// after a leaf of the tree.
409  inline node_iterator
410  node_end();
411 
412 #ifdef PB_DS_PAT_TRIE_TRACE_
413  void
414  trace() const;
415 #endif
416 
417  protected:
418  template<typename It>
419  void
420  copy_from_range(It, It);
421 
422  void
423  value_swap(PB_DS_CLASS_C_DEC&);
424 
425  node_pointer
426  recursive_copy_node(node_const_pointer);
427 
428  private:
429  void
430  initialize();
431 
432  inline void
433  apply_update(node_pointer, null_node_update_pointer);
434 
435  template<typename Node_Update_>
436  inline void
437  apply_update(node_pointer, Node_Update_*);
438 
439  bool
440  join_prep(PB_DS_CLASS_C_DEC&, branch_bag&);
441 
442  void
443  rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&);
444 
445  void
446  rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&);
447 
448  void
449  rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&);
450 
451  void
452  rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&);
453 
454  void
455  rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&);
456 
457  node_pointer
458  rec_join(node_pointer, node_pointer, size_type, branch_bag&);
459 
460  node_pointer
461  rec_join(leaf_pointer, leaf_pointer, branch_bag&);
462 
463  node_pointer
464  rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&);
465 
466  node_pointer
467  rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&);
468 
469  node_pointer
470  rec_join(inode_pointer, inode_pointer, branch_bag&);
471 
472  size_type
473  keys_diff_ind(typename access_traits::const_iterator,
474  typename access_traits::const_iterator,
475  typename access_traits::const_iterator,
476  typename access_traits::const_iterator);
477 
478  inode_pointer
479  insert_branch(node_pointer, node_pointer, branch_bag&);
480 
481  void
482  update_min_max_for_inserted_leaf(leaf_pointer);
483 
484  void
485  erase_leaf(leaf_pointer);
486 
487  inline void
488  actual_erase_leaf(leaf_pointer);
489 
490  void
491  clear_imp(node_pointer);
492 
493  void
494  erase_fixup(inode_pointer);
495 
496  void
497  update_min_max_for_erased_leaf(leaf_pointer);
498 
499  static inline a_const_iterator
500  pref_begin(node_const_pointer);
501 
502  static inline a_const_iterator
503  pref_end(node_const_pointer);
504 
505  inline node_pointer
506  find_imp(key_const_reference);
507 
508  inline node_pointer
509  lower_bound_imp(key_const_reference);
510 
511  inline node_pointer
512  upper_bound_imp(key_const_reference);
513 
514  inline static leaf_const_pointer
515  leftmost_descendant(node_const_pointer);
516 
517  inline static leaf_pointer
518  leftmost_descendant(node_pointer);
519 
520  inline static leaf_const_pointer
521  rightmost_descendant(node_const_pointer);
522 
523  inline static leaf_pointer
524  rightmost_descendant(node_pointer);
525 
526 #ifdef _GLIBCXX_DEBUG
527  void
528  assert_valid(const char*, int) const;
529 
530  void
531  assert_iterators(const char*, int) const;
532 
533  void
534  assert_reverse_iterators(const char*, int) const;
535 
536  static size_type
537  recursive_count_leafs(node_const_pointer, const char*, int);
538 #endif
539 
540 #ifdef PB_DS_PAT_TRIE_TRACE_
541  static void
542  trace_node(node_const_pointer, size_type);
543 
544  template<typename Metadata_>
545  static void
546  trace_node_metadata(node_const_pointer, type_to_type<Metadata_>);
547 
548  static void
549  trace_node_metadata(node_const_pointer, type_to_type<null_type>);
550 #endif
551 
552  leaf_pointer
553  split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&);
554 
555  node_pointer
556  rec_split(node_pointer, a_const_iterator, a_const_iterator,
557  PB_DS_CLASS_C_DEC&, branch_bag&);
558 
559  void
560  split_insert_branch(size_type, a_const_iterator, inode_iterator,
561  size_type, branch_bag&);
562 
563  static head_allocator s_head_allocator;
564  static inode_allocator s_inode_allocator;
565  static leaf_allocator s_leaf_allocator;
566 
567  head_pointer m_p_head;
568  size_type m_size;
569  };
570 
571 #define PB_DS_ASSERT_NODE_VALID(X) \
572  _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);)
573 
574 #define PB_DS_RECURSIVE_COUNT_LEAFS(X) \
575  recursive_count_leafs(X, __FILE__, __LINE__)
576 
588 
589 #undef PB_DS_RECURSIVE_COUNT_LEAFS
590 #undef PB_DS_ASSERT_NODE_VALID
591 #undef PB_DS_CLASS_C_DEC
592 #undef PB_DS_CLASS_T_DEC
593 #undef PB_DS_PAT_TRIE_NAME
594 #undef PB_DS_PAT_TRIE_TRAITS_BASE
595 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
596  } // namespace detail
597 } // namespace __gnu_pbds