summaryrefslogtreecommitdiff
path: root/storage
diff options
context:
space:
mode:
Diffstat (limited to 'storage')
-rw-r--r--storage/oqgraph/Makefile.am8
-rw-r--r--storage/oqgraph/graphcore-graph.cc28
-rw-r--r--storage/oqgraph/graphcore-graph.h221
-rw-r--r--storage/oqgraph/graphcore-types.h6
-rw-r--r--storage/oqgraph/graphcore.cc334
-rw-r--r--storage/oqgraph/graphcore.h2
-rw-r--r--storage/oqgraph/ha_oqgraph.cc727
-rw-r--r--storage/oqgraph/ha_oqgraph.h22
-rw-r--r--storage/oqgraph/oqgraph_judy.cc113
-rw-r--r--storage/oqgraph/oqgraph_judy.h109
-rw-r--r--storage/oqgraph/oqgraph_shim.cc28
-rw-r--r--storage/oqgraph/oqgraph_shim.h735
-rw-r--r--storage/oqgraph/oqgraph_thunk.cc975
-rw-r--r--storage/oqgraph/oqgraph_thunk.h415
14 files changed, 3044 insertions, 679 deletions
diff --git a/storage/oqgraph/Makefile.am b/storage/oqgraph/Makefile.am
index e99e134db02..95884623732 100644
--- a/storage/oqgraph/Makefile.am
+++ b/storage/oqgraph/Makefile.am
@@ -54,13 +54,13 @@ EXTRA_DIST = ha_oqgraph.h ha_oqgraph.cc graphcore.cc \
# DTRACEFILES = .libs/libha_oqgraph_la-ha_oqgraph.o
ORIG_CXXFLAGS = @CXXFLAGS@
-CXXFLAGS=
+CXXFLAGS= -DBOOST_ALL_NO_LIB=1
noinst_HEADERS = ha_oqgraph.h \
graphcore-graph.h graphcore-types.h graphcore.h
# oqgraph_probes.h
noinst_LTLIBRARIES = libgraphcore.la
-libgraphcore_la_SOURCES = graphcore.cc
+libgraphcore_la_SOURCES = graphcore.cc graphcore-graph.cc oqgraph_shim.cc oqgraph_thunk.cc
libgraphcore_la_CXXFLAGS = $(ORIG_CXXFLAGS) $(BOOST_CXXFLAGS)
if BUILD_OQGRAPH_FOR_MYSQL
@@ -73,14 +73,14 @@ endif !BUILD_OQGRAPH_STANDALONE
EXTRA_LTLIBRARIES = ha_oqgraph.la
mysqlplugin_LTLIBRARIES = @plugin_oqgraph_shared_target@
-ha_oqgraph_la_SOURCES = ha_oqgraph.cc
+ha_oqgraph_la_SOURCES = ha_oqgraph.cc oqgraph_judy.cc
ha_oqgraph_la_LIBADD = libgraphcore.la
# if HAVE_DTRACE
# ha_oqgraph_la_LIBADD += oqgraph_probes.o
# endif
-ha_oqgraph_la_LDFLAGS = -shared -module -rpath $(mysqlplugindir)
+ha_oqgraph_la_LDFLAGS = -shared -module -rpath $(mysqlplugindir) -lJudy -Wl,-flat_namespace
ha_oqgraph_la_CFLAGS = $(ORIG_CFLAGS) -DMYSQL_DYNAMIC_PLUGIN
ha_oqgraph_la_CXXFLAGS = $(ORIG_CXXFLAGS) -DMYSQL_DYNAMIC_PLUGIN
diff --git a/storage/oqgraph/graphcore-graph.cc b/storage/oqgraph/graphcore-graph.cc
new file mode 100644
index 00000000000..2160c000922
--- /dev/null
+++ b/storage/oqgraph/graphcore-graph.cc
@@ -0,0 +1,28 @@
+/* Copyright (C) 2009-2011 Arjen G Lentz & Antony T Curtis for Open Query
+
+ This program 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; version 2 of the License, or
+ (at your option) any later version.
+
+ This program 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.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/* ======================================================================
+ Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+ Mk.III implementation by Antony Curtis & Arjen Lentz
+ For more information, documentation, support, enhancement engineering,
+ and non-GPL licensing, see http://openquery.com/graph
+ or contact graph@openquery.com
+ For packaged binaries, see http://ourdelta.org
+ ======================================================================
+*/
+
+#include "graphcore-graph.h"
+
diff --git a/storage/oqgraph/graphcore-graph.h b/storage/oqgraph/graphcore-graph.h
index 46ddfb5335b..fb3b4b987e0 100644
--- a/storage/oqgraph/graphcore-graph.h
+++ b/storage/oqgraph/graphcore-graph.h
@@ -27,22 +27,209 @@
#ifndef oq_graphcore_graph_h_
#define oq_graphcore_graph_h_
-typedef adjacency_list
-<
- vecS,
- vecS,
- bidirectionalS,
- VertexInfo,
- EdgeInfo
-> Graph;
-
-#define GRAPH_WEIGHTMAP(G) get(&EdgeInfo::weight, G)
-typedef property_map<Graph, EdgeWeight EdgeInfo::*>::type weightmap_type;
-
-#define GRAPH_INDEXMAP(G) get(vertex_index, G)
-typedef property_map<Graph, vertex_index_t>::type indexmap_type;
-
-#define GRAPH_IDMAP(G) get(&VertexInfo::id, G)
-typedef property_map<Graph, VertexID VertexInfo::*>::type idmap_type;
+#include "oqgraph_shim.h"
+
+#include <boost/graph/two_bit_color_map.hpp>
+
+namespace boost
+{
+ typedef oqgraph3::graph Graph;
+
+ template <>
+ struct hash<graph_traits<oqgraph3::graph>::vertex_descriptor>
+ : public std::unary_function<
+ graph_traits<oqgraph3::graph>::vertex_descriptor, std::size_t>
+ {
+ std::size_t operator()(
+ const graph_traits<oqgraph3::graph>::vertex_descriptor& v) const
+ {
+ return boost::hash_value(v->id);
+ }
+ };
+
+ template<typename IndexMap = identity_property_map>
+ struct two_bit_judy_map
+ {
+ typedef typename property_traits<IndexMap>::key_type key_type;
+ typedef two_bit_color_type value_type;
+ typedef void reference;
+ typedef read_write_property_map_tag category;
+
+ open_query::judy_bitset msb;
+ open_query::judy_bitset lsb;
+ IndexMap index;
+
+ two_bit_judy_map(const IndexMap& i)
+ : index(i)
+ { }
+
+ friend two_bit_color_type get(
+ const two_bit_judy_map<IndexMap>& pm,
+ typename property_traits<IndexMap>::key_type key)
+ {
+ typename property_traits<IndexMap>::value_type i = get(pm.index, key);
+ return two_bit_color_type((2*int(pm.msb.test(i))) | int(pm.lsb.test(i)));
+ }
+
+ friend void put(
+ two_bit_judy_map<IndexMap>& pm,
+ typename property_traits<IndexMap>::key_type key,
+ two_bit_color_type value)
+ {
+ typename property_traits<IndexMap>::value_type i = get(pm.index, key);
+ pm.msb.set(i, value & 2);
+ pm.lsb.set(i, value & 1);
+ }
+ };
+
+ template<typename IndexMap>
+ inline two_bit_judy_map<IndexMap>
+ make_two_bit_judy_map(const IndexMap& index)
+ {
+ return two_bit_judy_map<IndexMap>(index);
+ }
+
+
+ template <typename Type>
+ struct default_lazy_initializer
+ {
+ template <typename Key>
+ Type operator()(const Key&) const { return Type(); }
+ };
+
+ template <typename Type>
+ struct copy_initializer
+ {
+ copy_initializer(const Type& value) : _(value) { }
+ template <typename Key>
+ const Type& operator()(const Key&) const { return _; }
+ const Type& _;
+ };
+
+ template <typename Type>
+ copy_initializer<Type> make_copy_initializer(const Type& value)
+ { return copy_initializer<Type>(value); }
+
+
+ template <typename Type>
+ struct value_initializer
+ {
+ value_initializer(const Type& value) : _(value) { }
+ template <typename Key>
+ const Type& operator()(const Key&) const { return _; }
+ const Type _;
+ };
+
+ template <typename Type>
+ value_initializer<Type> make_value_initializer(const Type& value)
+ { return value_initializer<Type>(value); }
+
+
+ template <typename Key>
+ struct identity_initializer
+ {
+ const Key& operator()(const Key& _) const { return _; }
+ };
+
+ template <class Container, class Generator>
+ struct lazy_property_map
+ {
+ typedef lazy_property_map<Container, Generator> self;
+ typedef typename Container::key_type key_type;
+ typedef typename Container::value_type::second_type value_type;
+ typedef value_type& reference;
+ typedef lvalue_property_map_tag category;
+
+ lazy_property_map(Container& m, Generator g= Generator())
+ : _m(m)
+ , _g(g)
+ { }
+
+ reference operator[](const key_type& k) const
+ {
+ typename Container::iterator found= _m.find(k);
+ if (_m.end() == found)
+ {
+ found= _m.insert(std::make_pair(k, _g(k))).first;
+ }
+ return found->second;
+ }
+
+ void set(const key_type& k, const value_type& v)
+ { _m[k] = v; }
+
+ friend reference get(const self& s, const key_type& k)
+ {
+ return s[k];
+ }
+
+ friend void put(self& s, const key_type& k, const value_type& v)
+ { s.set(k, v); }
+
+ Container& _m;
+ Generator _g;
+ };
+
+ template <class Container, class Generator>
+ lazy_property_map<Container, Generator>
+ make_lazy_property_map(Container& c, Generator g)
+ { return lazy_property_map<Container, Generator>(c, g); }
+
+#if 0
+
+ struct map_wra
+
+
+ struct property_traits< unordered_map_wrapper<K,T,H,P,A
+
+
+
+ template <class K, class T, class H, class P, class A>
+ struct property_traits< unordered_map<K,T,H,P,A> > {
+ typedef T value_type;
+ typedef K key_type;
+ typedef T& reference;
+ struct category
+ : public read_write_property_map_tag
+ , public lvalue_property_map_tag
+ { };
+
+ friend reference get(
+ unordered_map<K,T,H,P,A>& m,
+ const key_type& k)
+ {
+ return m[k];
+ }
+
+ friend void put(
+ unordered_map<K,T,H,P,A>& m,
+ const key_type& k,
+ const value_type& v)
+ {
+ m[k]= v;
+ }
+ };
+
+ //template <class K, class T, class H, class P, class A>
+ //property_traits< unordered_map<K,T,H,P,A> >::reference
+ //get(unordered_map<K,T,H,P,A>& m,
+ // const property_traits< unordered_map<K,T,H,P,A> >::key_type& k)
+ //{ return m[ k ]; }
+
+ //template <class K, class T, class H, class P, class A>
+ //void put(
+ // unordered_map<K,T,H,P,A>& m,
+ // const property_traits< unordered_map<K,T,H,P,A> >::key_type& k,
+ // const property_traits< unordered_map<K,T,H,P,A> >::value_type& v)
+ //{ m[ k ] = v; }
+
+ //template <class K, class T, class H, class P, class A>
+ //property_traits< unordered_map<K,T,H,P,A>::reference
+ //get(unordered_map<K,T,H,P,A>& m,
+ // const graph_traits<oqgraph3::graph>::vertex_descriptor& v)
+ //{ return m[ v->id ]; }
+#endif
+
+}
#endif
diff --git a/storage/oqgraph/graphcore-types.h b/storage/oqgraph/graphcore-types.h
index 7a7e4c62729..6a25182e28b 100644
--- a/storage/oqgraph/graphcore-types.h
+++ b/storage/oqgraph/graphcore-types.h
@@ -26,6 +26,7 @@
#ifndef oq_graphcore_types_h_
#define oq_graphcore_types_h_
+
namespace open_query
{
@@ -33,4 +34,9 @@ namespace open_query
typedef double EdgeWeight;
}
+
+
+class Field;
+typedef struct st_table TABLE;
+
#endif
diff --git a/storage/oqgraph/graphcore.cc b/storage/oqgraph/graphcore.cc
index 0b856ac253f..f57f7507e82 100644
--- a/storage/oqgraph/graphcore.cc
+++ b/storage/oqgraph/graphcore.cc
@@ -30,14 +30,13 @@
#include <boost/config.hpp>
+#include "graphcore-graph.h"
+
#include <set>
#include <stack>
#include <boost/property_map/property_map.hpp>
-#include <boost/graph/graph_concepts.hpp>
-#include <boost/graph/graph_archetypes.hpp>
-#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/iteration_macros.hpp>
@@ -46,6 +45,8 @@
#include "graphcore.h"
+#include <boost/unordered_map.hpp>
+
using namespace open_query;
using namespace boost;
@@ -53,46 +54,6 @@ static const row empty_row = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
namespace open_query
{
- enum vertex_id_t { vertex_id };
-
- struct VertexInfo {
- inline VertexInfo() { }
-
- inline VertexInfo(VertexID _id)
- : id(_id) { }
-
- VertexID id;
- };
-
- struct EdgeInfo {
- EdgeWeight weight;
- };
-}
-
-namespace boost
-{
- BOOST_INSTALL_PROPERTY(vertex, id);
-
- namespace graph
- {
- template<>
- struct internal_vertex_name<VertexInfo>
- {
- typedef multi_index::member<VertexInfo, VertexID, &VertexInfo::id> type;
- };
-
- template<>
- struct internal_vertex_constructor<VertexInfo>
- {
- typedef vertex_from_name<VertexInfo> type;
- };
- }
-}
-
-namespace open_query
-{
-
- #include "graphcore-graph.h"
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;
@@ -261,18 +222,15 @@ namespace open_query {
public:
Graph g;
- weightmap_type weightmap;
- idmap_type idmap;
- indexmap_type indexmap;
-
optional<Vertex> find_vertex(VertexID id) const;
optional<Edge> find_edge(Vertex, Vertex) const;
- inline oqgraph_share() throw()
- : g(),
- weightmap(GRAPH_WEIGHTMAP(g)),
- idmap(GRAPH_IDMAP(g)),
- indexmap(GRAPH_INDEXMAP(g))
+ inline oqgraph_share(
+ TABLE* table,
+ Field* origid,
+ Field* destid,
+ Field* weight) throw()
+ : g(table, origid, destid, weight)
{ }
inline ~oqgraph_share()
{ }
@@ -360,13 +318,13 @@ namespace open_query {
}
};
+ template <typename P, typename D>
struct GRAPHCORE_INTERNAL oqgraph_visit_dist
- : public base_visitor<oqgraph_visit_dist>
+ : public base_visitor< oqgraph_visit_dist<P,D> >
{
typedef on_finish_vertex event_filter;
- oqgraph_visit_dist(std::vector<Vertex>::iterator p,
- std::vector<EdgeWeight>::iterator d,
+ oqgraph_visit_dist(const P& p, const D& d,
stack_cursor *cursor)
: seq(0), m_cursor(*cursor), m_p(p), m_d(d)
{ assert(cursor); }
@@ -374,22 +332,28 @@ namespace open_query {
template<class T, class Graph>
void operator()(T u, Graph &g)
{
- m_cursor.results.push(reference(++seq, u, m_d[GRAPH_INDEXMAP(g)[u]]));
+ m_cursor.results.push(reference(++seq, u, m_d[ u ]));
}
private:
int seq;
stack_cursor &m_cursor;
- std::vector<Vertex>::iterator m_p;
- std::vector<EdgeWeight>::iterator m_d;
+ P m_p;
+ D m_d;
};
- template<bool record_weight, typename goal_filter>
+ template <typename P, typename D>
+ oqgraph_visit_dist<P,D>
+ make_oqgraph_visit_dist(const P& p, const D& d, stack_cursor *cursor)
+ { return oqgraph_visit_dist<P,D>(p, d, cursor); }
+
+
+ template<bool record_weight, typename goal_filter, typename P>
struct GRAPHCORE_INTERNAL oqgraph_goal
- : public base_visitor<oqgraph_goal<record_weight,goal_filter> >
+ : public base_visitor<oqgraph_goal<record_weight,goal_filter,P> >
{
typedef goal_filter event_filter;
- oqgraph_goal(Vertex goal, std::vector<Vertex>::iterator p,
+ oqgraph_goal(const Vertex& goal, const P& p,
stack_cursor *cursor)
: m_goal(goal), m_cursor(*cursor), m_p(p)
{ assert(cursor); }
@@ -400,17 +364,16 @@ namespace open_query {
if (u == m_goal)
{
int seq= 0;
- indexmap_type indexmap= GRAPH_INDEXMAP(g);
for (Vertex q, v= u;; v = q, seq++)
- if ((q= m_p[ indexmap[v] ]) == v)
+ if ((q= m_p[ v ]) == v)
break;
for (Vertex v= u;; u= v)
{
optional<Edge> edge;
optional<EdgeWeight> weight;
- v= m_p[ indexmap[u] ];
+ v= m_p[ u ];
if (record_weight && u != v)
{
typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
@@ -419,7 +382,7 @@ namespace open_query {
if (target(*ei, g) == u)
{
edge= *ei;
- weight= GRAPH_WEIGHTMAP(g)[*ei];
+ weight= get(boost::edge_weight, g, *ei);
break;
}
}
@@ -437,8 +400,14 @@ namespace open_query {
private:
Vertex m_goal;
stack_cursor &m_cursor;
- std::vector<Vertex>::iterator m_p;
+ P m_p;
};
+
+ template<bool record_weight, typename goal_filter, typename P>
+ oqgraph_goal<record_weight, goal_filter, P>
+ make_oqgraph_goal(const Vertex& goal, const P& p, stack_cursor *cursor)
+ { return oqgraph_goal<record_weight, goal_filter, P>(goal, p, cursor); }
+
}
namespace open_query
@@ -468,9 +437,14 @@ namespace open_query
return new (std::nothrow) oqgraph(share);
}
- oqgraph_share* oqgraph::create() throw()
+ oqgraph_share* oqgraph::create(
+ TABLE* table,
+ Field* origid,
+ Field* destid,
+ Field* weight) throw()
{
- return new (std::nothrow) oqgraph_share();
+ return new (std::nothrow) oqgraph_share(
+ table, origid, destid, weight);
}
optional<Edge>
@@ -480,14 +454,14 @@ namespace open_query
{
graph_traits<Graph>::out_edge_iterator ei, ei_end;
tie(ei, ei_end)= out_edges(orig, g);
- if ((ei= find_if(ei, ei_end, target_equals(dest, g))) != ei_end)
+ if ((ei= std::find_if(ei, ei_end, target_equals(dest, g))) != ei_end)
return *ei;
}
else
{
graph_traits<Graph>::in_edge_iterator ei, ei_end;
tie(ei, ei_end)= in_edges(dest, g);
- if ((ei= find_if(ei, ei_end, source_equals(orig, g))) != ei_end)
+ if ((ei= std::find_if(ei, ei_end, source_equals(orig, g))) != ei_end)
return *ei;
}
return optional<Edge>();
@@ -496,9 +470,10 @@ namespace open_query
optional<Vertex>
oqgraph_share::find_vertex(VertexID id) const
{
- return boost::graph::find_vertex(id, g);
+ return ::boost::find_vertex(id, g);
}
+#if 0
int oqgraph::delete_all() throw()
{
share->g.clear();
@@ -598,8 +573,9 @@ namespace open_query
optional<Vertex> orig= source(*edge, share->g),
dest= target(*edge, share->g);
- bool orig_neq= orig_id ? share->idmap[*orig] != *orig_id : 0;
- bool dest_neq= dest_id ? share->idmap[*dest] != *dest_id : 0;
+ bool orig_neq= orig_id ? get(boost::vertex_index, share->g, *orig) != *orig_id : 0;
+ bool dest_neq= dest_id ? get(boost::vertex_index, share->g, *dest) != *dest_id : 0;
+
if (orig_neq || dest_neq)
{
optional<Edge> new_edge;
@@ -675,7 +651,6 @@ namespace open_query
return OK;
}
-
int oqgraph::delete_edge(VertexID orig_id, VertexID dest_id) throw()
{
optional<Vertex> orig, dest;
@@ -694,6 +669,7 @@ namespace open_query
remove_vertex(*dest, share->g);
return OK;
}
+#endif
int oqgraph::search(int *latch, VertexID *orig_id, VertexID *dest_id) throw()
@@ -731,7 +707,8 @@ namespace open_query
{
Vertex v= target(*ei, share->g);
static_cast<stack_cursor*>(cursor)->
- results.push(reference(++seq, v, *ei, share->weightmap[*ei]));
+ results.push(reference(++seq, v, *ei,
+ get(boost::edge_weight, share->g, *ei)));
}
}
/* fall through */
@@ -745,7 +722,8 @@ namespace open_query
{
Vertex v= source(*ei, share->g);
static_cast<stack_cursor*>(cursor)->
- results.push(reference(++seq, v, *ei, share->weightmap[*ei]));
+ results.push(reference(++seq, v, *ei,
+ get(boost::edge_weight, share->g, *ei)));
}
}
break;
@@ -757,27 +735,29 @@ namespace open_query
case DIJKSTRAS | HAVE_ORIG | HAVE_DEST:
if ((cursor= new (std::nothrow) stack_cursor(share)) && orig && dest)
{
- std::vector<Vertex> p(num_vertices(share->g));
- std::vector<EdgeWeight> d(num_vertices(share->g));
- oqgraph_goal<true, on_finish_vertex>
- vis(*dest, p.begin(), static_cast<stack_cursor*>(cursor));
- p[share->indexmap[*orig]]= *orig;
+ boost::unordered_map<Vertex, Vertex> p;
+ boost::unordered_map<Vertex, EdgeWeight> d;
+ p[ *orig ]= *orig;
+ d[ *orig ] = EdgeWeight();
try
{
- dijkstra_shortest_paths(share->g, *orig,
- weight_map(
- share->weightmap
- ).
- distance_map(
- make_iterator_property_map(d.begin(), share->indexmap)
- ).
- predecessor_map(
- make_iterator_property_map(p.begin(), share->indexmap)
- ).
- visitor(
- make_dijkstra_visitor(vis)
- )
- );
+ dijkstra_shortest_paths_no_init(share->g, *orig,
+ make_lazy_property_map(p, identity_initializer<Vertex>()),
+ make_lazy_property_map(d, value_initializer<EdgeWeight>(
+ (std::numeric_limits<EdgeWeight>::max)())),
+ get(edge_weight, share->g),
+ get(vertex_index, share->g),
+ std::less<EdgeWeight>(),
+ closed_plus<EdgeWeight>(),
+ EdgeWeight(),
+ make_dijkstra_visitor(
+ make_oqgraph_goal<true, on_finish_vertex>(
+ *dest,
+ boost::make_assoc_property_map(p),
+ static_cast<stack_cursor*>(cursor)
+ )
+ ),
+ make_two_bit_judy_map(get(vertex_index, share->g)));
}
catch (...)
{ /* printf("found\n"); */ }
@@ -787,23 +767,25 @@ namespace open_query
case BREADTH_FIRST | HAVE_ORIG | HAVE_DEST:
if ((cursor= new (std::nothrow) stack_cursor(share)) && orig && dest)
{
- std::vector<Vertex> p(num_vertices(share->g));
- oqgraph_goal<false, on_discover_vertex>
- vis(*dest, p.begin(), static_cast<stack_cursor*>(cursor));
- p[share->indexmap[*orig]]= *orig;
+ boost::unordered_map<Vertex, Vertex> p;
+ boost::queue<Vertex> Q;
+ p[ *orig ]= *orig;
try
{
- breadth_first_search(share->g, *orig,
- visitor(make_bfs_visitor(
+ breadth_first_visit(share->g, *orig, Q,
+ make_bfs_visitor(
std::make_pair(
record_predecessors(
- make_iterator_property_map(p.begin(), share->indexmap),
+ boost::make_assoc_property_map(p),
on_tree_edge()
),
- vis)
+ make_oqgraph_goal<false, on_discover_vertex>(
+ *dest, boost::make_assoc_property_map(p),
+ static_cast<stack_cursor*>(cursor)
+ )
)
- )
- );
+ ),
+ make_two_bit_judy_map(get(vertex_index, share->g)));
}
catch (...)
{ /* printf("found\n"); */ }
@@ -814,109 +796,121 @@ namespace open_query
case BREADTH_FIRST | HAVE_ORIG:
if ((cursor= new (std::nothrow) stack_cursor(share)) && (orig || dest))
{
- std::vector<Vertex> p(num_vertices(share->g));
- std::vector<EdgeWeight> d(num_vertices(share->g));
- oqgraph_visit_dist vis(p.begin(), d.begin(),
- static_cast<stack_cursor*>(cursor));
- p[share->indexmap[*orig]]= *orig;
+ boost::unordered_map<Vertex, Vertex> p;
+ boost::unordered_map<Vertex, EdgeWeight> d;
+ boost::queue<Vertex> Q;
+ p[ *orig ]= *orig;
+ d[ *orig ] = EdgeWeight();
switch (ALGORITHM & op)
{
case DIJKSTRAS:
- dijkstra_shortest_paths(share->g, *orig,
- weight_map(
- share->weightmap
- ).
- distance_map(
- make_iterator_property_map(d.begin(), share->indexmap)
- ).
- predecessor_map(
- make_iterator_property_map(p.begin(), share->indexmap)
- ).
- visitor(
- make_dijkstra_visitor(vis)
- )
- );
- break;
+ dijkstra_shortest_paths_no_init(share->g, *orig,
+ make_lazy_property_map(p, identity_initializer<Vertex>()),
+ make_lazy_property_map(d, value_initializer<EdgeWeight>(
+ (std::numeric_limits<EdgeWeight>::max)())),
+ get(edge_weight, share->g),
+ get(vertex_index, share->g),
+ std::less<EdgeWeight>(),
+ closed_plus<EdgeWeight>(),
+ EdgeWeight(),
+ make_dijkstra_visitor(
+ make_oqgraph_visit_dist(
+ boost::make_assoc_property_map(p), d,
+ static_cast<stack_cursor*>(cursor)
+ )
+ ),
+ make_two_bit_judy_map(get(vertex_index, share->g)));
+ break;
case BREADTH_FIRST:
- breadth_first_search(share->g, *orig,
- visitor(make_bfs_visitor(
+ breadth_first_visit(share->g, *orig, Q,
+ make_bfs_visitor(
std::make_pair(
record_predecessors(
- make_iterator_property_map(p.begin(),
- share->indexmap),
+ boost::make_assoc_property_map(p),
on_tree_edge()
),
std::make_pair(
record_distances(
- make_iterator_property_map(d.begin(),
- share->indexmap),
+ boost::make_assoc_property_map(d),
on_tree_edge()
),
- vis
+ make_oqgraph_visit_dist(
+ boost::make_assoc_property_map(p),
+ boost::make_assoc_property_map(d),
+ static_cast<stack_cursor*>(cursor)
+ )
))
- ))
- );
+ ),
+ make_two_bit_judy_map(get(vertex_index, share->g)));
break;
default:
abort();
}
}
break;
+#if 0
case BREADTH_FIRST | HAVE_DEST:
case DIJKSTRAS | HAVE_DEST:
if ((cursor= new (std::nothrow) stack_cursor(share)) && (orig || dest))
{
- std::vector<Vertex> p(num_vertices(share->g));
- std::vector<EdgeWeight> d(num_vertices(share->g));
- oqgraph_visit_dist vis(p.begin(), d.begin(),
- static_cast<stack_cursor*>(cursor));
+ boost::unordered_map<Vertex, Vertex> p;
+ boost::unordered_map<Vertex, EdgeWeight> d;
+ boost::queue<Vertex> Q;
reverse_graph<Graph> r(share->g);
- p[share->indexmap[*dest]]= *dest;
+ p[ *dest ]= *dest;
+ d[ *dest ] = EdgeWeight();
switch (ALGORITHM & op)
{
case DIJKSTRAS:
- dijkstra_shortest_paths(r, *dest,
- weight_map(
- share->weightmap
- ).
- distance_map(
- make_iterator_property_map(d.begin(), share->indexmap)
- ).
- predecessor_map(
- make_iterator_property_map(p.begin(), share->indexmap)
- ).
- visitor(
- make_dijkstra_visitor(vis)
- )
- );
+ dijkstra_shortest_paths_no_init(share->g, *dest,
+ make_lazy_property_map(p, identity_initializer<Vertex>()),
+ make_lazy_property_map(d, value_initializer<EdgeWeight>(
+ (std::numeric_limits<EdgeWeight>::max)())),
+ get(edge_weight, share->g),
+ get(vertex_index, share->g),
+ std::less<EdgeWeight>(),
+ closed_plus<EdgeWeight>(),
+ EdgeWeight(),
+ make_dijkstra_visitor(
+ make_dijkstra_visitor(
+ make_oqgraph_visit_dist(
+ boost::make_assoc_property_map(p),
+ boost::make_assoc_property_map(d),
+ static_cast<stack_cursor*>(cursor)
+ )
+ )
+ ),
+ make_two_bit_judy_map(get(vertex_index, share->g)));
break;
case BREADTH_FIRST:
- breadth_first_search(r, *dest,
- visitor(make_bfs_visitor(
+ breadth_first_visit(share->g, *dest, Q,
+ make_bfs_visitor(
std::make_pair(
record_predecessors(
- make_iterator_property_map(p.begin(),
- share->indexmap),
+ boost::make_assoc_property_map(p),
on_tree_edge()
),
std::make_pair(
record_distances(
- make_iterator_property_map(d.begin(),
- share->indexmap),
+ boost::make_assoc_property_map(d),
on_tree_edge()
),
- vis
+ make_oqgraph_visit_dist(
+ boost::make_assoc_property_map(p),
+ boost::make_assoc_property_map(d),
+ static_cast<stack_cursor*>(cursor)
+ )
))
- ))
- );
+ ),
+ make_two_bit_judy_map(get(vertex_index, share->g)));
break;
default:
abort();
}
}
break;
-
+#endif
default:
break;
}
@@ -1006,7 +1000,7 @@ int stack_cursor::fetch_row(const row &row_info, row &result,
if ((result.seq_indicator= seq= last.sequence()))
result.seq= *seq;
if ((result.link_indicator= v= last.vertex()))
- result.link= share->idmap[*v];
+ result.link= get(boost::vertex_index, share->g, *v);
if ((result.weight_indicator= w= last.weight()))
result.weight= *w;
return oqgraph::OK;
@@ -1040,7 +1034,7 @@ int vertices_cursor::fetch_row(const row &row_info, row &result,
if (v)
{
result.link_indicator= 1;
- result.link= share->idmap[*v];
+ result.link= get(boost::vertex_index, share->g, *v);
#ifdef DISPLAY_VERTEX_INFO
result.seq_indicator= 1;
if ((result.seq= degree(*v, share->g)))
@@ -1048,10 +1042,10 @@ int vertices_cursor::fetch_row(const row &row_info, row &result,
EdgeWeight weight= 0;
graph_traits<Graph>::in_edge_iterator iei, iei_end;
for (tie(iei, iei_end)= in_edges(*v, share->g); iei != iei_end; ++iei)
- weight+= share->weightmap[*iei];
+ weight+= get(boost::edge_weight, share->g, *iei);
graph_traits<Graph>::out_edge_iterator oei, oei_end;
for (tie(oei, oei_end)= out_edges(*v, share->g); oei != oei_end; ++oei)
- weight+= share->weightmap[*oei];
+ weight+= get(boost::edge_weight, share->g, *oei);
result.weight_indicator= 1;
result.weight= weight / result.seq;
}
@@ -1085,9 +1079,9 @@ int edges_cursor::fetch_row(const row &row_info, row &result,
{
result= row_info;
result.orig_indicator= result.dest_indicator= result.weight_indicator= 1;
- result.orig= share->idmap[ source( *edge, share->g ) ];
- result.dest= share->idmap[ target( *edge, share->g ) ];
- result.weight= share->weightmap[ *edge ];
+ result.orig= get(boost::vertex_index, share->g, source( *edge, share->g ) );
+ result.dest= get(boost::vertex_index, share->g, target( *edge, share->g ) );
+ result.weight= get(boost::edge_weight, share->g, *edge);
return oqgraph::OK;
}
return oqgraph::NO_MORE_DATA;
diff --git a/storage/oqgraph/graphcore.h b/storage/oqgraph/graphcore.h
index 4aaddb2796f..d0f7844a36d 100644
--- a/storage/oqgraph/graphcore.h
+++ b/storage/oqgraph/graphcore.h
@@ -104,7 +104,7 @@ namespace open_query
void row_ref(void*) throw();
static oqgraph* create(oqgraph_share*) throw();
- static oqgraph_share *create() throw();
+ static oqgraph_share *create(TABLE*,Field*,Field*,Field*) throw();
static void free(oqgraph*) throw();
static void free(oqgraph_share*) throw();
diff --git a/storage/oqgraph/ha_oqgraph.cc b/storage/oqgraph/ha_oqgraph.cc
index cf9ef3d8997..06cdad13ccf 100644
--- a/storage/oqgraph/ha_oqgraph.cc
+++ b/storage/oqgraph/ha_oqgraph.cc
@@ -28,13 +28,12 @@
#pragma implementation // gcc: Class implementation
#endif
+#include <stdarg.h>
+#include <stdio.h>
+
#define MYSQL_SERVER // to have THD
#include "mysql_priv.h"
-#if MYSQL_VERSION_ID >= 50100
#include <mysql/plugin.h>
-#endif
-
-#ifdef HAVE_OQGRAPH
#include "ha_oqgraph.h"
#include "graphcore.h"
@@ -44,77 +43,36 @@
using namespace open_query;
-struct oqgraph_info_st
+struct oqgraph_table_option_struct
+{
+ char *table_name;
+
+ char *origid; // name of the origin id column
+ char *destid; // name of the target id column
+ char *weight; // name of the weight column (optional)
+};
+
+#define ha_table_option_struct oqgraph_table_option_struct
+ha_create_table_option oqgraph_table_option_list[]=
{
- THR_LOCK lock;
- oqgraph_share *graph;
- uint use_count;
- uint key_stat_version;
- uint records;
- bool dropped;
- char name[FN_REFLEN+1];
+ HA_TOPTION_STRING("data_table", table_name),
+ HA_TOPTION_STRING("origid", origid),
+ HA_TOPTION_STRING("destid", destid),
+ HA_TOPTION_STRING("weight", weight),
+ HA_TOPTION_END
};
static const char oqgraph_description[]=
- "Open Query Graph Computation Engine, stored in memory "
+ "Open Query Graph Computation Engine "
"(http://openquery.com/graph)";
-#if MYSQL_VERSION_ID < 50100
-static bool oqgraph_init();
-
-handlerton oqgraph_hton= {
- "OQGRAPH",
- SHOW_OPTION_YES,
- oqgraph_description,
- DB_TYPE_OQGRAPH,
- oqgraph_init,
- 0, /* slot */
- 0, /* savepoint size. */
- NULL, /* close_connection */
- NULL, /* savepoint */
- NULL, /* rollback to savepoint */
- NULL, /* release savepoint */
- NULL, /* commit */
- NULL, /* rollback */
- NULL, /* prepare */
- NULL, /* recover */
- NULL, /* commit_by_xid */
- NULL, /* rollback_by_xid */
- NULL, /* create_cursor_read_view */
- NULL, /* set_cursor_read_view */
- NULL, /* close_cursor_read_view */
- HTON_NO_FLAGS
-};
-
-#define STATISTIC_INCREMENT(X) \
-statistic_increment(table->in_use->status_var.X, &LOCK_status)
-#define MOVE(X) move_field(X)
-#define RECORDS records
-#else
#define STATISTIC_INCREMENT(X) ha_statistic_increment(&SSV::X)
#define MOVE(X) move_field_offset(X)
#define RECORDS stats.records
-#endif
-static HASH oqgraph_open_tables;
-static pthread_mutex_t LOCK_oqgraph;
static bool oqgraph_init_done= 0;
-#if MYSQL_VERSION_ID >= 50130
-#define HASH_KEY_LENGTH size_t
-#else
-#define HASH_KEY_LENGTH uint
-#endif
-static uchar* get_key(const uchar *ptr, HASH_KEY_LENGTH *length,
- my_bool)
-{
- const OQGRAPH_INFO *share= (const OQGRAPH_INFO*) ptr;
- *length= strlen(share->name);
- return (uchar*) share->name;
-}
-
-#if MYSQL_VERSION_ID >= 50100
static handler* oqgraph_create_handler(handlerton *hton, TABLE_SHARE *table,
MEM_ROOT *mem_root)
{
@@ -123,98 +81,20 @@ static handler* oqgraph_create_handler(handlerton *hton, TABLE_SHARE *table,
static int oqgraph_init(handlerton *hton)
{
-#else
-static bool oqgraph_init()
-{
- if (have_oqgraph == SHOW_OPTION_DISABLED)
- return 1;
-#endif
- if (pthread_mutex_init(&LOCK_oqgraph, MY_MUTEX_INIT_FAST))
- goto error;
- if (hash_init(&oqgraph_open_tables, &my_charset_bin, 32, 0, 0,
- get_key, 0, 0))
- {
- pthread_mutex_destroy(&LOCK_oqgraph);
- goto error;
- }
-#if MYSQL_VERSION_ID >= 50100
hton->state= SHOW_OPTION_YES;
hton->db_type= DB_TYPE_AUTOASSIGN;
hton->create= oqgraph_create_handler;
hton->flags= HTON_NO_FLAGS;
-#endif
+ hton->table_options= oqgraph_table_option_list;
oqgraph_init_done= TRUE;
return 0;
-error:
-#if MYSQL_VERSION_ID < 50100
- have_oqgraph= SHOW_OPTION_DISABLED;
-#endif
- return 1;
}
-#if MYSQL_VERSION_ID >= 50100
static int oqgraph_fini(void *)
{
- hash_free(&oqgraph_open_tables);
- pthread_mutex_destroy(&LOCK_oqgraph);
oqgraph_init_done= FALSE;
return 0;
}
-#endif
-
-static OQGRAPH_INFO *get_share(const char *name, TABLE *table=0)
-{
- OQGRAPH_INFO *share;
- uint length= strlen(name);
-
- safe_mutex_assert_owner(&LOCK_oqgraph);
- if (!(share= (OQGRAPH_INFO*) hash_search(&oqgraph_open_tables,
- (byte*) name, length)))
- {
- if (!table ||
- !(share= new OQGRAPH_INFO))
- return 0;
- share->use_count= share->key_stat_version= share->records= 0;
- share->dropped= 0;
- strmov(share->name, name);
- if (!(share->graph= oqgraph::create()))
- {
- delete share;
- return 0;
- }
- if (my_hash_insert(&oqgraph_open_tables, (byte*) share))
- {
- oqgraph::free(share->graph);
- delete share;
- return 0;
- }
- thr_lock_init(&share->lock);
- }
- share->use_count++;
- return share;
-}
-
-static int free_share(OQGRAPH_INFO *share, bool drop=0)
-{
- safe_mutex_assert_owner(&LOCK_oqgraph);
- if (!share)
- return 0;
- if (drop)
- {
- share->dropped= true;
- hash_delete(&oqgraph_open_tables, (byte*) share);
- }
- if (!--share->use_count)
- {
- if (share->dropped)
- {
- thr_lock_delete(&share->lock);
- oqgraph::free(share->graph);
- delete share;
- }
- }
- return 0;
-}
static int error_code(int res)
{
@@ -262,6 +142,9 @@ static int error_code(int res)
KEY (latch, origid, destid) USING HASH,
KEY (latch, destid, origid) USING HASH
) ENGINE=OQGRAPH
+ READ_TABLE=bar
+ ORIGID=src_id
+ DESTID=tgt_id
*/
static int oqgraph_check_table_structure (TABLE *table_arg)
@@ -329,16 +212,15 @@ static int oqgraph_check_table_structure (TABLE *table_arg)
** OQGRAPH tables
*****************************************************************************/
-#if MYSQL_VERSION_ID >= 50100
ha_oqgraph::ha_oqgraph(handlerton *hton, TABLE_SHARE *table_arg)
- : handler(hton, table_arg),
-#else
-ha_oqgraph::ha_oqgraph(TABLE *table_arg)
- : handler(&oqgraph_hton, table_arg),
-#endif
- share(0), graph(0), records_changed(0), key_stat_version(0)
+ : handler(hton, table_arg)
+ , graph_share(0)
+ , graph(0)
+ , error_message("", 0, &my_charset_latin1)
{ }
+ha_oqgraph::~ha_oqgraph()
+{ }
static const char *ha_oqgraph_exts[] =
{
@@ -350,11 +232,7 @@ const char **ha_oqgraph::bas_ext() const
return ha_oqgraph_exts;
}
-#if MYSQL_VERSION_ID >= 50100
ulonglong ha_oqgraph::table_flags() const
-#else
-ulong ha_oqgraph::table_flags() const
-#endif
{
return (HA_NO_BLOBS | HA_NULL_IN_KEY |
HA_REC_NOT_IN_SEQ | HA_CAN_INSERT_DELAYED |
@@ -366,278 +244,251 @@ ulong ha_oqgraph::index_flags(uint inx, uint part, bool all_parts) const
return HA_ONLY_WHOLE_INDEX | HA_KEY_SCAN_NOT_ROR;
}
-int ha_oqgraph::open(const char *name, int mode, uint test_if_locked)
+bool ha_oqgraph::get_error_message(int error, String* buf)
{
- pthread_mutex_lock(&LOCK_oqgraph);
- if ((share = get_share(name, table)))
- {
- ref_length= oqgraph::sizeof_ref;
- }
-
- if (share)
+ if (error < 0)
{
- /* Initialize variables for the opened table */
- thr_lock_data_init(&share->lock, &lock, NULL);
-
- graph= oqgraph::create(share->graph);
-
- /*
- We cannot run update_key_stats() here because we do not have a
- lock on the table. The 'records' count might just be changed
- temporarily at this moment and we might get wrong statistics (Bug
- #10178). Instead we request for update. This will be done in
- ha_oqgraph::info(), which is always called before key statistics are
- used.
- */
- key_stat_version= share->key_stat_version-1;
+ buf->append(error_message);
+ buf->c_ptr_safe();
+ error_message.length(0);
}
- pthread_mutex_unlock(&LOCK_oqgraph);
-
- return (share ? 0 : 1);
+ return false;
}
-int ha_oqgraph::close(void)
+void ha_oqgraph::print_error(const char* fmt, ...)
{
- pthread_mutex_lock(&LOCK_oqgraph);
- oqgraph::free(graph); graph= 0;
- int res= free_share(share);
- pthread_mutex_unlock(&LOCK_oqgraph);
- return error_code(res);
+ va_list ap;
+ va_start(ap, fmt);
+ error_message.reserve(256);
+ size_t len = error_message.length();
+ len += vsnprintf(&error_message[len], 255, fmt, ap);
+ error_message.length(len);
+ va_end(ap);
}
-void ha_oqgraph::update_key_stats()
+
+int ha_oqgraph::open(const char *name, int mode, uint test_if_locked)
{
- for (uint i= 0; i < table->s->keys; i++)
- {
- KEY *key=table->key_info+i;
- if (!key->rec_per_key)
- continue;
- if (key->algorithm != HA_KEY_ALG_BTREE)
- {
- if (key->flags & HA_NOSAME)
- key->rec_per_key[key->key_parts-1]= 1;
- else
- {
- unsigned vertices= graph->vertices_count();
- unsigned edges= graph->edges_count();
- uint no_records= vertices ? 2 * (edges + vertices) / vertices : 2;
- if (no_records < 2)
- no_records= 2;
- key->rec_per_key[key->key_parts-1]= no_records;
- }
- }
- }
- records_changed= 0;
- /* At the end of update_key_stats() we can proudly claim they are OK. */
- key_stat_version= share->key_stat_version;
-}
+ THD* thd = current_thd;
+ oqgraph_table_option_struct *options=
+ reinterpret_cast<oqgraph_table_option_struct*>(table->s->option_struct);
+ error_message.length(0);
+
+ const char* p= strend(name)-1;
+ while (p > name && *p != '\\' && *p != '/')
+ --p;
-int ha_oqgraph::write_row(byte * buf)
-{
- int res= oqgraph::MISC_FAIL;
- Field ** const field= table->field;
- STATISTIC_INCREMENT(ha_write_count);
+ init_tmp_table_share(
+ thd, share, table->s->db.str, table->s->db.length,
+ options->table_name, "");
-#if MYSQL_VERSION_ID >= 50100
- my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->read_set);
-#endif
- my_ptrdiff_t ptrdiff= buf - table->record[0];
+ size_t tlen= strlen(options->table_name);
+ size_t plen= (int)(p - name) + tlen;
- if (ptrdiff)
- {
- field[1]->MOVE(ptrdiff);
- field[2]->MOVE(ptrdiff);
- field[3]->MOVE(ptrdiff);
- }
+ share->path.str= (char*)
+ alloc_root(&share->mem_root, plen + 1);
- if (!field[1]->is_null() && !field[2]->is_null())
- {
- VertexID orig_id= (VertexID) field[1]->val_int();
- VertexID dest_id= (VertexID) field[2]->val_int();
- EdgeWeight weight= 1;
+ strmov(strnmov(share->path.str, name, (int)(p - name) + 1), options->table_name);
+
+ share->normalized_path.str= share->path.str;
+ share->path.length= share->normalized_path.length= plen;
- if (!field[3]->is_null())
- weight= (EdgeWeight) field[3]->val_real();
+ origid= destid= weight= 0;
- if (!(res= graph->insert_edge(orig_id, dest_id, weight, replace_dups)))
+ while (open_table_def(thd, share, 0))
+ {
+ if (thd->is_error() && thd->main_da.sql_errno() != ER_NO_SUCH_TABLE)
+ {
+ free_table_share(share);
+ return thd->main_da.sql_errno();
+ }
+
+ if (ha_create_table_from_engine(thd, table->s->db.str, options->table_name))
{
- ++records_changed;
- share->records++;
+ free_table_share(share);
+ return thd->main_da.sql_errno();
}
- if (res == oqgraph::DUPLICATE_EDGE && ignore_dups && !insert_dups)
- res= oqgraph::OK;
+ mysql_reset_errors(thd, 1);
+ thd->clear_error();
+ continue;
}
-
- if (ptrdiff)
+
+ if (int err= share->error)
{
- field[1]->MOVE(-ptrdiff);
- field[2]->MOVE(-ptrdiff);
- field[3]->MOVE(-ptrdiff);
+ open_table_error(share, share->error, share->open_errno, share->errarg);
+ free_table_share(share);
+ return err;
}
-#if MYSQL_VERSION_ID >= 50100
- dbug_tmp_restore_column_map(table->read_set, old_map);
-#endif
- if (!res && records_changed*OQGRAPH_STATS_UPDATE_THRESHOLD > share->records)
+ if (share->is_view)
{
- /*
- We can perform this safely since only one writer at the time is
- allowed on the table.
- */
- share->key_stat_version++;
+ open_table_error(share, 1, EMFILE, 0);
+ free_table_share(share);
+ print_error("VIEWs are not supported for a backing store");
+ return -1;
}
- return error_code(res);
-}
-
-int ha_oqgraph::update_row(const byte * old, byte * buf)
-{
- int res= oqgraph::MISC_FAIL;
- VertexID orig_id, dest_id;
- EdgeWeight weight= 1;
- Field **field= table->field;
- STATISTIC_INCREMENT(ha_update_count);
-
-#if MYSQL_VERSION_ID >= 50100
- my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->read_set);
-#endif
- my_ptrdiff_t ptrdiff= buf - table->record[0];
-
- if (ptrdiff)
+ if (int err= open_table_from_share(thd, share, "",
+ (uint) (HA_OPEN_KEYFILE | HA_OPEN_RNDFILE |
+ HA_GET_INDEX | HA_TRY_READ_ONLY),
+ READ_KEYINFO | COMPUTE_TYPES | EXTRA_RECORD,
+ thd->open_options, edges, FALSE))
{
- field[0]->MOVE(ptrdiff);
- field[1]->MOVE(ptrdiff);
- field[2]->MOVE(ptrdiff);
- field[3]->MOVE(ptrdiff);
+ open_table_error(share, err, EMFILE, 0);
+ free_table_share(share);
+ return -1;
}
- if (inited == INDEX || inited == RND)
+ edges->reginfo.lock_type= TL_READ;
+
+ edges->tablenr= thd->current_tablenr++;
+ edges->status= STATUS_NO_RECORD;
+ edges->file->ha_start_of_new_statement();
+ edges->file->ft_handler= 0;
+ edges->pos_in_table_list= 0;
+ edges->clear_column_bitmaps();
+ bfill(table->record[0], table->s->null_bytes, 255);
+ bfill(table->record[1], table->s->null_bytes, 255);
+
+ // We expect fields origid, destid and optionally weight
+ origid= destid= weight= 0;
+
+ if (!edges->file)
+ {
+ print_error("Some error occurred opening table '%s'", options->table_name);
+ free_table_share(share);
+ return -1;
+ }
+
+ for (Field **field= edges->field; *field; ++field)
{
- VertexID *origp= 0, *destp= 0;
- EdgeWeight *weightp= 0;
- if (!field[1]->is_null())
- *(origp= &orig_id)= (VertexID) field[1]->val_int();
- if (!field[2]->is_null())
- *(destp= &dest_id)= (VertexID) field[2]->val_int();
- if (!field[3]->is_null())
- *(weightp= &weight)= (EdgeWeight) field[3]->val_real();
-
- my_ptrdiff_t ptrdiff2= old - buf;
-
- field[0]->MOVE(ptrdiff2);
- field[1]->MOVE(ptrdiff2);
- field[2]->MOVE(ptrdiff2);
- field[3]->MOVE(ptrdiff2);
-
- if (field[0]->is_null())
+ if (strcmp(options->origid, (*field)->field_name))
+ continue;
+ if ((*field)->cmp_type() != INT_RESULT ||
+ !((*field)->flags & NOT_NULL_FLAG))
{
- if (!origp == field[1]->is_null() &&
- *origp == (VertexID) field[1]->val_int())
- origp= 0;
- if (!destp == field[2]->is_null() &&
- *destp == (VertexID) field[2]->val_int())
- origp= 0;
- if (!weightp == field[3]->is_null() &&
- *weightp == (VertexID) field[3]->val_real())
- weightp= 0;
-
- if (!(res= graph->modify_edge(oqgraph::current_row(),
- origp, destp, weightp, replace_dups)))
- ++records_changed;
- else if (ignore_dups && res == oqgraph::DUPLICATE_EDGE)
- res= oqgraph::OK;
+ print_error("Column '%s.%s' is not a not-null integer type",
+ options->table_name, options->origid);
+ closefrm(edges, 0);
+ free_table_share(share);
+ return -1;
}
-
- field[0]->MOVE(-ptrdiff2);
- field[1]->MOVE(-ptrdiff2);
- field[2]->MOVE(-ptrdiff2);
- field[3]->MOVE(-ptrdiff2);
+ origid = *field;
+ break;
}
-
- if (ptrdiff)
+
+ for (Field **field= edges->field; *field; ++field)
{
- field[0]->MOVE(-ptrdiff);
- field[1]->MOVE(-ptrdiff);
- field[2]->MOVE(-ptrdiff);
- field[3]->MOVE(-ptrdiff);
+ if (strcmp(options->destid, (*field)->field_name))
+ continue;
+ if ((*field)->type() != origid->type() ||
+ !((*field)->flags & NOT_NULL_FLAG))
+ {
+ print_error("Column '%s.%s' is not a not-null integer type",
+ options->table_name, options->destid);
+ closefrm(edges, 0);
+ free_table_share(share);
+ return -1;
+ }
+ destid = *field;
+ break;
}
-#if MYSQL_VERSION_ID >= 50100
- dbug_tmp_restore_column_map(table->read_set, old_map);
-#endif
-
- if (!res && records_changed*OQGRAPH_STATS_UPDATE_THRESHOLD > share->records)
+
+ for (Field **field= edges->field; options->weight && *field; ++field)
+ {
+ if (strcmp(options->weight, (*field)->field_name))
+ continue;
+ if ((*field)->result_type() != REAL_RESULT ||
+ !((*field)->flags & NOT_NULL_FLAG))
+ {
+ print_error("Column '%s.%s' is not a not-null real type",
+ options->table_name, options->weight);
+ closefrm(edges, 0);
+ free_table_share(share);
+ return -1;
+ }
+ weight = *field;
+ break;
+ }
+
+ if (!origid || !destid || (!weight && options->weight))
{
- /*
- We can perform this safely since only one writer at the time is
- allowed on the table.
- */
- share->key_stat_version++;
+ print_error("Data columns missing on table '%s'", options->table_name);
+ closefrm(edges, 0);
+ free_table_share(share);
+ return -1;
}
- return error_code(res);
+
+ if (!(graph_share = oqgraph::create(edges, origid, destid, weight)))
+ {
+ print_error("Unable to create graph instance.");
+ closefrm(edges, 0);
+ free_table_share(share);
+ return -1;
+ }
+ ref_length= oqgraph::sizeof_ref;
+
+ graph = oqgraph::create(graph_share);
+
+ return 0;
}
-int ha_oqgraph::delete_row(const byte * buf)
+int ha_oqgraph::close(void)
{
- int res= oqgraph::EDGE_NOT_FOUND;
- Field **field= table->field;
- STATISTIC_INCREMENT(ha_delete_count);
+ oqgraph::free(graph); graph= 0;
+ oqgraph::free(graph_share); graph_share= 0;
- if (inited == INDEX || inited == RND)
+ if (share)
{
- if ((res= graph->delete_edge(oqgraph::current_row())) == oqgraph::OK)
- {
- ++records_changed;
- share->records--;
- }
+ if (edges->file)
+ closefrm(edges, 0);
+ free_table_share(share);
}
- if (res != oqgraph::OK)
- {
-#if MYSQL_VERSION_ID >= 50100
- my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->read_set);
-#endif
- my_ptrdiff_t ptrdiff= buf - table->record[0];
-
- if (ptrdiff)
- {
- field[0]->MOVE(ptrdiff);
- field[1]->MOVE(ptrdiff);
- field[2]->MOVE(ptrdiff);
- }
+ return 0;
+}
- if (field[0]->is_null() && !field[1]->is_null() && !field[2]->is_null())
+void ha_oqgraph::update_key_stats()
+{
+ for (uint i= 0; i < table->s->keys; i++)
+ {
+ KEY *key=table->key_info+i;
+ if (!key->rec_per_key)
+ continue;
+ if (key->algorithm != HA_KEY_ALG_BTREE)
{
- VertexID orig_id= (VertexID) field[1]->val_int();
- VertexID dest_id= (VertexID) field[2]->val_int();
-
- if ((res= graph->delete_edge(orig_id, dest_id)) == oqgraph::OK)
+ if (key->flags & HA_NOSAME)
+ key->rec_per_key[key->key_parts-1]= 1;
+ else
{
- ++records_changed;
- share->records--;
+ //unsigned vertices= graph->vertices_count();
+ //unsigned edges= graph->edges_count();
+ //uint no_records= vertices ? 2 * (edges + vertices) / vertices : 2;
+ //if (no_records < 2)
+ uint
+ no_records= 2;
+ key->rec_per_key[key->key_parts-1]= no_records;
}
}
-
- if (ptrdiff)
- {
- field[0]->MOVE(-ptrdiff);
- field[1]->MOVE(-ptrdiff);
- field[2]->MOVE(-ptrdiff);
- }
-#if MYSQL_VERSION_ID >= 50100
- dbug_tmp_restore_column_map(table->read_set, old_map);
-#endif
}
+ /* At the end of update_key_stats() we can proudly claim they are OK. */
+ //skey_stat_version= share->key_stat_version;
+}
- if (!res && table->s->tmp_table == NO_TMP_TABLE &&
- records_changed*OQGRAPH_STATS_UPDATE_THRESHOLD > share->records)
- {
- /*
- We can perform this safely since only one writer at the time is
- allowed on the table.
- */
- share->key_stat_version++;
- }
- return error_code(res);
+
+int ha_oqgraph::write_row(byte * buf)
+{
+ return ER_OPEN_AS_READONLY;
+}
+
+int ha_oqgraph::update_row(const byte * old, byte * buf)
+{
+ return ER_OPEN_AS_READONLY;
+}
+
+int ha_oqgraph::delete_row(const byte * buf)
+{
+ return ER_OPEN_AS_READONLY;
}
int ha_oqgraph::index_read(byte * buf, const byte * key, uint key_len,
@@ -675,9 +526,7 @@ int ha_oqgraph::index_read_idx(byte * buf, uint index, const byte * key,
bmove_align(buf, table->s->default_values, table->s->reclength);
key_restore(buf, (byte*) key, key_info, key_len);
-#if MYSQL_VERSION_ID >= 50100
my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->read_set);
-#endif
my_ptrdiff_t ptrdiff= buf - table->record[0];
if (ptrdiff)
@@ -711,9 +560,7 @@ int ha_oqgraph::index_read_idx(byte * buf, uint index, const byte * key,
field[1]->MOVE(-ptrdiff);
field[2]->MOVE(-ptrdiff);
}
-#if MYSQL_VERSION_ID >= 50100
dbug_tmp_restore_column_map(table->read_set, old_map);
-#endif
res= graph->search(latchp, orig_idp, dest_idp);
@@ -729,9 +576,7 @@ int ha_oqgraph::fill_record(byte *record, const open_query::row &row)
bmove_align(record, table->s->default_values, table->s->reclength);
-#if MYSQL_VERSION_ID >= 50100
my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->write_set);
-#endif
my_ptrdiff_t ptrdiff= record - table->record[0];
if (ptrdiff)
@@ -790,15 +635,14 @@ int ha_oqgraph::fill_record(byte *record, const open_query::row &row)
field[4]->MOVE(-ptrdiff);
field[5]->MOVE(-ptrdiff);
}
-#if MYSQL_VERSION_ID >= 50100
dbug_tmp_restore_column_map(table->write_set, old_map);
-#endif
return 0;
}
int ha_oqgraph::rnd_init(bool scan)
{
+ edges->prepare_for_position();
return error_code(graph->random(scan));
}
@@ -836,75 +680,31 @@ int ha_oqgraph::cmp_ref(const byte *ref1, const byte *ref2)
int ha_oqgraph::info(uint flag)
{
- RECORDS= graph->vertices_count() + graph->edges_count();
-#if 0
- records= hp_info.records;
- deleted= hp_info.deleted;
- errkey= hp_info.errkey;
- mean_rec_length= hp_info.reclength;
- data_file_length= hp_info.data_length;
- index_file_length= hp_info.index_length;
- max_data_file_length= hp_info.max_records* hp_info.reclength;
- delete_length= hp_info.deleted * hp_info.reclength;
-#endif
+ RECORDS= graph->edges_count();
+
/*
If info() is called for the first time after open(), we will still
have to update the key statistics. Hoping that a table lock is now
in place.
*/
- if (key_stat_version != share->key_stat_version)
- update_key_stats();
+// if (key_stat_version != share->key_stat_version)
+ // update_key_stats();
return 0;
}
int ha_oqgraph::extra(enum ha_extra_function operation)
{
- switch (operation)
- {
- case HA_EXTRA_IGNORE_DUP_KEY:
- ignore_dups= true;
- break;
- case HA_EXTRA_NO_IGNORE_DUP_KEY:
- ignore_dups= false;
- insert_dups= false;
- break;
- case HA_EXTRA_WRITE_CAN_REPLACE:
- replace_dups= true;
- break;
- case HA_EXTRA_WRITE_CANNOT_REPLACE:
- replace_dups= false;
- break;
- case HA_EXTRA_INSERT_WITH_UPDATE:
- insert_dups= true;
- break;
- default:
- break;
- }
- return 0;
+ return edges->file->extra(operation);
}
int ha_oqgraph::delete_all_rows()
{
- int res;
- if (!(res= graph->delete_all()))
- {
- share->records= 0;
- }
-
- if (!res && table->s->tmp_table == NO_TMP_TABLE)
- {
- /*
- We can perform this safely since only one writer at the time is
- allowed on the table.
- */
- share->key_stat_version++;
- }
- return error_code(res);
+ return ER_OPEN_AS_READONLY;
}
int ha_oqgraph::external_lock(THD *thd, int lock_type)
{
- return 0; // No external locking
+ return edges->file->ha_external_lock(thd, lock_type);
}
@@ -912,10 +712,7 @@ THR_LOCK_DATA **ha_oqgraph::store_lock(THD *thd,
THR_LOCK_DATA **to,
enum thr_lock_type lock_type)
{
- if (lock_type != TL_IGNORE && lock.type == TL_UNLOCK)
- lock.type=lock_type;
- *to++= &lock;
- return to;
+ return edges->file->store_lock(thd, to, lock_type);
}
/*
@@ -923,29 +720,13 @@ THR_LOCK_DATA **ha_oqgraph::store_lock(THD *thd,
not when doing a CREATE on the table.
*/
-int ha_oqgraph::delete_table(const char *name)
+int ha_oqgraph::delete_table(const char *)
{
- int res= 0;
- OQGRAPH_INFO *share;
- pthread_mutex_lock(&LOCK_oqgraph);
- if ((share= get_share(name)))
- {
- res= free_share(share, true);
- }
- pthread_mutex_unlock(&LOCK_oqgraph);
- return error_code(res);
+ return 0;
}
-int ha_oqgraph::rename_table(const char * from, const char * to)
+int ha_oqgraph::rename_table(const char *, const char *)
{
- pthread_mutex_lock(&LOCK_oqgraph);
- if (OQGRAPH_INFO *share= get_share(from))
- {
- strmov(share->name, to);
- hash_update(&oqgraph_open_tables, (byte*) share,
- (byte*) from, strlen(from));
- }
- pthread_mutex_unlock(&LOCK_oqgraph);
return 0;
}
@@ -978,8 +759,9 @@ ha_rows ha_oqgraph::records_in_range(uint inx, key_range *min_key,
return RECORDS;
/* Assert that info() did run. We need current statistics here. */
- DBUG_ASSERT(key_stat_version == share->key_stat_version);
- ha_rows result= key->rec_per_key[key->key_parts-1];
+ //DBUG_ASSERT(key_stat_version == share->key_stat_version);
+ //ha_rows result= key->rec_per_key[key->key_parts-1];
+ ha_rows result= 10;
return result;
}
@@ -988,24 +770,13 @@ ha_rows ha_oqgraph::records_in_range(uint inx, key_range *min_key,
int ha_oqgraph::create(const char *name, TABLE *table_arg,
HA_CREATE_INFO *create_info)
{
- int res = -1;
- OQGRAPH_INFO *share;
+ oqgraph_table_option_struct *options=
+ reinterpret_cast<oqgraph_table_option_struct*>(table->s->option_struct);
- pthread_mutex_lock(&LOCK_oqgraph);
- if ((share= get_share(name)))
- {
- free_share(share);
- }
- else
- {
- if (!oqgraph_check_table_structure(table_arg))
- res= 0;;
- }
- pthread_mutex_unlock(&LOCK_oqgraph);
+ if (int res = oqgraph_check_table_structure(table_arg))
+ return error_code(res);
- if (this->share)
- info(HA_STATUS_NO_LOCK | HA_STATUS_CONST | HA_STATUS_VARIABLE);
- return error_code(res);
+ return 0;
}
@@ -1016,7 +787,6 @@ void ha_oqgraph::update_create_info(HA_CREATE_INFO *create_info)
// create_info->auto_increment_value= auto_increment_value;
}
-#if MYSQL_VERSION_ID >= 50100
struct st_mysql_storage_engine oqgraph_storage_engine=
{ MYSQL_HANDLERTON_INTERFACE_VERSION };
@@ -1030,12 +800,9 @@ mysql_declare_plugin(oqgraph)
PLUGIN_LICENSE_GPL,
(int (*)(void*)) oqgraph_init, /* Plugin Init */
oqgraph_fini, /* Plugin Deinit */
- 0x0200, /* Version: 2.0 */
+ 0x0300, /* Version: 3s.0 */
NULL, /* status variables */
NULL, /* system variables */
NULL /* config options */
}
mysql_declare_plugin_end;
-#endif
-
-#endif
diff --git a/storage/oqgraph/ha_oqgraph.h b/storage/oqgraph/ha_oqgraph.h
index dcc14b074da..4c606dcc7e4 100644
--- a/storage/oqgraph/ha_oqgraph.h
+++ b/storage/oqgraph/ha_oqgraph.h
@@ -39,19 +39,21 @@ namespace open_query
{
struct row;
class oqgraph;
+ class oqgraph_share;
}
/* class for the the Open Query Graph handler */
class ha_oqgraph: public handler
{
- OQGRAPH_INFO *share;
+ TABLE_SHARE share[1];
+ TABLE edges[1];
+ Field *origid;
+ Field *destid;
+ Field *weight;
+
+ open_query::oqgraph_share *graph_share;
open_query::oqgraph *graph;
- THR_LOCK_DATA lock;
- /* number of records changed since last statistics update */
- uint records_changed;
- uint key_stat_version;
- bool replace_dups, ignore_dups, insert_dups;
int fill_record(byte*, const open_query::row&);
@@ -63,7 +65,7 @@ public:
ha_oqgraph(TABLE *table);
ulong table_flags() const;
#endif
- ~ha_oqgraph() {}
+ ~ha_oqgraph();
const char *table_type() const
{
return "OQGRAPH";
@@ -109,6 +111,12 @@ public:
THR_LOCK_DATA **store_lock(THD *thd, THR_LOCK_DATA **to,
enum thr_lock_type lock_type);
int cmp_ref(const byte *ref1, const byte *ref2);
+
+ bool get_error_message(int error, String* buf);
+
+ void print_error(const char* fmt, ...);
+
private:
void update_key_stats();
+ String error_message;
};
diff --git a/storage/oqgraph/oqgraph_judy.cc b/storage/oqgraph/oqgraph_judy.cc
new file mode 100644
index 00000000000..bf6b8e879c4
--- /dev/null
+++ b/storage/oqgraph/oqgraph_judy.cc
@@ -0,0 +1,113 @@
+/* Copyright (C) 2009-2011 Arjen G Lentz & Antony T Curtis for Open Query
+
+ This program 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; version 2 of the License, or
+ (at your option) any later version.
+
+ This program 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.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/* ======================================================================
+ Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+ Mk.III implementation by Antony Curtis & Arjen Lentz
+ For more information, documentation, support, enhancement engineering,
+ and non-GPL licensing, see http://openquery.com/graph
+ or contact graph@openquery.com
+ For packaged binaries, see http://ourdelta.org
+ ======================================================================
+*/
+
+#include "oqgraph_judy.h"
+#include <Judy.h>
+
+void open_query::judy_bitset::clear()
+{
+ int rc;
+ J1FA(rc, array);
+}
+
+bool open_query::judy_bitset::test(size_type n) const
+{
+ int rc;
+ J1T(rc, array, n);
+ return rc == 1;
+}
+
+open_query::judy_bitset& open_query::judy_bitset::setbit(size_type n)
+{
+ int rc;
+ J1S(rc, array, n);
+ return *this;
+}
+
+open_query::judy_bitset& open_query::judy_bitset::reset(size_type n)
+{
+ int rc;
+ J1U(rc, array, n);
+ return *this;
+}
+
+open_query::judy_bitset& open_query::judy_bitset::flip(size_type n)
+{
+ int rc;
+ J1U(rc, array, n);
+ if (!rc)
+ {
+ J1S(rc, array, n);
+ }
+ return *this;
+}
+
+open_query::judy_bitset::size_type open_query::judy_bitset::num_blocks() const
+{
+ Word_t rc;
+ J1MU(rc, array);
+ return rc;
+}
+
+open_query::judy_bitset::size_type open_query::judy_bitset::size() const
+{
+ int rc;
+ Word_t index = (Word_t) -1;
+ J1L(rc, array, index);
+ if (!rc)
+ return index;
+ else
+ return npos;
+}
+
+open_query::judy_bitset::size_type open_query::judy_bitset::count() const
+{
+ Word_t rc;
+ J1C(rc, array, 0, -1);
+ return rc;
+}
+
+open_query::judy_bitset::size_type open_query::judy_bitset::find_first() const
+{
+ int rc;
+ Word_t index = 0;
+ J1F(rc, array, index);
+ if (!rc)
+ return index;
+ else
+ return npos;
+}
+
+open_query::judy_bitset::size_type open_query::judy_bitset::find_next(size_type n) const
+{
+ int rc;
+ Word_t index = (Word_t) n;
+ J1N(rc, array, index);
+ if (!rc)
+ return index;
+ else
+ return npos;
+}
diff --git a/storage/oqgraph/oqgraph_judy.h b/storage/oqgraph/oqgraph_judy.h
new file mode 100644
index 00000000000..965883c0864
--- /dev/null
+++ b/storage/oqgraph/oqgraph_judy.h
@@ -0,0 +1,109 @@
+/* Copyright (C) 2009-2011 Arjen G Lentz & Antony T Curtis for Open Query
+
+ This program 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; version 2 of the License, or
+ (at your option) any later version.
+
+ This program 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.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/* ======================================================================
+ Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+ Mk.III implementation by Antony Curtis & Arjen Lentz
+ For more information, documentation, support, enhancement engineering,
+ and non-GPL licensing, see http://openquery.com/graph
+ or contact graph@openquery.com
+ For packaged binaries, see http://ourdelta.org
+ ======================================================================
+*/
+
+#pragma once
+
+#include <cstddef>
+
+namespace open_query
+{
+
+ class judy_bitset
+ {
+ public:
+ typedef std::size_t size_type;
+ enum { npos = (size_type) -1 };
+
+ judy_bitset()
+ : array(0)
+ { }
+
+ ~judy_bitset()
+ { clear(); }
+
+ void clear();
+ bool empty() const { return !array; }
+ bool none() const { return npos == find_first(); }
+
+ inline judy_bitset& set(size_type n, bool val = true)
+ {
+ if (!val)
+ return reset(n);
+ else
+ return setbit(n);
+ }
+
+ judy_bitset& reset(size_type n);
+ judy_bitset& flip(size_type n);
+ bool test(size_type) const;
+ size_type count() const;
+ size_type size() const;
+ size_type num_blocks() const;
+
+ class reference
+ {
+ friend class judy_bitset;
+ reference(judy_bitset& array, size_type pos)
+ : j(array)
+ , n(pos)
+ { }
+ void operator&(); // not defined
+ public:
+ reference& operator=(bool value)
+ { j.set(n, value); return *this; }
+ reference& operator=(const reference& ref)
+ { j.set(n, ref); return *this; }
+
+ reference& operator|=(bool value)
+ { if (value) j.set(n); return *this; }
+ reference& operator&=(bool value)
+ { if (!value) j.reset(n); return *this; }
+ reference& operator^=(bool value)
+ { if (value) j.flip(n); return *this; }
+ reference& operator-=(bool value)
+ { if (value) j.reset(n); return *this; }
+
+ bool operator~() const { return !j.test(n); }
+ operator bool() const { return j.test(n); }
+ reference& flip() { j.flip(n); return *this; }
+
+ private:
+ judy_bitset& j;
+ size_type n;
+ };
+
+ reference operator[](size_type n) { return reference(*this, n); }
+ bool operator[](size_type n) const { return test(n); }
+
+ size_type find_first() const;
+ size_type find_next(size_type n) const;
+ private:
+ mutable void* array;
+
+ judy_bitset& setbit(size_type n);
+ };
+}
+
diff --git a/storage/oqgraph/oqgraph_shim.cc b/storage/oqgraph/oqgraph_shim.cc
new file mode 100644
index 00000000000..57ffe660532
--- /dev/null
+++ b/storage/oqgraph/oqgraph_shim.cc
@@ -0,0 +1,28 @@
+/* Copyright (C) 2009-2011 Arjen G Lentz & Antony T Curtis for Open Query
+
+ This program 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; version 2 of the License, or
+ (at your option) any later version.
+
+ This program 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.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/* ======================================================================
+ Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+ Mk.III implementation by Antony Curtis & Arjen Lentz
+ For more information, documentation, support, enhancement engineering,
+ and non-GPL licensing, see http://openquery.com/graph
+ or contact graph@openquery.com
+ For packaged binaries, see http://ourdelta.org
+ ======================================================================
+*/
+
+#include "oqgraph_shim.h"
+
diff --git a/storage/oqgraph/oqgraph_shim.h b/storage/oqgraph/oqgraph_shim.h
new file mode 100644
index 00000000000..4e381d797c3
--- /dev/null
+++ b/storage/oqgraph/oqgraph_shim.h
@@ -0,0 +1,735 @@
+/* Copyright (C) 2009-2011 Arjen G Lentz & Antony T Curtis for Open Query
+
+ This program 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; version 2 of the License, or
+ (at your option) any later version.
+
+ This program 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.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/* ======================================================================
+ Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+ Mk.III implementation by Antony Curtis & Arjen Lentz
+ For more information, documentation, support, enhancement engineering,
+ and non-GPL licensing, see http://openquery.com/graph
+ or contact graph@openquery.com
+ For packaged binaries, see http://ourdelta.org
+ ======================================================================
+*/
+
+#pragma once
+
+#include "oqgraph_thunk.h"
+#include "oqgraph_judy.h"
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/adjacency_iterator.hpp>
+
+namespace open_query
+{
+ struct OQGraphTraversalCategory
+ : public boost::bidirectional_graph_tag
+ , public boost::adjacency_graph_tag
+ , public boost::edge_list_graph_tag
+ { };
+
+}
+
+namespace oqgraph3
+{
+ struct traversal_category
+ : public boost::adjacency_graph_tag
+ , public boost::bidirectional_graph_tag
+ , public boost::edge_list_graph_tag
+ { };
+
+ struct edge_iterator
+ {
+ typedef edge_iterator self;
+ typedef edge_descriptor value_type;
+ typedef edge_descriptor& reference;
+ typedef edge_descriptor pointer;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::input_iterator_tag iterator_category;
+ edge_iterator() { }
+ edge_iterator(row_cursor iter) : _iter(iter) { }
+ edge_descriptor operator*() { return _iter->_current; }
+ self& operator++() { ++(*_iter); return *this; }
+ self operator++(int) { self t= *this; ++(*this); return t; }
+ bool operator==(const self& x) { return _iter == x._iter; }
+ bool operator!=(const self& x) { return _iter != x._iter; }
+ boost::optional<row_cursor> _iter;
+ };
+
+ struct vertex_iterator
+ {
+ typedef vertex_iterator self;
+ typedef vertex_descriptor value_type;
+ typedef vertex_descriptor& reference;
+ typedef vertex_descriptor pointer;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::input_iterator_tag iterator_category;
+ vertex_iterator() { }
+ vertex_iterator(edge_iterator iter) : _iter(iter) { }
+ vertex_descriptor operator*()
+ {
+ if (!_seen.test(_iter._iter->operator*().first))
+ return _iter._iter->_cache->vertex(_iter._iter->operator*().first);
+ else
+ return _iter._iter->_cache->vertex(_iter._iter->operator*().second);
+ }
+
+ self& operator++()
+ {
+ if (!_seen.test(_iter._iter->operator*().first))
+ {
+ _seen.set(_iter._iter->operator*().first);
+ }
+ else
+ {
+ _seen.set(_iter._iter->operator*().second);
+ }
+
+ while (_iter._iter->_current &&
+ _seen.test(_iter._iter->operator*().first) &&
+ _seen.test(_iter._iter->operator*().second))
+ {
+ ++_iter;
+ }
+ return *this;
+ }
+ self operator++(int) { self t= *this; ++(*this); return t; }
+ bool operator==(const self& x) { return _iter == x._iter; }
+ bool operator!=(const self& x) { return _iter != x._iter; }
+ edge_iterator _iter;
+ open_query::judy_bitset _seen;
+ };
+
+
+ struct out_edge_iterator
+ {
+ typedef out_edge_iterator self;
+ typedef vertex_info::edge_list_type::const_iterator iter_type;
+
+ typedef edge_descriptor value_type;
+ typedef edge_descriptor& reference;
+ typedef edge_descriptor pointer;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::input_iterator_tag iterator_category;
+ out_edge_iterator() { }
+ out_edge_iterator(iter_type iter, const vertex_descriptor& v)
+ : _iter(iter), _v(v) { }
+ edge_descriptor operator*()
+ { return _v->_cache->edge(edge_key(*_iter)); }
+ self& operator++() { ++_iter; return *this; }
+ self operator++(int) { self t= *this; ++(*this); return t; }
+ bool operator==(const self& x) { return _iter == x._iter; }
+ bool operator!=(const self& x) { return _iter != x._iter; }
+ iter_type _iter;
+ vertex_descriptor _v;
+ };
+
+ struct in_edge_iterator
+ {
+ typedef in_edge_iterator self;
+ typedef vertex_info::edge_list_type::const_iterator iter_type;
+
+ typedef edge_descriptor value_type;
+ typedef edge_descriptor& reference;
+ typedef edge_descriptor pointer;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::input_iterator_tag iterator_category;
+ in_edge_iterator() { }
+ in_edge_iterator(iter_type iter, const vertex_descriptor& v)
+ : _iter(iter), _v(v) { }
+ edge_descriptor operator*()
+ { return _v->_cache->edge(edge_key(*_iter)); }
+ self& operator++() { ++_iter; return *this; }
+ self operator++(int) { self t= *this; ++(*this); return t; }
+ bool operator==(const self& x) { return _iter == x._iter; }
+ bool operator!=(const self& x) { return _iter != x._iter; }
+ iter_type _iter;
+ vertex_descriptor _v;
+ };
+
+ struct vertex_index_property_map
+ {
+ typedef vertex_id value_type;
+ typedef value_type reference;
+ typedef vertex_descriptor key_type;
+ typedef boost::readable_property_map_tag category;
+ vertex_index_property_map(const graph& g) : _g(g) { }
+ const graph& _g;
+ };
+
+ struct edge_weight_property_map
+ {
+ typedef weight_t value_type;
+ typedef value_type reference;
+ typedef edge_descriptor key_type;
+ typedef boost::readable_property_map_tag category;
+ edge_weight_property_map(const graph& g) : _g(g) { }
+ const graph& _g;
+ };
+
+ struct edge_index_property_map
+ {
+ typedef edge_key::ref_type value_type;
+ typedef const edge_key::ref_type& reference;
+ typedef edge_descriptor key_type;
+ typedef boost::readable_property_map_tag category;
+ edge_index_property_map(const graph& g) : _g(g) { }
+ const graph& _g;
+ };
+}
+
+namespace boost
+{
+
+ template<>
+ struct graph_traits<oqgraph3::graph>
+ {
+ typedef oqgraph3::vertex_descriptor vertex_descriptor;
+ typedef oqgraph3::edge_descriptor edge_descriptor;
+ typedef boost::adjacency_iterator_generator<
+ oqgraph3::graph,
+ oqgraph3::vertex_descriptor,
+ oqgraph3::out_edge_iterator>::type adjacency_iterator;
+ typedef oqgraph3::out_edge_iterator out_edge_iterator;
+ typedef oqgraph3::in_edge_iterator in_edge_iterator;
+ typedef oqgraph3::vertex_iterator vertex_iterator;
+ typedef oqgraph3::edge_iterator edge_iterator;
+
+ typedef boost::directed_tag directed_category;
+ typedef boost::allow_parallel_edge_tag edge_parallel_category;
+ typedef oqgraph3::traversal_category traversal_category;
+
+ typedef oqgraph3::vertices_size_type vertices_size_type;
+ typedef oqgraph3::edges_size_type edges_size_type;
+ typedef oqgraph3::degree_size_type degree_size_type;
+
+ static inline vertex_descriptor null_vertex()
+ { return oqgraph3::vertex_descriptor(); }
+ };
+
+ template<>
+ struct graph_traits<const oqgraph3::graph>
+ : public graph_traits<oqgraph3::graph>
+ { };
+
+ template <>
+ struct graph_property_type<oqgraph3::graph>
+ {
+ typedef no_property type;
+ };
+
+ template <>
+ struct vertex_property_type<oqgraph3::graph>
+ {
+ typedef no_property type;
+ };
+
+ template <>
+ struct edge_property_type<oqgraph3::graph>
+ {
+ typedef no_property type;
+ };
+
+ template <>
+ struct graph_bundle_type<oqgraph3::graph>
+ {
+ typedef no_graph_bundle type;
+ };
+
+ template <>
+ struct vertex_bundle_type<oqgraph3::graph>
+ {
+ typedef no_vertex_bundle type;
+ };
+
+ template <>
+ struct edge_bundle_type<oqgraph3::graph>
+ {
+ typedef no_edge_bundle type;
+ };
+
+ inline std::pair<
+ graph_traits<oqgraph3::graph>::out_edge_iterator,
+ graph_traits<oqgraph3::graph>::out_edge_iterator>
+ out_edges(
+ graph_traits<oqgraph3::graph>::vertex_descriptor v,
+ const oqgraph3::graph&)
+ {
+ const oqgraph3::vertex_info::edge_list_type&
+ iter= v->out_edges();
+ return std::make_pair(
+ graph_traits<oqgraph3::graph>::out_edge_iterator(iter.begin(), v),
+ graph_traits<oqgraph3::graph>::out_edge_iterator(iter.end(), v));
+ }
+
+ inline std::pair<
+ graph_traits<oqgraph3::graph>::in_edge_iterator,
+ graph_traits<oqgraph3::graph>::in_edge_iterator>
+ in_edges(
+ graph_traits<oqgraph3::graph>::vertex_descriptor v,
+ const oqgraph3::graph&)
+ {
+ const oqgraph3::vertex_info::edge_list_type&
+ iter= v->out_edges();
+ return std::make_pair(
+ graph_traits<oqgraph3::graph>::in_edge_iterator(iter.begin(), v),
+ graph_traits<oqgraph3::graph>::in_edge_iterator(iter.end(), v));
+ }
+
+ // EdgeListGraph concepts
+ inline std::pair<
+ graph_traits<oqgraph3::graph>::edge_iterator,
+ graph_traits<oqgraph3::graph>::edge_iterator>
+ edges(const oqgraph3::graph& _g)
+ {
+ oqgraph3::graph& g= const_cast<oqgraph3::graph&>(_g);
+ return std::make_pair(
+ graph_traits<oqgraph3::graph>::edge_iterator(
+ oqgraph3::row_cursor(&g).first()),
+ graph_traits<oqgraph3::graph>::edge_iterator(
+ oqgraph3::row_cursor(&g).end()));
+ }
+
+ inline std::pair<
+ graph_traits<oqgraph3::graph>::vertex_iterator,
+ graph_traits<oqgraph3::graph>::vertex_iterator>
+ vertices(const oqgraph3::graph& g)
+ {
+ std::pair<
+ graph_traits<oqgraph3::graph>::edge_iterator,
+ graph_traits<oqgraph3::graph>::edge_iterator> epair= edges(g);
+ return std::make_pair(
+ graph_traits<oqgraph3::graph>::vertex_iterator(epair.first),
+ graph_traits<oqgraph3::graph>::vertex_iterator(epair.second));
+ }
+
+ inline graph_traits<oqgraph3::graph>::vertices_size_type
+ num_vertices(const oqgraph3::graph& g)
+ {
+ std::size_t count = 0;
+ for (std::pair<
+ graph_traits<oqgraph3::graph>::vertex_iterator,
+ graph_traits<oqgraph3::graph>::vertex_iterator> i= vertices(g);
+ i.first != i.second; ++i.first)
+ {
+ ++count;
+ }
+ return count;
+ }
+
+ template<>
+ struct property_map<oqgraph3::graph, edge_weight_t>
+ {
+ typedef void type;
+ typedef oqgraph3::edge_weight_property_map const_type;
+ };
+
+ template<>
+ struct property_map<oqgraph3::graph, vertex_index_t>
+ {
+ typedef void type;
+ typedef oqgraph3::vertex_index_property_map const_type;
+ };
+
+ template<>
+ struct property_map<oqgraph3::graph, edge_index_t>
+ {
+ typedef void type;
+ typedef oqgraph3::edge_index_property_map const_type;
+ };
+
+ inline property_map<
+ oqgraph3::graph,
+ edge_weight_t>::const_type::reference
+ get(
+ edge_weight_t,
+ const oqgraph3::graph& g,
+ const property_map<
+ oqgraph3::graph,
+ edge_weight_t>::const_type::key_type& key)
+ { return oqgraph3::row_cursor(key, const_cast<oqgraph3::graph*>(&g))->_weight; }
+
+ inline property_map<
+ oqgraph3::graph,
+ edge_weight_t>::const_type
+ get(edge_weight_t,
+ const oqgraph3::graph& g)
+ { return property_map<oqgraph3::graph, edge_weight_t>::const_type(g); }
+
+ inline property_map<
+ oqgraph3::graph,
+ edge_weight_t>::const_type::reference
+ get(property_map<oqgraph3::graph,
+ edge_weight_t>::const_type p,
+ const property_map<
+ oqgraph3::graph,
+ edge_weight_t>::const_type::key_type& key)
+ { return oqgraph3::row_cursor(
+ key, const_cast<oqgraph3::graph*>(&p._g))->_weight; }
+
+ inline property_map<
+ oqgraph3::graph,
+ edge_index_t>::const_type::reference
+ get(edge_index_t,
+ const oqgraph3::graph&,
+ const property_map<
+ oqgraph3::graph,
+ edge_index_t>::const_type::key_type& key)
+ { return key->_ref; }
+
+ inline property_map<oqgraph3::graph, edge_index_t>::const_type
+ get(edge_index_t, const oqgraph3::graph& g)
+ { return property_map<oqgraph3::graph, edge_index_t>::const_type(g); }
+
+ inline property_map<oqgraph3::graph, edge_index_t>::const_type::reference
+ get(property_map<oqgraph3::graph, edge_index_t>::const_type,
+ const property_map<oqgraph3::graph,
+ edge_index_t>::const_type::key_type& key)
+ { return key->_ref; }
+
+ inline property_map<oqgraph3::graph, vertex_index_t>::const_type::reference
+ get(vertex_index_t, const oqgraph3::graph&,
+ const property_map<oqgraph3::graph,
+ vertex_index_t>::const_type::key_type& key)
+ { return key->id; }
+
+ inline property_map<oqgraph3::graph, vertex_index_t>::const_type
+ get(vertex_index_t, const oqgraph3::graph& g)
+ { return property_map<oqgraph3::graph, vertex_index_t>::const_type(g); }
+
+ inline property_map<oqgraph3::graph, vertex_index_t>::const_type::reference
+ get(property_map<oqgraph3::graph, vertex_index_t>::const_type,
+ const property_map<oqgraph3::graph,
+ vertex_index_t>::const_type::key_type& key)
+ { return key->id; }
+
+
+ inline optional<graph_traits<oqgraph3::graph>::vertex_descriptor>
+ find_vertex(oqgraph3::vertex_id id, const oqgraph3::graph& g)
+ {
+ graph_traits<oqgraph3::graph>::vertex_descriptor tmp(
+ const_cast<oqgraph3::graph&>(g).vertex(id));
+ if (tmp)
+ return tmp;
+ else
+ return none;
+ }
+
+
+}
+
+#if 0
+
+
+ class OQGraph
+ {
+ public:
+
+ typedef OQGraph graph_type;
+
+ // more commonly used graph types
+ typedef void stored_vertex;
+ typedef std::size_t vertices_size_type;
+ typedef std::size_t edges_size_type;
+ typedef std::size_t degree_size_type;
+ typedef oqgraph3::vertex_descriptor vertex_descriptor;
+ typedef oqgraph3::edge_descriptor edge_descriptor;
+
+ // iterator types
+
+
+ typedef boost::adjacency_iterator_generator<
+ OQGraph,
+ vertex_descriptor,
+ out_edge_iterator>::type adjacency_iterator;
+
+ // miscellaneous types
+ typedef boost::directed_graph_tag graph_tag;
+ typedef boost::directed_tag directed_category;
+ typedef boost::allow_parallel_edge_tag edge_parallel_category;
+ typedef OQGraphTraversalCategory traversal_category;
+
+ typedef oqgraph3::vertex_id vertex_index_type;
+ typedef oqgraph3::edge_key::ref_type edge_index_type;
+
+ typedef void edge_property_type;
+ typedef void vertex_property_type;
+ typedef void graph_property_type;
+
+ // Graph concepts
+ static vertex_descriptor null_vertex()
+ { return vertex_descriptor(); }
+
+ oqgraph3::graph_cache_ptr _cache;
+
+ vertex_descriptor source(edge_descriptor e) const
+ { return _cache->vertex(oqgraph3::row_cursor(e)->first); }
+ vertex_descriptor target(edge_descriptor e) const
+ { return _cache->vertex(oqgraph3::row_cursor(e)->second); }
+ degree_size_type out_degree(vertex_descriptor v) const
+ { return v->out_edges().size(); }
+ std::pair<out_edge_iterator,out_edge_iterator>
+ out_edges(vertex_descriptor v) const
+ {
+ const oqgraph3::vertex_info::edge_list_type&
+ iter= v->out_edges();
+ return std::make_pair(
+ out_edge_iterator(iter.begin(), v),
+ out_edge_iterator(iter.end(), v));
+ }
+ degree_size_type in_degree(vertex_descriptor v) const
+ { return v->in_edges().size(); }
+ std::pair<in_edge_iterator,in_edge_iterator>
+ in_edges(vertex_descriptor v) const
+ {
+ const oqgraph3::vertex_info::edge_list_type&
+ iter= v->out_edges();
+ return std::make_pair(
+ in_edge_iterator(iter.begin(), v),
+ in_edge_iterator(iter.end(), v));
+ }
+ degree_size_type degree(vertex_descriptor v) const
+ { return v->degree(); }
+ vertex_descriptor vertex() const
+ { return null_vertex(); }
+ std::pair<edge_descriptor, bool> edge(
+ vertex_descriptor u, vertex_descriptor v) const
+ { edge_descriptor result= _cache->edge(u, v);
+ return std::make_pair(result, bool(result)); }
+ edges_size_type num_edges() const
+ { return _cache->num_edges(); }
+ std::pair<edge_iterator,edge_iterator>
+ edges() const
+ {
+ return std::make_pair(
+ edge_iterator(oqgraph3::row_cursor(_cache).first()),
+ edge_iterator(oqgraph3::row_cursor(_cache).end()));
+ }
+ };
+
+
+ struct vertex_index_property_map
+ {
+ typedef oqgraph3::vertex_id value_type;
+ typedef value_type reference;
+ typedef OQGraph::vertex_descriptor key_type;
+ typedef boost::readable_property_map_tag category;
+ };
+
+ struct edge_weight_property_map
+ {
+ typedef oqgraph3::weight_t value_type;
+ typedef value_type reference;
+ typedef OQGraph::edge_descriptor key_type;
+ typedef boost::readable_property_map_tag category;
+ };
+
+ struct edge_index_property_map
+ {
+ typedef oqgraph3::edge_key::ref_type value_type;
+ typedef const oqgraph3::edge_key::ref_type& reference;
+ typedef OQGraph::edge_descriptor key_type;
+ typedef boost::readable_property_map_tag category;
+ };
+}
+
+namespace boost
+{
+ template<>
+ struct property_map<open_query::OQGraph, edge_weight_t>
+ {
+ typedef void type;
+ typedef open_query::edge_weight_property_map const_type;
+ };
+
+ template<>
+ struct property_map<open_query::OQGraph, vertex_index_t>
+ {
+ typedef void type;
+ typedef open_query::vertex_index_property_map const_type;
+ };
+
+ template<>
+ struct property_map<open_query::OQGraph, edge_index_t>
+ {
+ typedef void type;
+ typedef open_query::edge_index_property_map const_type;
+ };
+
+ property_map<
+ open_query::OQGraph,
+ edge_weight_t>::const_type::reference
+ get(
+ edge_weight_t,
+ const open_query::OQGraph&,
+ const property_map<
+ open_query::OQGraph,
+ edge_weight_t>::const_type::key_type& key)
+ { return oqgraph3::row_cursor(key)->_weight; }
+
+ property_map<
+ open_query::OQGraph,
+ edge_weight_t>::const_type
+ get(edge_weight_t,
+ const open_query::OQGraph&)
+ { return property_map<open_query::OQGraph, edge_weight_t>::const_type(); }
+
+ property_map<
+ open_query::OQGraph,
+ edge_weight_t>::const_type::reference
+ get(property_map<open_query::OQGraph,
+ edge_weight_t>::const_type,
+ const property_map<
+ open_query::OQGraph,
+ edge_weight_t>::const_type::key_type& key)
+ { return oqgraph3::row_cursor(key)->_weight; }
+
+ property_map<
+ open_query::OQGraph,
+ edge_index_t>::const_type::reference
+ get(edge_index_t,
+ const open_query::OQGraph&,
+ const property_map<
+ open_query::OQGraph,
+ edge_index_t>::const_type::key_type& key)
+ { return key->_ref; }
+
+ property_map<open_query::OQGraph, edge_index_t>::const_type
+ get(edge_index_t, const open_query::OQGraph&)
+ { return property_map<open_query::OQGraph, edge_index_t>::const_type(); }
+
+ property_map<open_query::OQGraph, edge_index_t>::const_type::reference
+ get(property_map<open_query::OQGraph, edge_index_t>::const_type,
+ const property_map<open_query::OQGraph, edge_index_t>::const_type::key_type& key)
+ { return key->_ref; }
+
+ property_map<open_query::OQGraph, vertex_index_t>::const_type::reference
+ get(vertex_index_t, const open_query::OQGraph&,
+ const property_map<open_query::OQGraph, vertex_index_t>::const_type::key_type& key)
+ { return key->id; }
+
+ property_map<open_query::OQGraph, vertex_index_t>::const_type
+ get(vertex_index_t, const open_query::OQGraph&)
+ { return property_map<open_query::OQGraph, vertex_index_t>::const_type(); }
+
+ property_map<open_query::OQGraph, vertex_index_t>::const_type::reference
+ get(property_map<open_query::OQGraph, vertex_index_t>::const_type,
+ const property_map<open_query::OQGraph, vertex_index_t>::const_type::key_type& key)
+ { return key->id; }
+
+
+ optional<open_query::OQGraph::vertex_descriptor>
+ find_vertex(oqgraph3::vertex_id id, const open_query::OQGraph& g)
+ { open_query::OQGraph::vertex_descriptor tmp(g._cache->vertex(id));
+ if (tmp)
+ return tmp;
+ else
+ return none;
+ }
+
+
+
+
+ // IncidenceGraph concepts
+ inline open_query::OQGraph::vertex_descriptor
+ source(
+ open_query::OQGraph::edge_descriptor e,
+ open_query::OQGraph const& g)
+ { return g.source(e); }
+
+ inline open_query::OQGraph::vertex_descriptor
+ target(
+ open_query::OQGraph::edge_descriptor e,
+ open_query::OQGraph const& g)
+ { return g.target(e); }
+
+ inline open_query::OQGraph::degree_size_type
+ out_degree(
+ open_query::OQGraph::vertex_descriptor v,
+ open_query::OQGraph const& g)
+ { return g.out_degree(v); }
+
+ inline std::pair<
+ open_query::OQGraph::out_edge_iterator,
+ open_query::OQGraph::out_edge_iterator
+ >
+ out_edges(
+ open_query::OQGraph::vertex_descriptor v,
+ open_query::OQGraph const& g)
+ { return g.out_edges(v); }
+
+ // BidirectionalGraph concepts
+ inline open_query::OQGraph::degree_size_type
+ in_degree(
+ open_query::OQGraph::vertex_descriptor v,
+ open_query::OQGraph const& g)
+ { return g.in_degree(v); }
+
+ inline std::pair<
+ open_query::OQGraph::in_edge_iterator,
+ open_query::OQGraph::in_edge_iterator
+ >
+ in_edges(
+ open_query::OQGraph::vertex_descriptor v,
+ open_query::OQGraph const& g)
+ { return g.in_edges(v); }
+
+
+ inline open_query::OQGraph::degree_size_type
+ degree(
+ open_query::OQGraph::vertex_descriptor v,
+ open_query::OQGraph const& g)
+ { return g.degree(v); }
+
+ // AdjacencyGraph concepts
+ //inline std::pair<
+ // open_query::OQGraph::adjacency_iterator,
+ // open_query::OQGraph::adjacency_iterator
+ // >
+ //adjacent_vertices(
+ // open_query::OQGraph::vertex_descriptor v,
+ // open_query::OQGraph const& g)
+ //{ return g.adjacent_vertices(v, g.impl()); }
+
+ open_query::OQGraph::vertex_descriptor
+ vertex(
+ open_query::OQGraph::vertices_size_type n,
+ open_query::OQGraph const& g)
+ { return g.vertex(); }
+
+ std::pair<open_query::OQGraph::edge_descriptor, bool>
+ edge(
+ open_query::OQGraph::vertex_descriptor u,
+ open_query::OQGraph::vertex_descriptor v,
+ open_query::OQGraph const& g)
+ { return g.edge(u, v); }
+
+
+ // Vertex index management
+ inline open_query::OQGraph::vertex_index_type
+ get_vertex_index(
+ open_query::OQGraph::vertex_descriptor v,
+ open_query::OQGraph const& g)
+ { return get(boost::vertex_index, g, v); }
+
+ // Edge index management
+ inline const open_query::OQGraph::edge_index_type&
+ get_edge_index(
+ open_query::OQGraph::edge_descriptor v,
+ open_query::OQGraph const& g)
+ { return get(boost::edge_index, g, v); }
+}
+
+#endif
diff --git a/storage/oqgraph/oqgraph_thunk.cc b/storage/oqgraph/oqgraph_thunk.cc
new file mode 100644
index 00000000000..d93fcd2992d
--- /dev/null
+++ b/storage/oqgraph/oqgraph_thunk.cc
@@ -0,0 +1,975 @@
+/* Copyright (C) 2009-2011 Arjen G Lentz & Antony T Curtis for Open Query
+
+ This program 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; version 2 of the License, or
+ (at your option) any later version.
+
+ This program 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.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/* ======================================================================
+ Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+ Mk.III implementation by Antony Curtis & Arjen Lentz
+ For more information, documentation, support, enhancement engineering,
+ and non-GPL licensing, see http://openquery.com/graph
+ or contact graph@openquery.com
+ For packaged binaries, see http://ourdelta.org
+ ======================================================================
+*/
+
+#include "oqgraph_thunk.h"
+
+#include <boost/tuple/tuple.hpp>
+
+#define MYSQL_SERVER
+#include "mysql_priv.h"
+
+oqgraph3::vertex_info::~vertex_info()
+{ }
+
+void oqgraph3::vertex_info::release()
+{
+ if (!--(_ref_count))
+ {
+ oqgraph3::graph& cache= *_cache;
+ oqgraph3::graph::vertex_cache_type::const_iterator it;
+
+ if (!_on_gc)
+ {
+ cache._gc_vertices.push(this);
+ _on_gc= true;
+ }
+
+ while (!cache._gc_running && cache._gc_vertices.size() > 64)
+ {
+ cache._gc_running= true;
+ if (cache._gc_vertices.front()->_ref_count ||
+ (it= cache._cache_vertices.find(*cache._gc_vertices.front()))
+ == cache._cache_vertices.end())
+ {
+ cache._gc_vertices.front()->_on_gc= false;
+ }
+ else
+ {
+ cache._cache_vertices.quick_erase(it);
+ }
+ cache._gc_vertices.pop();
+ cache._gc_running= false;
+ }
+ }
+}
+
+oqgraph3::edge_key::~edge_key()
+{ }
+
+void oqgraph3::edge_key::release() const
+{
+ if (!--(_ref_count))
+ {
+ oqgraph3::graph& cache= *_cache;
+ oqgraph3::graph::edge_cache_type::const_iterator it;
+
+ if (!_on_gc)
+ {
+ cache._gc_edges.push(const_cast<edge_key*>(this));
+ _on_gc= true;
+ }
+
+ while (!cache._gc_running && cache._gc_edges.size() > 512)
+ {
+ cache._gc_running= true;
+ if (cache._gc_edges.front()->_ref_count ||
+ (it= cache._cache_edges.find(*cache._gc_edges.front()))
+ == cache._cache_edges.end())
+ {
+ cache._gc_edges.front()->_on_gc= false;
+ }
+ else
+ {
+ cache._cache_edges.quick_erase(it);
+ }
+ cache._gc_edges.pop();
+ cache._gc_running= false;
+ }
+ }
+}
+
+oqgraph3::graph::graph(
+ ::TABLE* table,
+ ::Field* source,
+ ::Field* target,
+ ::Field* weight)
+ : _gc_running(false)
+ , _ref_count(0)
+ , _table(table)
+ , _source(source)
+ , _target(target)
+ , _weight(weight)
+{
+ bitmap_set_bit(table->read_set, source->field_index);
+ bitmap_set_bit(table->read_set, target->field_index);
+ if (weight)
+ bitmap_set_bit(table->read_set, weight->field_index);
+
+ table->file->column_bitmaps_signal();
+}
+
+oqgraph3::graph::~graph()
+{ }
+
+oqgraph3::row_cursor& oqgraph3::row_cursor::operator++()
+{
+ if (!_current)
+ return *this;
+
+ graph::edge_cache_type::iterator
+ current= _cache->_cache_edges.find(*_current);
+
+ if (current->second._next)
+ {
+ graph::edge_cache_type::iterator next=
+ _cache->_cache_edges.find(edge_key(*current->second._next));
+ if (_cache->_cache_edges.end() != next)
+ {
+ _current.reset(&next->first);
+ return *this;
+ }
+ }
+
+ TABLE& table= *_cache->_table;
+
+ table.file->ha_index_init(0, 1);
+
+ if (table.file->ha_index_read_map(
+ table.record[0],
+ reinterpret_cast<const uchar*>(current->first._ref.data()),
+ (key_part_map)((1 << table.key_info->key_parts) - 1),
+ HA_READ_AFTER_KEY))
+ {
+ table.file->ha_index_end();
+ _current.reset(0);
+ return *this;
+ }
+
+ update_virtual_fields(table.in_use, &table);
+
+ table.file->ha_index_end();
+
+ edge_key tmp(table.key_info->key_length, _cache);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ if (_cache->_cache_edges.end() != found)
+ {
+ // we already had a row, link them together
+ found->second._prev= &current->first._ref;
+ current->second._next= &found->first._ref;
+ _current.reset(&found->first);
+ return *this;
+ }
+
+ _current.reset(&_cache->_cache_edges.insert(
+ std::make_pair(
+ tmp,
+ row_info(
+ _cache->_source->val_int(),
+ _cache->_target->val_int(),
+ _cache->_weight ? _cache->_weight->val_real() : 1.0,
+ &_current->_ref,
+ 0
+ )
+ )).first->first);
+ return *this;
+}
+
+oqgraph3::row_cursor& oqgraph3::row_cursor::first()
+{
+ TABLE& table= *_cache->_table;
+
+ printf("%s:%d\n", __func__, __LINE__);
+ table.file->ha_index_init(0, 1);
+
+ printf("%s:%d\n", __func__, __LINE__);
+ if (!table.file->ha_index_first(table.record[0]))
+ {
+ printf("%s:%d\n", __func__, __LINE__);
+ update_virtual_fields(table.in_use, &table);
+
+ printf("%s:%d\n", __func__, __LINE__);
+ edge_key tmp(table.key_info->key_length, _cache);
+
+ printf("%s:%d\n", __func__, __LINE__);
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ printf("%s:%d\n", __func__, __LINE__);
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ printf("%s:%d\n", __func__, __LINE__);
+ if (found != _cache->_cache_edges.end())
+ {
+ // we already had a row
+ printf("%s:%d\n", __func__, __LINE__);
+ _current.reset(&found->first);
+ }
+ else
+ {
+ printf("%s:%d\n", __func__, __LINE__);
+ _current.reset(&_cache->_cache_edges.insert(
+ std::make_pair(
+ tmp,
+ row_info(
+ _cache->_source->val_int(),
+ _cache->_target->val_int(),
+ _cache->_weight ? _cache->_weight->val_real() : 1.0,
+ 0,
+ 0
+ )
+ )).first->first);
+ }
+ }
+
+ printf("%s:%d\n", __func__, __LINE__);
+ table.file->ha_index_end();
+
+ printf("%s:%d\n", __func__, __LINE__);
+ return *this;
+}
+
+oqgraph3::row_cursor& oqgraph3::row_cursor::last()
+{
+ TABLE& table= *_cache->_table;
+
+ table.file->ha_index_init(0, 1);
+
+ if (!table.file->ha_index_last(table.record[0]))
+ {
+ update_virtual_fields(table.in_use, &table);
+
+ edge_key tmp(table.key_info->key_length, _cache);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ if (found != _cache->_cache_edges.end())
+ {
+ // we already had a row
+ _current.reset(&found->first);
+ }
+ else
+ {
+ _current.reset(&_cache->_cache_edges.insert(
+ std::make_pair(
+ tmp,
+ row_info(
+ _cache->_source->val_int(),
+ _cache->_target->val_int(),
+ _cache->_weight ? _cache->_weight->val_real() : 1.0,
+ 0,
+ 0
+ )
+ )).first->first);
+ }
+ }
+
+ table.file->ha_index_end();
+
+ return *this;
+}
+
+oqgraph3::row_cursor& oqgraph3::row_cursor::operator--()
+{
+ if (!_current)
+ return last();
+
+ graph::edge_cache_type::iterator
+ current= _cache->_cache_edges.find(*_current);
+
+ if (current->second._prev)
+ {
+ graph::edge_cache_type::iterator prev=
+ _cache->_cache_edges.find(edge_key(*current->second._prev));
+ if (_cache->_cache_edges.end() != prev)
+ {
+ _current.reset(&prev->first);
+ return *this;
+ }
+ }
+
+ TABLE& table= *_cache->_table;
+ table.file->ha_index_init(0, 1);
+
+ if (table.file->ha_index_read_map(
+ table.record[0],
+ reinterpret_cast<const uchar*>(current->first._ref.data()),
+ (key_part_map)((1 << table.key_info->key_parts) - 1),
+ HA_READ_BEFORE_KEY))
+ {
+ table.file->ha_index_end();
+ _current.reset();
+ return *this;
+ }
+
+ update_virtual_fields(table.in_use, &table);
+
+ table.file->ha_index_end();
+
+ edge_key tmp(table.key_info->key_length, _cache);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ if (_cache->_cache_edges.end() != found)
+ {
+ // we already had a row, link them together
+ found->second._next= &current->first._ref;
+ current->second._prev= &found->first._ref;
+ _current.reset(&found->first);
+ return *this;
+ }
+
+ _current.reset(&_cache->_cache_edges.insert(
+ std::make_pair(
+ tmp,
+ row_info(
+ _cache->_source->val_int(),
+ _cache->_target->val_int(),
+ _cache->_weight ? _cache->_weight->val_real() : 1.0,
+ 0,
+ &_current->_ref
+ )
+ )).first->first);
+ return *this;
+}
+
+oqgraph3::row_cursor& oqgraph3::row_cursor::operator+=(difference_type delta)
+{
+ if (!delta || !_current)
+ return *this;
+
+ if (delta < 0)
+ return *this -= (-delta);
+
+ graph::edge_cache_type::iterator
+ current= _cache->_cache_edges.find(*_current);
+
+ bool index_started= false;
+ TABLE& table= *_cache->_table;
+
+ while (delta-- > 0)
+ {
+ if (_cache->_cache_edges.end() != current)
+ {
+ if (current->second._next)
+ {
+ graph::edge_cache_type::iterator
+ next= _cache->_cache_edges.find(edge_key(*current->second._next));
+
+ if (_cache->_cache_edges.end() != next)
+ {
+ current= next;
+ continue;
+ }
+
+ if (!index_started)
+ {
+ table.file->ha_index_init(0, 1);
+ index_started= true;
+ }
+
+ if (table.file->ha_index_read_map(
+ table.record[0],
+ reinterpret_cast<const uchar*>(current->second._next->data()),
+ (key_part_map)((1 << table.key_info->key_parts) - 1),
+ HA_READ_KEY_OR_NEXT))
+ {
+ table.file->ha_index_end();
+ _current.reset();
+ return *this;
+ }
+ }
+ else
+ {
+ if (!index_started)
+ {
+ table.file->ha_index_init(0, 1);
+ index_started= true;
+ }
+
+ if (table.file->ha_index_read_map(
+ table.record[0],
+ reinterpret_cast<const uchar*>(current->first._ref.data()),
+ (key_part_map)((1 << table.key_info->key_parts) - 1),
+ HA_READ_AFTER_KEY))
+ {
+ table.file->ha_index_end();
+ _current.reset();
+ return *this;
+ }
+ }
+
+ edge_key tmp(table.key_info->key_length);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ if (found != _cache->_cache_edges.end())
+ {
+ // we already had a row, link them together
+ found->second._next= &current->first._ref;
+ current->second._prev= &found->first._ref;
+ }
+ current= found;
+ }
+ else
+ {
+ if (!index_started)
+ return *this;
+
+ if (table.file->ha_index_next(table.record[0]))
+ {
+ table.file->ha_index_end();
+ _current.reset();
+ return *this;
+ }
+
+ edge_key tmp(table.key_info->key_length);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ current= _cache->_cache_edges.find(tmp);
+ }
+ }
+
+ if (index_started)
+ {
+ table.file->ha_index_end();
+ }
+
+ return *this;
+}
+
+oqgraph3::row_cursor& oqgraph3::row_cursor::operator-=(difference_type delta)
+{
+ if (!delta || !_current)
+ return *this;
+
+ if (delta < 0)
+ return *this += (-delta);
+
+ graph::edge_cache_type::iterator
+ current= _cache->_cache_edges.find(*_current);
+
+ bool index_started= false;
+ TABLE& table= *_cache->_table;
+
+ while (delta-- > 0)
+ {
+ if (_cache->_cache_edges.end() != current)
+ {
+ if (current->second._next)
+ {
+ graph::edge_cache_type::iterator next=
+ _cache->_cache_edges.find(edge_key(*current->second._next));
+
+ if (_cache->_cache_edges.end() != next)
+ {
+ current= next;
+ continue;
+ }
+
+ if (!index_started)
+ {
+ table.file->ha_index_init(0, 1);
+ index_started= true;
+ }
+
+ if (table.file->ha_index_read_map(
+ table.record[0],
+ reinterpret_cast<const uchar*>(current->second._next->data()),
+ (key_part_map)((1 << table.key_info->key_parts) - 1),
+ HA_READ_KEY_OR_PREV))
+ {
+ table.file->ha_index_end();
+ return first();
+ }
+ }
+ else
+ {
+ if (!index_started)
+ {
+ table.file->ha_index_init(0, 1);
+ index_started= true;
+ }
+
+ if (table.file->ha_index_read_map(
+ table.record[0],
+ reinterpret_cast<const uchar*>(current->first._ref.data()),
+ (key_part_map)((1 << table.key_info->key_parts) - 1),
+ HA_READ_BEFORE_KEY))
+ {
+ table.file->ha_index_end();
+ return first();
+ }
+ }
+
+ edge_key tmp(table.key_info->key_length);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ if (_cache->_cache_edges.end() != found)
+ {
+ // we already had a row, link them together
+ found->second._next= &current->first._ref;
+ current->second._prev= &found->first._ref;
+ }
+ current= found;
+ }
+ else
+ {
+ if (!index_started)
+ return first();
+
+ if (table.file->ha_index_prev(table.record[0]))
+ {
+ table.file->ha_index_end();
+ return first();
+ }
+
+ edge_key tmp(table.key_info->key_length);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ current= _cache->_cache_edges.find(tmp);
+ }
+ }
+
+ if (index_started)
+ {
+ table.file->ha_index_end();
+ }
+
+ return *this;
+}
+
+oqgraph3::vertex_descriptor oqgraph3::graph::vertex(vertex_id id)
+{
+ vertex_cache_type::const_iterator
+ found= _cache_vertices.find(vertex_info(id));
+
+ if (_cache_vertices.end() != found)
+ return vertex_descriptor(const_cast<vertex_info*>(found.operator->()));
+
+ return vertex_descriptor(const_cast<vertex_info*>(
+ _cache_vertices.insert(vertex_info(id, this)).first.operator->()));
+}
+
+oqgraph3::edge_descriptor oqgraph3::graph::edge(const edge_key& key)
+{
+ edge_cache_type::const_iterator
+ found= _cache_edges.find(key);
+
+ if (_cache_edges.end() != found)
+ return edge_descriptor(&found->first);
+
+ TABLE& table= *_table;
+
+ table.file->ha_index_init(0, 0);
+
+ if (table.file->ha_index_read_map(
+ table.record[0],
+ reinterpret_cast<const uchar*>(key._ref.data()),
+ (key_part_map)((1 << table.key_info->key_parts) - 1),
+ HA_READ_KEY_EXACT))
+ {
+ table.file->ha_index_end();
+ return edge_descriptor();
+ }
+
+ update_virtual_fields(table.in_use, &table);
+
+ table.file->ha_index_end();
+
+ return edge_descriptor(&_cache_edges.insert(
+ std::make_pair(
+ edge_key(key, this),
+ row_info(
+ _source->val_int(),
+ _target->val_int(),
+ _weight ? _weight->val_real() : 1.0,
+ 0,
+ 0
+ )
+ )).first->first);
+}
+
+oqgraph3::edge_descriptor oqgraph3::graph::edge(
+ const vertex_descriptor& source,
+ const vertex_descriptor& target)
+{
+ vertex_cache_type::const_iterator xsource= _cache_vertices.find(*source);
+
+ if (_cache_vertices.end() != xsource && xsource->_out_edges)
+ {
+ const vertex_info::edge_list_type& edges= *xsource->_out_edges;
+ for (vertex_info::edge_list_type::const_iterator
+ it= edges.begin(), end= edges.end(); end != it; ++it)
+ {
+ edge_cache_type::const_iterator
+ found= _cache_edges.find(edge_key(*it));
+
+ if (_cache_edges.end() != found &&
+ target->id == found->second.second)
+ {
+ return edge_descriptor(&found->first);
+ }
+ }
+ return edge_descriptor();
+ }
+
+ vertex_cache_type::const_iterator xtarget= _cache_vertices.find(*target);
+
+ if (_cache_vertices.end() != xtarget && xtarget->_in_edges)
+ {
+ const vertex_info::edge_list_type& edges= *xtarget->_in_edges;
+ for (vertex_info::edge_list_type::const_iterator
+ it= edges.begin(), end= edges.end(); end != it; ++it)
+ {
+ edge_cache_type::const_iterator
+ found= _cache_edges.find(edge_key(*it));
+
+ if (_cache_edges.end() != found &&
+ source->id == found->second.first)
+ {
+ return edge_descriptor(&found->first);
+ }
+ }
+ return edge_descriptor();
+ }
+
+ // If we have an index which has both key parts, we can use that
+ // to quickly retrieve the edge descriptor.
+
+ TABLE& table= *_table;
+
+ uint source_fieldpos= _source->offset(table.record[0]);
+ uint target_fieldpos= _target->offset(table.record[0]);
+ int i= 0;
+ for( ::KEY *key_info= table.s->key_info,
+ *key_end= key_info + table.s->keys;
+ key_info < key_end; ++key_info, ++i)
+ {
+ if (key_info->key_parts < 2)
+ continue;
+ if ((key_info->key_part[0].offset == source_fieldpos &&
+ key_info->key_part[1].offset == target_fieldpos) ||
+ (key_info->key_part[0].offset == target_fieldpos &&
+ key_info->key_part[1].offset == source_fieldpos))
+ {
+ // we can use this key
+ restore_record(&table, s->default_values);
+
+ bitmap_set_bit(table.write_set, _source->field_index);
+ bitmap_set_bit(table.write_set, _target->field_index);
+ _source->store(source->id, 1);
+ _target->store(target->id, 1);
+ bitmap_clear_bit(table.write_set, _source->field_index);
+ bitmap_clear_bit(table.write_set, _target->field_index);
+
+ uint key_len= key_info->key_part[0].store_length +
+ key_info->key_part[1].store_length;
+ uchar* key_prefix= (uchar*) my_alloca(key_len);
+
+ table.file->ha_index_init(i, 0);
+
+ key_copy(key_prefix, table.record[0], key_info, key_len);
+ if (!table.file->ha_index_read_map(
+ table.record[0], key_prefix, (key_part_map)3, HA_READ_KEY_EXACT))
+ {
+ // We have found the edge,
+
+ update_virtual_fields(table.in_use, &table);
+
+ table.file->ha_index_end();
+ my_afree(key_prefix);
+
+ edge_key tmp(table.key_info->key_length, this);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache_edges.find(tmp);
+ if (_cache_edges.end() != found)
+ {
+ // we already had the edge
+ return edge_descriptor(&found->first);
+ }
+
+ return edge_descriptor(&_cache_edges.insert(
+ std::make_pair(
+ tmp,
+ row_info(
+ _source->val_int(),
+ _target->val_int(),
+ _weight ? _weight->val_real() : 1.0,
+ 0,
+ 0
+ )
+ )).first->first);
+ }
+ }
+ }
+
+ const vertex_info::edge_list_type& edges= vertex(source->id)->out_edges();
+ for (vertex_info::edge_list_type::const_iterator
+ it= edges.begin(), end= edges
+ .end(); end != it; ++it)
+ {
+ edge_cache_type::const_iterator
+ found= _cache_edges.find(edge_key(*it));
+
+ if (_cache_edges.end() != found &&
+ target->id == found->second.second)
+ {
+ return edge_descriptor(&found->first);
+ }
+ }
+
+ return edge_descriptor();
+}
+
+oqgraph3::edges_size_type oqgraph3::graph::num_edges() const
+{
+ return _table->file->stats.records;
+}
+
+const oqgraph3::vertex_info::edge_list_type&
+oqgraph3::vertex_info::out_edges()
+{
+ if (!_out_edges)
+ {
+ _out_edges = edge_list_type();
+ TABLE& table= *_cache->_table;
+
+ uint source_fieldpos= _cache->_source->offset(table.record[0]);
+ int i= 0;
+ for( ::KEY *key_info= table.s->key_info,
+ *key_end= key_info + table.s->keys;
+ key_info < key_end; ++key_info, ++i)
+ {
+ if (key_info->key_part[0].offset == source_fieldpos)
+ {
+ // we can use this key
+ restore_record(&table, s->default_values);
+
+ bitmap_set_bit(table.write_set, _cache->_source->field_index);
+ _cache->_source->store(id, 1);
+ bitmap_clear_bit(table.write_set, _cache->_source->field_index);
+
+ uint key_len= key_info->key_part[0].store_length;
+ uchar* key= (uchar*) my_alloca(key_len);
+
+ table.file->ha_index_init(i, 1);
+
+ key_copy(key, table.record[0], key_info, key_len);
+ if (!table.file->ha_index_read_map(
+ table.record[0], key, (key_part_map)1, HA_READ_KEY_EXACT))
+ {
+ // We have found an edge,
+ do
+ {
+ update_virtual_fields(table.in_use, &table);
+
+ edge_key tmp(table.key_info->key_length, _cache);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ if (_cache->_cache_edges.end() == found)
+ {
+ found= _cache->_cache_edges.insert(
+ std::make_pair(
+ tmp,
+ row_info(
+ _cache->_source->val_int(),
+ _cache->_target->val_int(),
+ _cache->_weight ? _cache->_weight->val_real() : 1.0,
+ 0,
+ 0
+ )
+ )).first;
+ }
+ _out_edges->push_back(found->first._ref);
+ }
+ while (!table.file->ha_index_next_same(
+ table.record[0], key, key_len));
+
+ table.file->ha_index_end();
+ my_afree(key);
+ break;
+ }
+ table.file->ha_index_end();
+ }
+ }
+ }
+ return *_out_edges;
+}
+
+const oqgraph3::vertex_info::edge_list_type&
+oqgraph3::vertex_info::in_edges()
+{
+ if (!_in_edges)
+ {
+ _in_edges = edge_list_type();
+ TABLE& table= *_cache->_table;
+
+ uint target_fieldpos= _cache->_target->offset(table.record[0]);
+ int i= 0;
+ for( ::KEY *key_info= table.s->key_info,
+ *key_end= key_info + table.s->keys;
+ key_info < key_end; ++key_info, ++i)
+ {
+ if (key_info->key_part[0].offset == target_fieldpos)
+ {
+ // we can use this key
+ restore_record(&table, s->default_values);
+
+ bitmap_set_bit(table.write_set, _cache->_target->field_index);
+ _cache->_target->store(id, 1);
+ bitmap_clear_bit(table.write_set, _cache->_target->field_index);
+
+ uint key_len= key_info->key_part[0].store_length;
+ uchar* key= (uchar*) my_alloca(key_len);
+
+ table.file->ha_index_init(i, 1);
+
+ key_copy(key, table.record[0], key_info, key_len);
+ if (!table.file->ha_index_read_map(
+ table.record[0], key, (key_part_map)1, HA_READ_KEY_EXACT))
+ {
+ // We have found an edge,
+ do
+ {
+ update_virtual_fields(table.in_use, &table);
+
+ edge_key tmp(table.key_info->key_length, _cache);
+
+ key_copy(
+ reinterpret_cast<uchar*>(const_cast<char*>(tmp._ref.data())),
+ table.record[0],
+ table.key_info,
+ tmp._ref.size(), true);
+
+ graph::edge_cache_type::iterator
+ found= _cache->_cache_edges.find(tmp);
+ if (_cache->_cache_edges.end() == found)
+ {
+ found= _cache->_cache_edges.insert(
+ std::make_pair(
+ tmp,
+ row_info(
+ _cache->_source->val_int(),
+ _cache->_target->val_int(),
+ _cache->_weight ? _cache->_weight->val_real() : 1.0,
+ 0,
+ 0
+ )
+ )).first;
+ }
+ _in_edges->push_back(found->first._ref);
+ }
+ while (!table.file->ha_index_next_same(
+ table.record[0], key, key_len));
+
+ table.file->ha_index_end();
+ my_afree(key);
+ break;
+ }
+ table.file->ha_index_end();
+ }
+ }
+ }
+ return *_in_edges;
+}
+
+std::size_t oqgraph3::vertex_info::degree()
+{
+ return out_edges().size() + in_edges().size();
+}
+
+oqgraph3::degree_size_type oqgraph3::vertex_descriptor::in_degree() const
+{
+ return (*this)->in_edges().size();
+}
+
+oqgraph3::degree_size_type oqgraph3::vertex_descriptor::out_degree() const
+{
+ return (*this)->out_edges().size();
+}
+
+oqgraph3::vertex_descriptor oqgraph3::edge_descriptor::source() const
+{
+ return (*this)->_cache->vertex(
+ oqgraph3::row_cursor(*this, (*this)->_cache)->first);
+}
+
+oqgraph3::vertex_descriptor oqgraph3::edge_descriptor::target() const
+{
+ return (*this)->_cache->vertex(
+ oqgraph3::row_cursor(*this, (*this)->_cache)->second);
+}
+
diff --git a/storage/oqgraph/oqgraph_thunk.h b/storage/oqgraph/oqgraph_thunk.h
new file mode 100644
index 00000000000..1ea3cbcc861
--- /dev/null
+++ b/storage/oqgraph/oqgraph_thunk.h
@@ -0,0 +1,415 @@
+/* Copyright (C) 2009-2011 Arjen G Lentz & Antony T Curtis for Open Query
+
+ This program 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; version 2 of the License, or
+ (at your option) any later version.
+
+ This program 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.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+/* ======================================================================
+ Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+ Mk.III implementation by Antony Curtis & Arjen Lentz
+ For more information, documentation, support, enhancement engineering,
+ and non-GPL licensing, see http://openquery.com/graph
+ or contact graph@openquery.com
+ For packaged binaries, see http://ourdelta.org
+ ======================================================================
+*/
+
+#pragma once
+
+#include <list>
+#include <queue>
+#include <string>
+#include <utility>
+
+#include <boost/intrusive_ptr.hpp>
+#include <boost/optional.hpp>
+#include <boost/unordered_map.hpp>
+#include <boost/unordered_set.hpp>
+#include <boost/pending/queue.hpp>
+#include <boost/ptr_container/ptr_deque.hpp>
+
+#include "graphcore-types.h"
+
+namespace oqgraph3
+{
+ typedef open_query::VertexID vertex_id;
+ typedef open_query::EdgeWeight weight_t;
+
+ typedef size_t vertices_size_type;
+ typedef size_t edges_size_type;
+ typedef size_t degree_size_type;
+
+ struct graph;
+ struct vertex_info;
+
+ typedef boost::intrusive_ptr<graph> graph_ptr;
+
+ struct edge_key
+ {
+ typedef std::string ref_type;
+
+ ref_type _ref;
+ mutable int _ref_count;
+
+ graph_ptr _cache;
+ mutable bool _on_gc;
+
+ operator const ref_type&() const { return _ref; }
+
+ explicit edge_key(
+ std::size_t length,
+ const graph_ptr& cache= graph_ptr())
+ : _ref(length, '\0')
+ , _ref_count(0)
+ , _cache(cache)
+ { }
+
+ template <typename C, typename T, typename A>
+ explicit edge_key(const std::basic_string<C,T,A>& ref)
+ : _ref(ref.begin(), ref.end())
+ , _ref_count(0)
+ , _cache(0)
+ { }
+
+ edge_key(const edge_key& src)
+ : _ref(src._ref)
+ , _ref_count(0)
+ , _cache(src._cache)
+ { }
+
+ edge_key(const edge_key& src, const graph_ptr& cache)
+ : _ref(src._ref)
+ , _ref_count(0)
+ , _cache(cache)
+ { }
+
+ ~edge_key();
+
+ void release() const;
+
+ friend void intrusive_ptr_add_ref(const edge_key* ptr)
+ { ++ptr->_ref_count; }
+ friend void intrusive_ptr_release(const edge_key* ptr)
+ { ptr->release(); }
+ };
+
+ struct vertex_info
+ {
+ typedef vertex_id vertex_id_type;
+ typedef std::list<edge_key::ref_type> edge_list_type;
+
+ const vertex_id_type id;
+ mutable int _ref_count;
+ boost::optional<edge_list_type> _in_edges;
+ boost::optional<edge_list_type> _out_edges;
+
+ graph_ptr _cache;
+ mutable bool _on_gc;
+
+ explicit vertex_info(
+ vertex_id_type i,
+ const graph_ptr& cache= graph_ptr())
+ : id(i)
+ , _ref_count(0)
+ , _cache(cache)
+ , _on_gc(false)
+ { }
+ ~vertex_info();
+
+ const edge_list_type& out_edges();
+ const edge_list_type& in_edges();
+ std::size_t degree();
+
+ void release();
+
+ friend void intrusive_ptr_add_ref(vertex_info* ptr)
+ { ++ptr->_ref_count; }
+ friend void intrusive_ptr_release(vertex_info* ptr)
+ { ptr->release(); }
+ };
+
+ struct vertex_descriptor
+ : public boost::intrusive_ptr<vertex_info>
+ {
+ vertex_descriptor()
+ : boost::intrusive_ptr<vertex_info>()
+ { }
+
+ vertex_descriptor(vertex_info* v)
+ : boost::intrusive_ptr<vertex_info>(v)
+ { }
+
+ vertex_descriptor(const vertex_descriptor& v)
+ : boost::intrusive_ptr<vertex_info>(v)
+ { }
+
+ degree_size_type in_degree() const;
+ degree_size_type out_degree() const;
+
+ friend degree_size_type in_degree(const vertex_descriptor& v, const graph&)
+ { return v.in_degree(); }
+ friend degree_size_type out_degree(const vertex_descriptor& v, const graph&)
+ { return v.out_degree(); }
+ };
+
+ struct edge_descriptor
+ : public boost::intrusive_ptr<const edge_key>
+ {
+ edge_descriptor()
+ : boost::intrusive_ptr<const edge_key>()
+ { }
+
+ edge_descriptor(const edge_key* e)
+ : boost::intrusive_ptr<const edge_key>(e)
+ { }
+
+ edge_descriptor(const edge_descriptor& e)
+ : boost::intrusive_ptr<const edge_key>(e)
+ { }
+
+ vertex_descriptor source() const;
+ vertex_descriptor target() const;
+
+ friend vertex_descriptor source(const edge_descriptor& e, const graph&)
+ { return e.source(); }
+
+ friend vertex_descriptor target(const edge_descriptor& e, const graph&)
+ { return e.target(); }
+ };
+
+ struct row_info
+ : public std::pair<vertex_id, vertex_id>
+ {
+ weight_t _weight;
+
+ const edge_key::ref_type* _prev;
+ const edge_key::ref_type* _next;
+
+ row_info(
+ first_type source,
+ second_type target,
+ weight_t weight,
+ const edge_key::ref_type* prev,
+ const edge_key::ref_type* next)
+ : std::pair<first_type, second_type>(source, target)
+ , _weight(weight)
+ , _prev(prev)
+ , _next(next)
+ { }
+ };
+
+ namespace internal
+ {
+ template <typename Value> struct hash
+ : public std::unary_function<Value, std::size_t>
+ {
+ boost::hash<Value> ref_hasher;
+ std::size_t operator()(const Value& v) const
+ {
+ return ref_hasher(v);
+ }
+ };
+
+ template <typename Value> struct equal_to
+ : public std::binary_function<Value, Value, bool>
+ {
+ std::equal_to<Value> ref_equals;
+ bool operator()(const Value& x, const Value& y) const
+ {
+ return ref_equals(x, y);
+ }
+ };
+
+ template <> struct hash<edge_key>
+ : public std::unary_function<edge_key, std::size_t>
+ {
+ boost::hash<edge_key::ref_type> ref_hasher;
+ std::size_t operator()(edge_key const& v) const
+ {
+ return ref_hasher(v._ref);
+ }
+ };
+
+ template <> struct hash<const edge_key*>
+ : public std::unary_function<const edge_key*, std::size_t>
+ {
+ boost::hash<edge_key::ref_type> ref_hasher;
+ std::size_t operator()(const edge_key* const& v) const
+ {
+ return ref_hasher(v->_ref);
+ }
+ };
+
+ template <> struct hash<vertex_info>
+ : public std::unary_function<vertex_info, std::size_t>
+ {
+ boost::hash<vertex_info::vertex_id_type> id_hasher;
+ std::size_t operator()(vertex_info const& v) const
+ {
+ return id_hasher(v.id);
+ }
+ };
+
+ template <> struct equal_to<edge_key>
+ : public std::binary_function<edge_key, edge_key, bool>
+ {
+ std::equal_to<edge_key::ref_type> ref_equals;
+ bool operator()(const edge_key& x, const edge_key& y) const
+ {
+ return ref_equals(x._ref, y._ref);
+ }
+ };
+
+ template <> struct equal_to<const edge_key*>
+ : public std::binary_function<const edge_key*, edge_key, bool>
+ {
+ std::equal_to<edge_key::ref_type> ref_equals;
+ bool operator()(const edge_key*& x, const edge_key*& y) const
+ {
+ return ref_equals(x->_ref, y->_ref);
+ }
+ };
+
+
+ template <> struct equal_to<vertex_info>
+ : public std::binary_function<vertex_info, vertex_info, bool>
+ {
+ std::equal_to<vertex_info::vertex_id_type> id_equals;
+ bool operator()(const vertex_info& x, const vertex_info& y) const
+ {
+ return id_equals(x.id, y.id);
+ }
+ };
+ }
+
+ struct graph
+ {
+ typedef boost::unordered_map<
+ edge_key,
+ row_info,
+ internal::hash<edge_key>,
+ internal::equal_to<edge_key> > edge_cache_type;
+ typedef boost::unordered_set<
+ vertex_info,
+ internal::hash<vertex_info>,
+ internal::equal_to<vertex_info> > vertex_cache_type;
+
+ bool _gc_running;
+ mutable int _ref_count;
+
+ edge_cache_type _cache_edges;
+ boost::queue<edge_key*> _gc_edges;
+
+ vertex_cache_type _cache_vertices;
+ boost::queue<vertex_info*> _gc_vertices;
+
+ ::TABLE* _table;
+ ::Field* _source;
+ ::Field* _target;
+ ::Field* _weight;
+
+ graph(
+ ::TABLE* table,
+ ::Field* source,
+ ::Field* target,
+ ::Field* weight= 0);
+ ~graph();
+
+ vertex_descriptor vertex(vertex_id);
+ edge_descriptor edge(const edge_key&);
+ edge_descriptor edge(
+ const vertex_descriptor&,
+ const vertex_descriptor&);
+
+ edges_size_type num_edges() const;
+
+ friend edges_size_type num_edges(const graph& g)
+ { return g.num_edges(); }
+
+ friend void intrusive_ptr_add_ref(graph* ptr)
+ { ptr->_ref_count++; }
+
+ friend void intrusive_ptr_release(graph* ptr)
+ { ptr->_ref_count--; }
+ };
+
+ struct row_cursor
+ {
+ typedef std::random_access_iterator_tag iterator_category;
+ typedef graph::edge_cache_type::value_type::second_type value_type;
+ typedef value_type* pointer;
+ typedef const value_type* const_pointer;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+ typedef graph::edge_cache_type::size_type size_type;
+ typedef graph::edge_cache_type::difference_type difference_type;
+
+ graph_ptr _cache;
+ edge_descriptor _current;
+
+ explicit row_cursor(graph* cache)
+ : _cache(cache)
+ { }
+
+ explicit row_cursor(const graph_ptr& cache)
+ : _cache(cache)
+ { }
+
+ explicit row_cursor(const edge_descriptor& e, const graph_ptr& cache)
+ : _cache(cache)
+ , _current(e)
+ { }
+
+ reference operator*() const
+ { return _cache->_cache_edges.find(*_current)->second; }
+
+ pointer operator->() const
+ { return &_cache->_cache_edges.find(*_current)->second; }
+
+ row_cursor& operator++();
+
+ row_cursor operator++(int)
+ { row_cursor tmp= *this; ++*this; return tmp; }
+
+ row_cursor& operator--();
+
+ row_cursor operator--(int)
+ { row_cursor tmp= *this; --*this; return tmp; }
+
+ row_cursor& operator+=(difference_type delta);
+
+ row_cursor operator+(difference_type delta) const
+ { row_cursor tmp= *this; return tmp += delta; }
+
+ row_cursor& operator-=(difference_type delta);
+
+ row_cursor operator-(difference_type delta) const
+ { row_cursor tmp= *this; return tmp -= delta; }
+
+ reference operator[](difference_type offset) const
+ { return *(*this + offset); }
+
+ row_cursor& first();
+ row_cursor& last();
+ row_cursor& end()
+ { _current.reset(); return *this; }
+
+ bool operator==(const row_cursor& x) const
+ { return _current == x._current; }
+
+ bool operator!=(const row_cursor& x) const
+ { return _current != x._current; }
+ };
+
+}
+
View Lorry Controller Status