Viewing file:  aatree.h (4.9 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/* Copyright (C) 2009-2022 Free Software Foundation, Inc.
Contributed by Richard Henderson <rth@redhat.com>.
This file is part of the GNU Transactional Memory Library (libitm).
Libitm is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for
more details.
Under Section 7 of GPL version 3, you are granted additional
permissions described in the GCC Runtime Library Exception, version
3.1, as published by the Free Software Foundation.
You should have received a copy of the GNU General Public License and
a copy of the GCC Runtime Library Exception along with this program;
see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
<http://www.gnu.org/licenses/>. */
/* Implements an AA tree (http://en.wikipedia.org/wiki/AA_tree) with an
integer key, and data attached to the node via flexible array member. */
#ifndef LIBITM_AATREE_H
#define LIBITM_AATREE_H 1
namespace GTM HIDDEN {
template<typename KEY> class aa_tree_key;
class aa_node_base
{
public:
static const bool L = false;
static const bool R = true;
private:
typedef unsigned int level_type;
aa_node_base *m_link[2];
level_type m_level;
static const aa_node_base s_nil;
public:
aa_node_base(level_type l = 1)
: m_link { const_cast<aa_node_base *>(&s_nil),
const_cast<aa_node_base *>(&s_nil) },
m_level(l)
{ }
bool is_nil() const { return this == &s_nil; }
aa_node_base * link(bool d) { return m_link[d]; }
void set_link(bool d, aa_node_base *val) { m_link[d] = val; }
aa_node_base *skew();
aa_node_base *split();
void decrease_level();
static void *operator new (size_t s) { return xmalloc (s); }
static void operator delete (void *p) { free (p); }
};
template<typename KEY>
struct aa_node_key : public aa_node_base
{
typedef aa_node_base base;
KEY key;
explicit aa_node_key(KEY k) : key(k) { }
aa_node_key * link(bool d)
{
return static_cast<aa_node_key *>(base::link(d));
}
aa_node_key *skew() { return static_cast<aa_node_key *>(base::skew()); }
aa_node_key *split() { return static_cast<aa_node_key *>(base::split()); }
};
template<typename KEY, typename DATA>
struct aa_node : public aa_node_key<KEY>
{
typedef aa_node_key<KEY> base;
DATA data;
explicit aa_node(KEY k) : base(k) { }
aa_node * link(bool d)
{
return static_cast<aa_node *>(base::link(d));
}
};
template<typename KEY>
class aa_tree_key
{
public:
typedef aa_node_key<KEY> node;
typedef node *node_ptr;
protected:
node_ptr m_tree;
protected:
aa_tree_key() : m_tree(0) { }
node_ptr find(KEY k) const;
static node_ptr insert_1 (node_ptr t, node_ptr n);
void insert(node_ptr n);
static node_ptr erase_1 (node_ptr t, KEY k, node_ptr *pfree);
node_ptr erase(KEY k);
};
extern template class aa_tree_key<uintptr_t>;
template<typename KEY, typename DATA>
class aa_tree : public aa_tree_key<KEY>
{
public:
typedef aa_tree_key<KEY> base;
typedef aa_node<KEY, DATA> node;
typedef node *node_ptr;
typedef void (*trav_callback)(KEY, DATA *, void *);
private:
static void clear_1 (node_ptr);
static void traverse_1 (node_ptr, trav_callback, void *);
public:
aa_tree() = default;
~aa_tree() { clear(); }
static void *operator new (size_t s, aa_tree<KEY, DATA>* p) { return p; }
DATA *find(KEY k) const
{
node_ptr n = static_cast<node_ptr>(base::find (k));
return n ? &n->data : 0;
}
DATA *insert(KEY k)
{
node_ptr n = new node(k);
base::insert(n);
return &n->data;
}
void erase(KEY k)
{
node_ptr n = static_cast<node_ptr>(base::erase (k));
delete n;
}
node_ptr remove(KEY k, DATA** data)
{
node_ptr n = static_cast<node_ptr>(base::erase (k));
*data = (n ? &n->data : 0);
return n;
}
void clear()
{
node_ptr n = static_cast<node_ptr>(this->m_tree);
if (n)
{
this->m_tree = 0;
clear_1 (n);
}
}
void traverse (trav_callback cb, void *cb_data)
{
node_ptr t = static_cast<node_ptr>(this->m_tree);
if (t != 0)
traverse_1 (t, cb, cb_data);
}
};
template<typename KEY, typename DATA>
void
aa_tree<KEY, DATA>::clear_1 (node_ptr t)
{
if (t->is_nil())
return;
clear_1 (t->link(node::L));
clear_1 (t->link(node::R));
delete t;
}
template<typename KEY, typename DATA>
void
aa_tree<KEY, DATA>::traverse_1 (node_ptr t, trav_callback cb, void *cb_data)
{
if (t->is_nil())
return;
cb (t->key, &t->data, cb_data);
traverse_1 (t->link(node::L), cb, cb_data);
traverse_1 (t->link(node::R), cb, cb_data);
}
} // namespace GTM
#endif // LIBITM_AATREE_H
|
