libitm/aatree.h

   1 /* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
   2    Contributed by Richard Henderson <rth@redhat.com>.
   3
   4    This file is part of the GNU Transactional Memory Library (libitm).
   5
   6    Libitm is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
  12    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14    more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 /* Implements an AA tree (http://en.wikipedia.org/wiki/AA_tree) with an
  26    integer key, and data attached to the node via flexible array member.  */
  27
  28 #ifndef LIBITM_AATREE_H
  29 #define LIBITM_AATREE_H 1
  30
  31 namespace GTM HIDDEN {
  32
  33 template<typename KEY> class aa_tree_key;
  34
  35 class aa_node_base
  36 {
  37  public:
  38   static const bool L = false;
  39   static const bool R = true;
  40
  41  private:
  42   typedef unsigned int level_type;
  43
  44   aa_node_base *m_link[2];
  45   level_type m_level;
  46
  47   static const aa_node_base s_nil;
  48
  49  public:
  50   aa_node_base(level_type l = 1)
  51     : m_link { const_cast<aa_node_base *>(&s_nil),
  52                const_cast<aa_node_base *>(&s_nil) },
  53       m_level(l)
  54   { }
  55
  56   bool is_nil() const { return this == &s_nil; }
  57
  58   aa_node_base * link(bool d) { return m_link[d]; }
  59   void set_link(bool d, aa_node_base *val) { m_link[d] = val; }
  60
  61   aa_node_base *skew();
  62   aa_node_base *split();
  63   void decrease_level();
  64
  65   static void *operator new (size_t s) { return xmalloc (s); }
  66   static void operator delete (void *p) { free (p); }
  67 };
  68
  69 template<typename KEY>
  70 struct aa_node_key : public aa_node_base
  71 {
  72   typedef aa_node_base base;
  73
  74   KEY key;
  75
  76   explicit aa_node_key(KEY k) : key(k) { }
  77
  78   aa_node_key * link(bool d)
  79   {
  80     return static_cast<aa_node_key *>(base::link(d));
  81   }
  82
  83   aa_node_key *skew() { return static_cast<aa_node_key *>(base::skew()); }
  84   aa_node_key *split() { return static_cast<aa_node_key *>(base::split()); }
  85 };
  86
  87 template<typename KEY, typename DATA>
  88 struct aa_node : public aa_node_key<KEY>
  89 {
  90   typedef aa_node_key<KEY> base;
  91
  92   DATA data;
  93
  94   explicit aa_node(KEY k) : base(k) { }
  95
  96   aa_node * link(bool d)
  97   {
  98     return static_cast<aa_node *>(base::link(d));
  99   }
 100 };
 101
 102 template<typename KEY>
 103 class aa_tree_key
 104 {
 105  public:
 106   typedef aa_node_key<KEY> node;
 107   typedef node *node_ptr;
 108
 109  protected:
 110   node_ptr m_tree;
 111
 112  protected:
 113   aa_tree_key() : m_tree(0) { }
 114
 115   node_ptr find(KEY k) const;
 116
 117   static node_ptr insert_1 (node_ptr t, node_ptr n);
 118   void insert(node_ptr n);
 119
 120   static node_ptr erase_1 (node_ptr t, KEY k, node_ptr *pfree);
 121   node_ptr erase(KEY k);
 122 };
 123
 124 extern template class aa_tree_key<uintptr_t>;
 125
 126 template<typename KEY, typename DATA>
 127 class aa_tree : public aa_tree_key<KEY>
 128 {
 129  public:
 130   typedef aa_tree_key<KEY> base;
 131   typedef aa_node<KEY, DATA> node;
 132   typedef node *node_ptr;
 133
 134   typedef void (*trav_callback)(KEY, DATA *, void *);
 135
 136  private:
 137   static void clear_1 (node_ptr);
 138   static void traverse_1 (node_ptr, trav_callback, void *);
 139
 140  public:
 141   aa_tree() = default;
 142   ~aa_tree() { clear(); }
 143
 144   static void *operator new (size_t s, aa_tree<KEY, DATA>* p) { return p; }
 145
 146   DATA *find(KEY k) const
 147   {
 148     node_ptr n = static_cast<node_ptr>(base::find (k));
 149     return n ? &n->data : 0;
 150   }
 151
 152   DATA *insert(KEY k)
 153   {
 154     node_ptr n = new node(k);
 155     base::insert(n);
 156     return &n->data;
 157   }
 158
 159   void erase(KEY k)
 160   {
 161     node_ptr n = static_cast<node_ptr>(base::erase (k));
 162     delete n;
 163   }
 164
 165   node_ptr remove(KEY k, DATA** data)
 166   {
 167     node_ptr n = static_cast<node_ptr>(base::erase (k));
 168     *data = (n ? &n->data : 0);
 169     return n;
 170   }
 171
 172   void clear()
 173   {
 174     node_ptr n = static_cast<node_ptr>(this->m_tree);
 175     if (n)
 176       {
 177         this->m_tree = 0;
 178         clear_1 (n);
 179       }
 180   }
 181
 182   void traverse (trav_callback cb, void *cb_data)
 183   {
 184     node_ptr t = static_cast<node_ptr>(this->m_tree);
 185     if (t != 0)
 186       traverse_1 (t, cb, cb_data);
 187   }
 188 };
 189
 190
 191 template<typename KEY, typename DATA>
 192 void
 193 aa_tree<KEY, DATA>::clear_1 (node_ptr t)
 194 {
 195   if (t->is_nil())
 196     return;
 197   clear_1 (t->link(node::L));
 198   clear_1 (t->link(node::R));
 199   delete t;
 200 }
 201
 202 template<typename KEY, typename DATA>
 203 void
 204 aa_tree<KEY, DATA>::traverse_1 (node_ptr t, trav_callback cb, void *cb_data)
 205 {
 206   if (t->is_nil())
 207     return;
 208   cb (t->key, &t->data, cb_data);
 209   traverse_1 (t->link(node::L), cb, cb_data);
 210   traverse_1 (t->link(node::R), cb, cb_data);
 211 }
 212
 213 } // namespace GTM
 214
 215 #endif // LIBITM_AATREE_H