00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef SYMNODE_H_
00019 #define SYMNODE_H_
00020
00021 #include <cassert>
00022
00023 #if __GNUC__ >= 3
00024 #include <backward/hash_map.h>
00025 #elif __GNUC__ < 3
00026 #include <hash_map.h>
00027 using std::hash_map;
00028 #endif
00029
00030
00031 struct UniqueNodeStats { virtual ~UniqueNodeStats(){} };
00032
00033 #include "SymImpl.h"
00034 #include "token.h"
00035
00036 #if __GNUC__ == 4
00037 #define USE_TR1 1
00038 #else
00039 #define USE_TR1 0
00040 #endif
00041
00042 #undef USE_TR1
00043 #define USE_TR1 0
00044
00045 #if USE_TR1
00046 #include <tr1/unordered_map>
00047 typedef std::tr1::unordered_map<detail::SymKey, detail::SymValue, detail::SymKey::Hash> SymMap;
00048 #else
00049 typedef hash_map<detail::SymKey, detail::SymValue, detail::SymKey::Hash> SymMap;
00050 #endif
00051
00052 typedef SymMap::iterator SymIterator;
00053
00054
00055
00056 class Sym
00057 {
00058 public:
00059
00060 Sym() : node(dag.end()) {}
00061 explicit Sym(token_t token, const SymVec& args);
00062 explicit Sym(token_t token, const Sym& args);
00063 explicit Sym(token_t var);
00064
00065 explicit Sym(SymIterator it) : node(it) { incref(); }
00066
00067 Sym(const Sym& oth) : node(oth.node) { incref(); }
00068 ~Sym() { decref(); }
00069
00070 const Sym& operator=(const Sym& oth) {
00071 if (oth.node == node) return *this;
00072 decref();
00073 node = oth.node;
00074 incref();
00075 return *this;
00076 }
00077
00078
00079 UniqueNodeStats* extra_stats() const { return empty()? 0 : node->second.uniqueNodeStats; }
00080
00081 int hashcode() const { return node->first.get_hash_code(); }
00082
00083
00084 friend struct detail::SymKey::Hash;
00085 friend struct detail::SymKey;
00086
00087 unsigned refcount() const { return empty()? 0: node->second.refcount; }
00088
00089 bool operator==(const Sym& other) const {
00090 return node == other.node;
00091 }
00092 bool operator!=(const Sym& other) const { return !(*this == other); }
00093
00094 bool empty() const { return node == dag.end(); }
00095
00096
00097 unsigned arity() const { return node->first.arity(); }
00098 token_t token() const { return node->first.token; }
00099
00100 const SymVec& args() const { return node->first.vec(); }
00101
00102
00103 unsigned size() const { return empty()? 0 : node->second.size; }
00104 unsigned depth() const { return empty()? 0 : node->second.depth; }
00105
00106 SymMap::iterator iterator() const { return node; }
00107
00108
00109 static SymMap& get_dag() { return dag; }
00110
00111
00112
00113 static void set_factory_function(UniqueNodeStats* (*f)(const Sym&)) { factory=f; }
00114 static void clear_factory_function() { factory = 0; }
00115
00116 static const std::vector<unsigned>& token_refcount() { return token_count; }
00117
00118 unsigned address() const { return reinterpret_cast<unsigned>(&*node); }
00119
00120 private :
00121
00122
00123 Sym private_get(size_t w) const;
00124
00125 unsigned __unchecked_refcount() const { return node->second.refcount; }
00126
00127 void incref() {
00128 if (!empty()) {
00129 ++(node->second.refcount);
00130 ++token_count[token()];
00131 }
00132 }
00133 void decref() {
00134 if (!empty()) {
00135 --token_count[token()];
00136 if (--(node->second.refcount) == 0) {
00137 dag.erase(node);
00138 }
00139 }
00140 }
00141
00142
00143 SymIterator node;
00144
00145
00146 static SymMap dag;
00147
00148 static std::vector<unsigned> token_count;
00149
00150
00151 static UniqueNodeStats* (*factory)(const Sym&);
00152
00153 };
00154
00155
00156 class HashSym {
00157 public:
00158 int operator()(const Sym& sym) const { return sym.hashcode(); }
00159 };
00160
00161
00162
00163
00164 Sym get_subtree(const Sym& org, size_t w);
00165
00166
00167 Sym insert_subtree(const Sym& org, size_t w, const Sym& nw);
00168
00169
00170 inline Sym next(const Sym& sym) {
00171 SymIterator it = sym.iterator();
00172 ++it;
00173 if (it == Sym::get_dag().end()) it = Sym::get_dag().begin();
00174 return Sym(it);
00175 }
00176
00177 #endif