summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xBUILD/SETUP.sh2
-rwxr-xr-xmysql-test/mysql-test-run.pl29
-rw-r--r--mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc4
-rw-r--r--mysql-test/suite/oqgraph/r/basic.result63
-rw-r--r--mysql-test/suite/oqgraph/t/basic-master.opt2
-rw-r--r--mysql-test/suite/oqgraph/t/basic.test45
-rw-r--r--storage/oqgraph/CMakeFiles.txt22
-rw-r--r--storage/oqgraph/Makefile.am96
-rw-r--r--storage/oqgraph/graphcore-graph.h48
-rw-r--r--storage/oqgraph/graphcore-types.h36
-rw-r--r--storage/oqgraph/graphcore.cc1099
-rw-r--r--storage/oqgraph/graphcore.h116
-rw-r--r--storage/oqgraph/graphstore.c356
-rw-r--r--storage/oqgraph/graphstore.h90
-rw-r--r--storage/oqgraph/ha_oqgraph.cc1040
-rw-r--r--storage/oqgraph/ha_oqgraph.h114
-rw-r--r--storage/oqgraph/oqgraph_config.h.in73
-rw-r--r--storage/oqgraph/oqgraph_probes.d19
-rw-r--r--storage/oqgraph/oqgraph_probes.h45
-rw-r--r--storage/oqgraph/plug.in32
20 files changed, 3329 insertions, 2 deletions
diff --git a/BUILD/SETUP.sh b/BUILD/SETUP.sh
index 30148cde360..b5116a18a8d 100755
--- a/BUILD/SETUP.sh
+++ b/BUILD/SETUP.sh
@@ -202,7 +202,7 @@ if test -z "$CC" ; then
fi
if test -z "$CXX" ; then
- CXX=gcc
+ CXX=g++
fi
# If ccache (a compiler cache which reduces build time)
diff --git a/mysql-test/mysql-test-run.pl b/mysql-test/mysql-test-run.pl
index 526077a7de1..a9d778b72b4 100755
--- a/mysql-test/mysql-test-run.pl
+++ b/mysql-test/mysql-test-run.pl
@@ -126,7 +126,7 @@ my $path_config_file; # The generated config file, var/my.cnf
# executables will be used by the test suite.
our $opt_vs_config = $ENV{'MTR_VS_CONFIG'};
-my $DEFAULT_SUITES= "binlog,federated,main,maria,rpl,innodb,parts";
+my $DEFAULT_SUITES= "binlog,federated,main,maria,rpl,innodb,parts,oqgraph";
our $opt_usage;
our $opt_list_options;
@@ -1933,6 +1933,33 @@ sub environment_setup {
$ENV{'EXAMPLE_PLUGIN_LOAD'}="--plugin_load=;EXAMPLE=".$plugin_filename.";";
}
+ # --------------------------------------------------------------------------
+ # Add the path where mysqld will find graph_engine.so
+ # --------------------------------------------------------------------------
+ if ($mysql_version_id >= 50100 && !(IS_WINDOWS && $opt_embedded_server)) {
+ my $plugin_filename;
+ if (IS_WINDOWS)
+ {
+ $plugin_filename = "oqgraph_engine.dll";
+ }
+ else
+ {
+ $plugin_filename = "oqgraph_engine.so";
+ }
+ my $lib_oqgraph_plugin=
+ mtr_file_exists(vs_config_dirs('storage/oqgraph',$plugin_filename),
+ "$basedir/storage/oqgraph/.libs/".$plugin_filename,
+ "$basedir/lib/mariadb/plugin/".$plugin_filename,
+ "$basedir/lib/mysql/plugin/".$plugin_filename);
+ $ENV{'OQGRAPH_PLUGIN'}=
+ ($lib_oqgraph_plugin ? basename($lib_oqgraph_plugin) : "");
+ $ENV{'OQGRAPH_PLUGIN_OPT'}= "--plugin-dir=".
+ ($lib_oqgraph_plugin ? dirname($lib_oqgraph_plugin) : "");
+
+ $ENV{'GRAPH_ENGINE_SO'}="'".$plugin_filename."'";
+ $ENV{'OQGRAPH_PLUGIN_LOAD'}="--plugin_load=;OQGRAPH=".$plugin_filename.";";
+ }
+
# ----------------------------------------------------
# Add the path where mysqld will find mypluglib.so
# ----------------------------------------------------
diff --git a/mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc b/mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc
new file mode 100644
index 00000000000..6fc3c6a0632
--- /dev/null
+++ b/mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc
@@ -0,0 +1,4 @@
+disable_query_log;
+--require r/true.require
+select (PLUGIN_LIBRARY LIKE 'oqgraph_engine%') as `TRUE` from information_schema.plugins where PLUGIN_NAME='OQGRAPH';
+enable_query_log;
diff --git a/mysql-test/suite/oqgraph/r/basic.result b/mysql-test/suite/oqgraph/r/basic.result
new file mode 100644
index 00000000000..e90659c0986
--- /dev/null
+++ b/mysql-test/suite/oqgraph/r/basic.result
@@ -0,0 +1,63 @@
+drop table if exists graph;
+Warnings:
+Note 1051 Unknown table 'graph'
+CREATE TABLE graph (
+latch SMALLINT UNSIGNED NULL,
+origid BIGINT UNSIGNED NULL,
+destid BIGINT UNSIGNED NULL,
+weight DOUBLE NULL,
+seq BIGINT UNSIGNED NULL,
+linkid BIGINT UNSIGNED NULL,
+KEY (latch, origid, destid) USING HASH,
+KEY (latch, destid, origid) USING HASH
+) ENGINE=OQGRAPH;
+delete from graph;
+insert into graph(origid, destid) values (1,2), (2,1);
+insert into graph(origid, destid) values (1,3), (3,1);
+insert into graph(origid, destid) values (3,4), (4,3);
+insert into graph(origid, destid) values (3,5), (5,3);
+insert into graph(origid, destid) values (5,6), (6,5);
+select * from graph where latch = 2 and origid = 1 and weight = 1;
+latch origid destid weight seq linkid
+2 1 NULL 1 3 3
+2 1 NULL 1 2 2
+select * from graph where latch = 2 and origid = 1 and weight = 2;
+latch origid destid weight seq linkid
+2 1 NULL 2 5 5
+2 1 NULL 2 4 4
+select * from graph
+where latch = 2 and origid = 1 and (weight = 1 or weight = 2);
+latch origid destid weight seq linkid
+2 1 NULL 2 5 5
+2 1 NULL 2 4 4
+2 1 NULL 1 3 3
+2 1 NULL 1 2 2
+select * from graph where latch=1 and origid=1 and destid=6;
+latch origid destid weight seq linkid
+1 1 6 NULL 0 1
+1 1 6 1 1 3
+1 1 6 1 2 5
+1 1 6 1 3 6
+select * from graph where latch=1 and origid=1 and destid=4;
+latch origid destid weight seq linkid
+1 1 4 NULL 0 1
+1 1 4 1 1 3
+1 1 4 1 2 4
+select * from graph where latch=1 and origid=4 and destid=1;
+latch origid destid weight seq linkid
+1 4 1 NULL 0 4
+1 4 1 1 1 3
+1 4 1 1 2 1
+insert into graph (origid,destid) values (4,6);
+delete from graph where origid=5;
+delete from graph where origid=3 and destid=5;
+select * from graph where latch=1 and origid=1 and destid=6;
+latch origid destid weight seq linkid
+1 1 6 NULL 0 1
+1 1 6 1 1 3
+1 1 6 1 2 4
+1 1 6 1 3 6
+select * from graph where latch=1 and origid=6 and destid=1;
+latch origid destid weight seq linkid
+truncate table graph;
+drop table graph;
diff --git a/mysql-test/suite/oqgraph/t/basic-master.opt b/mysql-test/suite/oqgraph/t/basic-master.opt
new file mode 100644
index 00000000000..4fe63014479
--- /dev/null
+++ b/mysql-test/suite/oqgraph/t/basic-master.opt
@@ -0,0 +1,2 @@
+$OQGRAPH_PLUGIN_OPT
+$OQGRAPH_PLUGIN_LOAD
diff --git a/mysql-test/suite/oqgraph/t/basic.test b/mysql-test/suite/oqgraph/t/basic.test
new file mode 100644
index 00000000000..b39341ba3d5
--- /dev/null
+++ b/mysql-test/suite/oqgraph/t/basic.test
@@ -0,0 +1,45 @@
+-- source suite/oqgraph/include/have_oqgraph_engine.inc
+
+drop table if exists graph;
+
+CREATE TABLE graph (
+ latch SMALLINT UNSIGNED NULL,
+ origid BIGINT UNSIGNED NULL,
+ destid BIGINT UNSIGNED NULL,
+ weight DOUBLE NULL,
+ seq BIGINT UNSIGNED NULL,
+ linkid BIGINT UNSIGNED NULL,
+ KEY (latch, origid, destid) USING HASH,
+ KEY (latch, destid, origid) USING HASH
+ ) ENGINE=OQGRAPH;
+
+delete from graph;
+
+insert into graph(origid, destid) values (1,2), (2,1);
+insert into graph(origid, destid) values (1,3), (3,1);
+insert into graph(origid, destid) values (3,4), (4,3);
+insert into graph(origid, destid) values (3,5), (5,3);
+insert into graph(origid, destid) values (5,6), (6,5);
+
+select * from graph where latch = 2 and origid = 1 and weight = 1;
+
+select * from graph where latch = 2 and origid = 1 and weight = 2;
+
+select * from graph
+where latch = 2 and origid = 1 and (weight = 1 or weight = 2);
+
+select * from graph where latch=1 and origid=1 and destid=6;
+select * from graph where latch=1 and origid=1 and destid=4;
+select * from graph where latch=1 and origid=4 and destid=1;
+
+insert into graph (origid,destid) values (4,6);
+
+delete from graph where origid=5;
+delete from graph where origid=3 and destid=5;
+
+select * from graph where latch=1 and origid=1 and destid=6;
+select * from graph where latch=1 and origid=6 and destid=1;
+
+truncate table graph;
+
+drop table graph;
diff --git a/storage/oqgraph/CMakeFiles.txt b/storage/oqgraph/CMakeFiles.txt
new file mode 100644
index 00000000000..b039c1ddb44
--- /dev/null
+++ b/storage/oqgraph/CMakeFiles.txt
@@ -0,0 +1,22 @@
+# Copyright (C) 2006 MySQL AB
+#
+# 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.
+#
+# 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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+
+SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -DSAFEMALLOC -DSAFE_MUTEX")
+SET(CMAKE_C_FLAGS_DEBUG "${CMAKE_C_FLAGS_DEBUG} -DSAFEMALLOC -DSAFE_MUTEX")
+
+INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR}/include ${CMAKE_SOURCE_DIR}/sql
+ ${CMAKE_SOURCE_DIR}/regex
+ ${CMAKE_SOURCE_DIR}/extra/yassl/include)
+ADD_LIBRARY(oqgraph ha_oqgraph.cc)
diff --git a/storage/oqgraph/Makefile.am b/storage/oqgraph/Makefile.am
new file mode 100644
index 00000000000..727f92ceb25
--- /dev/null
+++ b/storage/oqgraph/Makefile.am
@@ -0,0 +1,96 @@
+# Copyright (C) 2007-2009 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.II 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
+# ======================================================================
+
+mysqlplugindir= $(pkglibdir)/plugin
+
+BOOST_CXXFLAGS = -frtti -fexceptions -fimplicit-templates
+#BOOST_CXXFLAGS+= -g
+#original flags before 2009-11-10
+#BOOST_CXXFLAGS+= -O3 -fomit-frame-pointer -fstrict-aliasing
+#BOOST_CXXFLAGS+= -momit-leaf-frame-pointer -falign-loops
+#modified flags:
+# - remove omit-frame-pointer, x86 specific (fails on PPC) + hinders debugging
+# Option details from gcc man:
+# Don't keep the frame pointer in a register for functions that don't need one.
+# This avoids the instructions to save, set up and restore frame pointers;
+# it also makes an extra register available in many functions.
+# It also makes debugging impossible on some machines.
+# (automatically gets enabled anyway by -O* on some architectures)
+BOOST_CXXFLAGS+= -O3 -fstrict-aliasing
+BOOST_CXXFLAGS+= -falign-loops
+BOOST_CXXFLAGS+= -fvisibility-inlines-hidden
+BOOST_CXXFLAGS+= -funroll-loops -fno-trapping-math
+
+EXTRA_DIST = ha_oqgraph.h ha_oqgraph.cc graphcore.cc \
+ graphcore-graph.h graphcore-types.h graphcore.h \
+ CMakeFiles.txt plug.in oqgraph_probes.d
+
+DTRACE = @DTRACE@
+DTRACEFLAGS = @DTRACEFLAGS@
+DTRACEFILES = .libs/liboqgraph_engine_la-ha_oqgraph.o
+
+ORIG_CXXFLAGS = @CXXFLAGS@
+CXXFLAGS=
+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_CXXFLAGS = $(ORIG_CXXFLAGS) $(BOOST_CXXFLAGS)
+
+if BUILD_OQGRAPH_FOR_MYSQL
+
+if BUILD_OQGRAPH_STANDALONE
+INCLUDES = -DDBUG_ON -DSAFE_MUTEX -DUNIV_MUST_NOT_INLINE -DEXTRA_DEBUG -DFORCE_INIT_OF_VARS -DSAFEMALLOC -DPEDANTIC_SAFEMALLOC -DSAFE_MUTEX -DHAVE_OQGRAPH $(MYSQL_INC)
+else
+INCLUDES = -I$(top_srcdir)/include -I$(top_builddir)/include -I$(top_srcdir)/regex -I$(top_srcdir)/sql -I$(srcdir) -DHAVE_OQGRAPH
+endif !BUILD_OQGRAPH_STANDALONE
+
+EXTRA_LTLIBRARIES = oqgraph_engine.la
+mysqlplugin_LTLIBRARIES = @plugin_oqgraph_shared_target@
+oqgraph_engine_la_SOURCES = ha_oqgraph.cc
+oqgraph_engine_la_LIBADD = libgraphcore.la
+
+if HAVE_DTRACE
+ oqgraph_engine_la_LIBADD += oqgraph_probes.o
+endif
+
+oqgraph_engine_la_LDFLAGS = -module -rpath $(mysqlplugindir)
+oqgraph_engine_la_CFLAGS = $(ORIG_CFLAGS) -DMYSQL_DYNAMIC_PLUGIN
+oqgraph_engine_la_CXXFLAGS = $(ORIG_CXXFLAGS) -DMYSQL_DYNAMIC_PLUGIN
+
+oqgraph_probes.h: oqgraph_probes.d
+ $(DTRACE) $(DTRACEFLAGS) -h -s oqgraph_probes.d
+ mv oqgraph_probes.h oqgraph_probes.h.bak
+ sed "s/#include <unistd.h>//g" oqgraph_probes.h.bak > oqgraph_probes.h
+ rm oqgraph_probes.h.bak
+
+oqgraph_probes.o:
+ $(DTRACE) $(DTRACEFLAGS) -G -s oqgraph_probes.d $(DTRACEFILES)
+
+endif BUILD_OQGRAPH_FOR_MYSQL
+
+# End
diff --git a/storage/oqgraph/graphcore-graph.h b/storage/oqgraph/graphcore-graph.h
new file mode 100644
index 00000000000..46ddfb5335b
--- /dev/null
+++ b/storage/oqgraph/graphcore-graph.h
@@ -0,0 +1,48 @@
+/* Copyright (C) 2007-2009 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.II 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
+ ======================================================================
+*/
+
+#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;
+
+#endif
diff --git a/storage/oqgraph/graphcore-types.h b/storage/oqgraph/graphcore-types.h
new file mode 100644
index 00000000000..7a7e4c62729
--- /dev/null
+++ b/storage/oqgraph/graphcore-types.h
@@ -0,0 +1,36 @@
+/* Copyright (C) 2007-2009 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.II 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
+ ======================================================================
+*/
+
+#ifndef oq_graphcore_types_h_
+#define oq_graphcore_types_h_
+namespace open_query
+{
+
+ typedef unsigned long long VertexID;
+ typedef double EdgeWeight;
+
+}
+#endif
diff --git a/storage/oqgraph/graphcore.cc b/storage/oqgraph/graphcore.cc
new file mode 100644
index 00000000000..178db2937ef
--- /dev/null
+++ b/storage/oqgraph/graphcore.cc
@@ -0,0 +1,1099 @@
+/* Copyright (C) 2007-2009 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.II 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 <strings.h>
+
+#define BOOST_ALL_NO_LIB 1
+
+#include <boost/config.hpp>
+
+#include <set>
+#include <stack>
+
+#include <boost/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>
+#include <boost/graph/reverse_graph.hpp>
+#include <boost/graph/graph_utility.hpp>
+
+#include "graphcore.h"
+
+using namespace open_query;
+using namespace boost;
+
+static const row empty_row = { 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;
+
+ typedef std::list<std::pair<Vertex,optional<EdgeWeight> > > shortest_path_list;
+ typedef shortest_path_list::iterator shortest_path_iterator;
+
+ template<typename ID, typename IDMap>
+ class id_equals_t
+ {
+ public:
+ id_equals_t(ID id, IDMap map)
+ : m_id(id), m_map(map)
+ { }
+ template<typename V>
+ bool operator()(V u) const
+ {
+ return m_map[u] == m_id;
+ }
+ private:
+ ID m_id;
+ IDMap m_map;
+ };
+
+ template<typename ID, typename IDMap>
+ inline id_equals_t<ID,IDMap>
+ id_equals(ID id, IDMap idmap)
+ {
+ return id_equals_t<ID,IDMap>(id, idmap);
+ }
+
+ template<typename T, typename Graph>
+ class target_equals_t
+ {
+ public:
+ target_equals_t(T target, Graph &g)
+ : m_target(target), m_g(g)
+ { }
+ template<typename V>
+ bool operator()(V u) const
+ {
+ return target(u, m_g) == m_target;
+ }
+ private:
+ T m_target;
+ Graph &m_g;
+ };
+
+ template<typename T, typename Graph>
+ inline target_equals_t<T,Graph>
+ target_equals(T target, Graph &g)
+ {
+ return target_equals_t<T,Graph>(target, g);
+ }
+
+ template<typename T, typename Graph>
+ class source_equals_t
+ {
+ public:
+ source_equals_t(T source, Graph &g)
+ : m_source(source), m_g(g)
+ { }
+ template<typename V>
+ bool operator()(V u) const
+ {
+ return source(u, m_g) == m_source;
+ }
+ private:
+ T m_source;
+ Graph &m_g;
+ };
+
+ template<typename T, typename Graph>
+ inline source_equals_t<T,Graph>
+ source_equals(T source, Graph &g)
+ {
+ return source_equals_t<T,Graph>(source, g);
+ }
+
+ struct reference
+ {
+ int m_flags;
+ int m_sequence;
+ Vertex m_vertex;
+ Edge m_edge;
+ EdgeWeight m_weight;
+
+ enum
+ {
+ HAVE_SEQUENCE = 1,
+ HAVE_WEIGHT = 2,
+ HAVE_EDGE = 4,
+ };
+
+ inline reference()
+ : m_flags(0), m_sequence(0),
+ m_vertex(graph_traits<Graph>::null_vertex()),
+ m_edge(), m_weight(0)
+ { }
+
+ inline reference(int s, Edge e)
+ : m_flags(HAVE_SEQUENCE | HAVE_EDGE), m_sequence(s),
+ m_vertex(graph_traits<Graph>::null_vertex()),
+ m_edge(e), m_weight(0)
+ { }
+
+ inline reference(int s, Vertex v, const optional<Edge> &e,
+ const optional<EdgeWeight> &w)
+ : m_flags(HAVE_SEQUENCE | (w ? HAVE_WEIGHT : 0) | (e ? HAVE_EDGE : 0)),
+ m_sequence(s), m_vertex(v)
+ {
+ if (w) m_weight= *w;
+ if (e) m_edge= *e;
+ }
+
+ inline reference(int s, Vertex v, Edge e, EdgeWeight w)
+ : m_flags(HAVE_SEQUENCE | HAVE_WEIGHT | HAVE_EDGE),
+ m_sequence(s), m_vertex(v), m_edge(e), m_weight(w)
+ { }
+
+ inline reference(int s, Vertex v, EdgeWeight w)
+ : m_flags(HAVE_SEQUENCE | HAVE_WEIGHT),
+ m_sequence(s), m_vertex(v), m_edge(), m_weight(w)
+ { }
+
+ inline reference(int s, Vertex v)
+ : m_flags(HAVE_SEQUENCE), m_sequence(s), m_vertex(v), m_edge(),
+ m_weight(0)
+ { }
+
+ optional<int> sequence() const
+ {
+ if (m_flags & HAVE_SEQUENCE)
+ {
+ return m_sequence;
+ }
+ return optional<int>();
+ }
+
+ optional<Vertex> vertex() const
+ {
+ if (m_vertex != graph_traits<Graph>::null_vertex())
+ return m_vertex;
+ return optional<Vertex>();
+ }
+
+ optional<Edge> edge() const
+ {
+ if (m_flags & HAVE_EDGE)
+ return m_edge;
+ return optional<Edge>();
+ };
+
+ optional<EdgeWeight> weight() const
+ {
+ if (m_flags & HAVE_WEIGHT)
+ return m_weight;
+ return optional<EdgeWeight>();
+ }
+ };
+}
+
+namespace open_query {
+ class GRAPHCORE_INTERNAL oqgraph_share
+ {
+ 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()
+ { }
+ };
+
+ class GRAPHCORE_INTERNAL oqgraph_cursor
+ {
+ public:
+ oqgraph_share *const share;
+
+ inline oqgraph_cursor(oqgraph_share *arg)
+ : share(arg)
+ { }
+ virtual ~oqgraph_cursor()
+ { }
+
+ virtual int fetch_row(const row &, row&) = 0;
+ virtual int fetch_row(const row &, row&, const reference&) = 0;
+ virtual void current(reference& ref) const = 0;
+ };
+}
+
+namespace open_query {
+ class GRAPHCORE_INTERNAL stack_cursor : public oqgraph_cursor
+ {
+ private:
+ optional<EdgeWeight> no_weight;
+ public:
+ int sequence;
+ std::stack<reference> results;
+ reference last;
+
+ inline stack_cursor(oqgraph_share *arg)
+ : oqgraph_cursor(arg), no_weight(), sequence(0), results(), last()
+ { }
+
+ int fetch_row(const row &, row&);
+ int fetch_row(const row &, row&, const reference&);
+
+ void current(reference& ref) const
+ {
+ ref= last;
+ }
+ };
+
+ class GRAPHCORE_INTERNAL vertices_cursor : public oqgraph_cursor
+ {
+ typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
+
+ size_t position;
+ reference last;
+ public:
+ inline vertices_cursor(oqgraph_share *arg)
+ : oqgraph_cursor(arg), position(0)
+ { }
+
+ int fetch_row(const row &, row&);
+ int fetch_row(const row &, row&, const reference&);
+
+ void current(reference& ref) const
+ {
+ ref= last;
+ }
+
+ };
+
+ class GRAPHCORE_INTERNAL edges_cursor : public oqgraph_cursor
+ {
+ typedef graph_traits<Graph>::edge_iterator edge_iterator;
+ typedef edge_iterator::difference_type edge_difference;
+
+ edge_difference position;
+ reference last;
+ public:
+ inline edges_cursor(oqgraph_share *arg)
+ : oqgraph_cursor(arg), position(0), last()
+ { }
+
+ int fetch_row(const row &, row&);
+ int fetch_row(const row &, row&, const reference&);
+
+ void current(reference& ref) const
+ {
+ ref= last;
+ }
+ };
+
+ struct GRAPHCORE_INTERNAL oqgraph_visit_dist
+ : public base_visitor<oqgraph_visit_dist>
+ {
+ typedef on_finish_vertex event_filter;
+
+ oqgraph_visit_dist(std::vector<Vertex>::iterator p,
+ std::vector<EdgeWeight>::iterator d,
+ stack_cursor *cursor)
+ : seq(0), m_cursor(*cursor), m_p(p), m_d(d)
+ { assert(cursor); }
+
+ template<class T, class Graph>
+ void operator()(T u, Graph &g)
+ {
+ m_cursor.results.push(reference(++seq, u, m_d[GRAPH_INDEXMAP(g)[u]]));
+ }
+ private:
+ int seq;
+ stack_cursor &m_cursor;
+ std::vector<Vertex>::iterator m_p;
+ std::vector<EdgeWeight>::iterator m_d;
+ };
+
+ template<bool record_weight, typename goal_filter>
+ struct GRAPHCORE_INTERNAL oqgraph_goal
+ : public base_visitor<oqgraph_goal<record_weight,goal_filter> >
+ {
+ typedef goal_filter event_filter;
+
+ oqgraph_goal(Vertex goal, std::vector<Vertex>::iterator p,
+ stack_cursor *cursor)
+ : m_goal(goal), m_cursor(*cursor), m_p(p)
+ { assert(cursor); }
+
+ template<class T, class Graph>
+ void operator()(T u, Graph &g)
+ {
+ 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)
+ break;
+
+ for (Vertex v= u;; u= v)
+ {
+ optional<Edge> edge;
+ optional<EdgeWeight> weight;
+ v= m_p[ indexmap[u] ];
+ if (record_weight && u != v)
+ {
+ typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
+ for (tie(ei, ei_end)= out_edges(v, g); ei != ei_end; ++ei)
+ {
+ if (target(*ei, g) == u)
+ {
+ edge= *ei;
+ weight= GRAPH_WEIGHTMAP(g)[*ei];
+ break;
+ }
+ }
+ }
+ else if (u != v)
+ weight= 1;
+ m_cursor.results.push(reference(seq--, u, edge, weight));
+ if (u == v)
+ break;
+ }
+ throw this;
+ }
+ }
+
+ private:
+ Vertex m_goal;
+ stack_cursor &m_cursor;
+ std::vector<Vertex>::iterator m_p;
+ };
+}
+
+namespace open_query
+{
+ inline oqgraph::oqgraph(oqgraph_share *arg) throw()
+ : share(arg), cursor(0)
+ { }
+
+ inline oqgraph::~oqgraph() throw()
+ {
+ delete cursor;
+ }
+
+ unsigned oqgraph::edges_count() const throw()
+ {
+ return num_edges(share->g);
+ }
+
+ unsigned oqgraph::vertices_count() const throw()
+ {
+ return num_vertices(share->g);
+ }
+
+ oqgraph* oqgraph::create(oqgraph_share *share) throw()
+ {
+ assert(share != NULL);
+ return new (std::nothrow) oqgraph(share);
+ }
+
+ oqgraph_share* oqgraph::create() throw()
+ {
+ return new (std::nothrow) oqgraph_share();
+ }
+
+ optional<Edge>
+ oqgraph_share::find_edge(Vertex orig, Vertex dest) const
+ {
+ if (in_degree(dest, g) >= out_degree(orig, g))
+ {
+ 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)
+ 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)
+ return *ei;
+ }
+ return optional<Edge>();
+ }
+
+ optional<Vertex>
+ oqgraph_share::find_vertex(VertexID id) const
+ {
+ return boost::graph::find_vertex(id, g);
+ }
+
+ int oqgraph::delete_all() throw()
+ {
+ share->g.clear();
+ return 0;
+ }
+
+ int oqgraph::insert_edge(
+ VertexID orig_id, VertexID dest_id, EdgeWeight weight, bool replace) throw()
+ {
+ optional<Vertex> orig, dest;
+ optional<Edge> edge;
+ bool inserted= 0;
+
+ if (weight < 0)
+ return INVALID_WEIGHT;
+ if (!(orig= share->find_vertex(orig_id)))
+ {
+ try
+ {
+ orig= add_vertex(VertexInfo(orig_id), share->g);
+ if (orig == graph_traits<Graph>::null_vertex())
+ return CANNOT_ADD_VERTEX;
+ }
+ catch (...)
+ {
+ return CANNOT_ADD_VERTEX;
+ }
+ }
+ if (!(dest= share->find_vertex(dest_id)))
+ {
+ try
+ {
+ dest= add_vertex(VertexInfo(dest_id), share->g);
+ if (dest == graph_traits<Graph>::null_vertex())
+ return CANNOT_ADD_VERTEX;
+ }
+ catch (...)
+ {
+ return CANNOT_ADD_VERTEX;
+ }
+ }
+ if (!(edge= share->find_edge(*orig, *dest)))
+ {
+ try
+ {
+ tie(edge, inserted)= add_edge(*orig, *dest, share->g);
+ if (!inserted)
+ return CANNOT_ADD_EDGE;
+ }
+ catch (...)
+ {
+ return CANNOT_ADD_EDGE;
+ }
+ }
+ else
+ {
+ if (!replace)
+ return DUPLICATE_EDGE;
+ }
+ share->weightmap[*edge]= weight;
+ return OK;
+ }
+
+ int oqgraph::delete_edge(current_row_st) throw()
+ {
+ reference ref;
+ if (cursor)
+ return EDGE_NOT_FOUND;
+ cursor->current(ref);
+ optional<Edge> edge;
+ if (!(edge= ref.edge()))
+ return EDGE_NOT_FOUND;
+ Vertex orig= source(*edge, share->g);
+ Vertex dest= target(*edge, share->g);
+ remove_edge(*edge, share->g);
+ if (!degree(orig, share->g))
+ remove_vertex(orig, share->g);
+ if (!degree(dest, share->g))
+ remove_vertex(dest, share->g);
+ return OK;
+ }
+
+ int oqgraph::modify_edge(current_row_st,
+ VertexID *orig_id, VertexID *dest_id, EdgeWeight *weight,
+ bool replace) throw()
+ {
+ if (!cursor)
+ return EDGE_NOT_FOUND;
+ reference ref;
+ cursor->current(ref);
+ optional<Edge> edge;
+ if (!(edge= ref.edge()))
+ return EDGE_NOT_FOUND;
+ if (weight && *weight < 0)
+ return INVALID_WEIGHT;
+
+ 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;
+ if (orig_neq || dest_neq)
+ {
+ optional<Edge> new_edge;
+ if (orig_neq && !(orig= share->find_vertex(*orig_id)))
+ {
+ try
+ {
+ orig= add_vertex(VertexInfo(*orig_id), share->g);
+ if (orig == graph_traits<Graph>::null_vertex())
+ return CANNOT_ADD_VERTEX;
+ }
+ catch (...)
+ {
+ return CANNOT_ADD_VERTEX;
+ }
+ }
+ if (dest_neq && !(dest= share->find_vertex(*dest_id)))
+ {
+ try
+ {
+ dest= add_vertex(VertexInfo(*dest_id), share->g);
+ if (dest == graph_traits<Graph>::null_vertex())
+ return CANNOT_ADD_VERTEX;
+ }
+ catch (...)
+ {
+ return CANNOT_ADD_VERTEX;
+ }
+ }
+ if (!(new_edge= share->find_edge(*orig, *dest)))
+ {
+ try
+ {
+ bool inserted;
+ tie(new_edge, inserted)= add_edge(*orig, *dest, share->g);
+ if (!inserted)
+ return CANNOT_ADD_EDGE;
+ }
+ catch (...)
+ {
+ return CANNOT_ADD_EDGE;
+ }
+ }
+ else
+ {
+ if (!replace)
+ return DUPLICATE_EDGE;
+ }
+ share->weightmap[*new_edge]= share->weightmap[*edge];
+ remove_edge(*edge, share->g);
+ edge= new_edge;
+ }
+ if (weight)
+ share->weightmap[*edge]= *weight;
+ return OK;
+ }
+
+ int oqgraph::modify_edge(
+ VertexID orig_id, VertexID dest_id, EdgeWeight weight) throw()
+ {
+ optional<Vertex> orig, dest;
+ optional<Edge> edge;
+
+ if (weight < 0)
+ return INVALID_WEIGHT;
+ if (!(orig= share->find_vertex(orig_id)))
+ return EDGE_NOT_FOUND;
+ if (!(dest= share->find_vertex(dest_id)))
+ return EDGE_NOT_FOUND;
+ if (!(edge= share->find_edge(*orig, *dest)))
+ return EDGE_NOT_FOUND;
+ share->weightmap[*edge]= weight;
+ return OK;
+ }
+
+
+ int oqgraph::delete_edge(VertexID orig_id, VertexID dest_id) throw()
+ {
+ optional<Vertex> orig, dest;
+ optional<Edge> edge;
+
+ if (!(orig= share->find_vertex(orig_id)))
+ return EDGE_NOT_FOUND;
+ if (!(dest= share->find_vertex(dest_id)))
+ return EDGE_NOT_FOUND;
+ if (!(edge= share->find_edge(*orig, *dest)))
+ return EDGE_NOT_FOUND;
+ remove_edge(*edge, share->g);
+ if (!degree(*orig, share->g))
+ remove_vertex(*orig, share->g);
+ if (!degree(*dest, share->g))
+ remove_vertex(*dest, share->g);
+ return OK;
+ }
+
+
+ int oqgraph::search(int *latch, VertexID *orig_id, VertexID *dest_id) throw()
+ {
+ optional<Vertex> orig, dest;
+ int op= 0, seq= 0;
+ enum {
+ NO_SEARCH = 0,
+ DIJKSTRAS = 1,
+ BREADTH_FIRST = 2,
+
+ ALGORITHM = 0x0ffff,
+ HAVE_ORIG = 0x10000,
+ HAVE_DEST = 0x20000,
+ };
+
+ delete cursor; cursor= 0;
+ row_info= empty_row;
+ if ((row_info.latch_indicator= latch))
+ op= ALGORITHM & (row_info.latch= *latch);
+ if ((row_info.orig_indicator= orig_id) && (op|= HAVE_ORIG))
+ orig= share->find_vertex((row_info.orig= *orig_id));
+ if ((row_info.dest_indicator= dest_id) && (op|= HAVE_DEST))
+ dest= share->find_vertex((row_info.dest= *dest_id));
+ //try
+ //{
+ switch (op)
+ {
+ case NO_SEARCH | HAVE_ORIG | HAVE_DEST:
+ case NO_SEARCH | HAVE_ORIG:
+ if ((cursor= new (std::nothrow) stack_cursor(share)) && orig)
+ {
+ graph_traits<Graph>::out_edge_iterator ei, ei_end;
+ for (tie(ei, ei_end)= out_edges(*orig, share->g); ei != ei_end; ++ei)
+ {
+ Vertex v= target(*ei, share->g);
+ static_cast<stack_cursor*>(cursor)->
+ results.push(reference(++seq, v, *ei, share->weightmap[*ei]));
+ }
+ }
+ /* fall through */
+ case NO_SEARCH | HAVE_DEST:
+ if ((op & HAVE_DEST) &&
+ (cursor || (cursor= new (std::nothrow) stack_cursor(share))) &&
+ dest)
+ {
+ graph_traits<Graph>::in_edge_iterator ei, ei_end;
+ for (tie(ei, ei_end)= in_edges(*dest, share->g); ei != ei_end; ++ei)
+ {
+ Vertex v= source(*ei, share->g);
+ static_cast<stack_cursor*>(cursor)->
+ results.push(reference(++seq, v, *ei, share->weightmap[*ei]));
+ }
+ }
+ break;
+
+ case NO_SEARCH:
+ cursor= new (std::nothrow) vertices_cursor(share);
+ break;
+
+ 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;
+ 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)
+ )
+ );
+ }
+ catch (...)
+ { /* printf("found\n"); */ }
+ }
+ break;
+
+ 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;
+ try
+ {
+ breadth_first_search(share->g, *orig,
+ visitor(make_bfs_visitor(
+ std::make_pair(
+ record_predecessors(
+ make_iterator_property_map(p.begin(), share->indexmap),
+ on_tree_edge()
+ ),
+ vis)
+ )
+ )
+ );
+ }
+ catch (...)
+ { /* printf("found\n"); */ }
+ }
+ break;
+
+ case DIJKSTRAS | HAVE_ORIG:
+ 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;
+ 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;
+ case BREADTH_FIRST:
+ breadth_first_search(share->g, *orig,
+ visitor(make_bfs_visitor(
+ std::make_pair(
+ record_predecessors(
+ make_iterator_property_map(p.begin(),
+ share->indexmap),
+ on_tree_edge()
+ ),
+ std::make_pair(
+ record_distances(
+ make_iterator_property_map(d.begin(),
+ share->indexmap),
+ on_tree_edge()
+ ),
+ vis
+ ))
+ ))
+ );
+ break;
+ default:
+ abort();
+ }
+ }
+ break;
+
+ 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));
+ reverse_graph<Graph> r(share->g);
+ p[share->indexmap[*dest]]= *dest;
+ 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)
+ )
+ );
+ break;
+ case BREADTH_FIRST:
+ breadth_first_search(r, *dest,
+ visitor(make_bfs_visitor(
+ std::make_pair(
+ record_predecessors(
+ make_iterator_property_map(p.begin(),
+ share->indexmap),
+ on_tree_edge()
+ ),
+ std::make_pair(
+ record_distances(
+ make_iterator_property_map(d.begin(),
+ share->indexmap),
+ on_tree_edge()
+ ),
+ vis
+ ))
+ ))
+ );
+ break;
+ default:
+ abort();
+ }
+ }
+ break;
+
+ default:
+ break;
+ }
+ return 0;
+ //}
+ //catch (...)
+ //{
+ // return MISC_FAIL;
+ //}
+ }
+
+ int oqgraph::fetch_row(row& result) throw()
+ {
+ if (!cursor)
+ return NO_MORE_DATA;
+ return cursor->fetch_row(row_info, result);
+ }
+
+ int oqgraph::fetch_row(row& result, const void* ref_ptr) throw()
+ {
+ const reference &ref= *(const reference*) ref_ptr;
+ if (!cursor)
+ return NO_MORE_DATA;
+ return cursor->fetch_row(row_info, result, ref);
+ }
+
+ void oqgraph::row_ref(void *ref_ptr) throw()
+ {
+ reference &ref= *(reference*) ref_ptr;
+ if (cursor)
+ cursor->current(ref);
+ else
+ ref= reference();
+ }
+
+ int oqgraph::random(bool scan) throw()
+ {
+ if (scan || !cursor)
+ {
+ delete cursor; cursor= 0;
+ if (!(cursor= new (std::nothrow) edges_cursor(share)))
+ return MISC_FAIL;
+ }
+ row_info= empty_row;
+ return OK;
+ }
+
+ void oqgraph::free(oqgraph *graph) throw()
+ {
+ delete graph;
+ }
+
+ void oqgraph::free(oqgraph_share *graph) throw()
+ {
+ delete graph;
+ }
+
+ const size_t oqgraph::sizeof_ref= sizeof(reference);
+}
+
+int stack_cursor::fetch_row(const row &row_info, row &result)
+{
+ if (!results.empty())
+ {
+ if (int res= fetch_row(row_info, result, results.top()))
+ return res;
+ results.pop();
+ return oqgraph::OK;
+ }
+ else
+ {
+ last= reference();
+ return oqgraph::NO_MORE_DATA;
+ }
+}
+
+int stack_cursor::fetch_row(const row &row_info, row &result,
+ const reference &ref)
+{
+ last= ref;
+ if (optional<Vertex> v= last.vertex())
+ {
+ optional<int> seq;
+ optional<EdgeWeight> w;
+ optional<Vertex> v;
+ result= row_info;
+ if ((result.seq_indicator= seq= last.sequence()))
+ result.seq= *seq;
+ if ((result.link_indicator= v= last.vertex()))
+ result.link= share->idmap[*v];
+ if ((result.weight_indicator= w= last.weight()))
+ result.weight= *w;
+ return oqgraph::OK;
+ }
+ else
+ return oqgraph::NO_MORE_DATA;
+}
+
+
+int vertices_cursor::fetch_row(const row &row_info, row &result)
+{
+ vertex_iterator it, end;
+ reference ref;
+ size_t count= position;
+ for (tie(it, end)= vertices(share->g); count && it != end; ++it, --count);
+ if (it != end)
+ ref= reference(position+1, *it);
+ if (int res= fetch_row(row_info, result, ref))
+ return res;
+ position++;
+ return oqgraph::OK;
+}
+
+int vertices_cursor::fetch_row(const row &row_info, row &result,
+ const reference &ref)
+{
+ last= ref;
+ optional<Vertex> v= last.vertex();
+ result= row_info;
+ if (v)
+ {
+ result.link_indicator= 1;
+ result.link= share->idmap[*v];
+#ifdef DISPLAY_VERTEX_INFO
+ result.seq_indicator= 1;
+ if ((result.seq= degree(*v, share->g)))
+ {
+ 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];
+ 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];
+ result.weight_indicator= 1;
+ result.weight= weight / result.seq;
+ }
+#endif
+ return oqgraph::OK;
+ }
+ else
+ return oqgraph::NO_MORE_DATA;
+}
+
+int edges_cursor::fetch_row(const row &row_info, row &result)
+{
+ edge_iterator it, end;
+ reference ref;
+ size_t count= position;
+ for (tie(it, end)= edges(share->g); count && it != end; ++it, --count);
+ if (it != end)
+ ref= reference(position+1, *it);
+ if (int res= fetch_row(row_info, result, ref))
+ return res;
+ ++position;
+ return oqgraph::OK;
+}
+
+int edges_cursor::fetch_row(const row &row_info, row &result,
+ const reference &ref)
+{
+ optional<Edge> edge;
+ if ((edge= (last= ref).edge()))
+ {
+ 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 ];
+ return oqgraph::OK;
+ }
+ return oqgraph::NO_MORE_DATA;
+}
+
+namespace boost {
+ GRAPHCORE_INTERNAL void throw_exception(std::exception const&)
+ {
+ abort();
+ }
+}
diff --git a/storage/oqgraph/graphcore.h b/storage/oqgraph/graphcore.h
new file mode 100644
index 00000000000..4aaddb2796f
--- /dev/null
+++ b/storage/oqgraph/graphcore.h
@@ -0,0 +1,116 @@
+/* Copyright (C) 2007-2009 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.II 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
+ ======================================================================
+*/
+
+#ifndef oq_graphcore_h_
+#define oq_graphcore_h_
+
+/* #define GRAPHCORE_INTERNAL __attribute__((visibility("hidden"))) */
+#define GRAPHCORE_INTERNAL
+
+#include "graphcore-types.h"
+
+namespace open_query
+{
+ class oqgraph_share;
+ class oqgraph_cursor;
+
+ struct row
+ {
+ bool latch_indicator;
+ bool orig_indicator;
+ bool dest_indicator;
+ bool weight_indicator;
+ bool seq_indicator;
+ bool link_indicator;
+
+ int latch;
+ VertexID orig;
+ VertexID dest;
+ EdgeWeight weight;
+ unsigned seq;
+ VertexID link;
+ };
+
+ class oqgraph
+ {
+ oqgraph_share *const share;
+ oqgraph_cursor *cursor;
+ row row_info;
+
+ inline oqgraph(oqgraph_share*) throw();
+ inline ~oqgraph() throw();
+ public:
+
+ enum error_code
+ {
+ OK= 0,
+ NO_MORE_DATA,
+ EDGE_NOT_FOUND,
+ INVALID_WEIGHT,
+ DUPLICATE_EDGE,
+ CANNOT_ADD_VERTEX,
+ CANNOT_ADD_EDGE,
+ MISC_FAIL
+ };
+
+ struct current_row_st {};
+ static inline current_row_st current_row()
+ { return current_row_st(); }
+
+ unsigned vertices_count() const throw();
+ unsigned edges_count() const throw();
+
+ int delete_all(void) throw();
+
+ int insert_edge(VertexID, VertexID, EdgeWeight, bool=0) throw();
+ int modify_edge(VertexID, VertexID, EdgeWeight) throw();
+ int delete_edge(VertexID, VertexID) throw();
+
+ int modify_edge(current_row_st,
+ VertexID*, VertexID*, EdgeWeight*, bool=0) throw();
+ int delete_edge(current_row_st) throw();
+
+ int replace_edge(VertexID orig, VertexID dest, EdgeWeight weight) throw()
+ { return insert_edge(orig, dest, weight, true); }
+
+ int search(int*, VertexID*, VertexID*) throw();
+ int random(bool) throw();
+
+ int fetch_row(row&) throw();
+ int fetch_row(row&, const void*) throw();
+ void row_ref(void*) throw();
+
+ static oqgraph* create(oqgraph_share*) throw();
+ static oqgraph_share *create() throw();
+
+ static void free(oqgraph*) throw();
+ static void free(oqgraph_share*) throw();
+
+ static const size_t sizeof_ref;
+ };
+
+}
+#endif
diff --git a/storage/oqgraph/graphstore.c b/storage/oqgraph/graphstore.c
new file mode 100644
index 00000000000..c5478b56ca5
--- /dev/null
+++ b/storage/oqgraph/graphstore.c
@@ -0,0 +1,356 @@
+/*
+ * Graph Engine - Copyright (C) 2007 by Arjen Lentz (arjen@openquery.com.au)
+ * graphstore.c internal storage system
+ */
+#include <stdlib.h>
+#include <string.h>
+#include <my_global.h>
+#include <my_sys.h>
+#include "graphstore.h"
+
+
+/*
+ create a new vertex, and add it to the list (or start a list)
+ NOTE! gspp is ptr to base ptr
+
+ returns 1 for ok, 0 for error
+*/
+static int _add_vertex (GRAPHSTORE **gspp, GRAPH_VERTEXID id)
+{
+ GRAPHSTORE *newgsp;
+ GRAPHSTORE *gscurp;
+
+ if (gspp == NULL)
+ return 0;
+
+ /* not allowing 0 */
+ if (!id)
+ return 0;
+
+ if (*gspp != NULL) {
+ for (gscurp = *gspp; gscurp != NULL; gscurp = gscurp->next) {
+ if (gscurp->vertex->id == id)
+ return 1; /* we can ignore, id already exists */
+ }
+ }
+
+ /* allocate and initialise */
+ if ((newgsp = my_malloc(sizeof (GRAPHSTORE),MYF(MY_ZEROFILL))) == NULL)
+ return 0;
+
+ if ((newgsp->vertex = my_malloc(sizeof (GRAPH_VERTEX),MYF(MY_ZEROFILL))) == NULL) {
+ my_free(newgsp,MYF(0));
+ return 0;
+ }
+
+ newgsp->vertex->id = id;
+ /* add new vertex to end of list */
+ if (*gspp != NULL) {
+ for (gscurp = *gspp; gscurp->next != NULL; gscurp = gscurp->next);
+ gscurp->next = newgsp;
+ }
+ else /* new list */
+ *gspp = newgsp;
+
+ /* ok */
+ return 1;
+}
+
+
+/*
+ find a vertex by id
+
+ returns ptr or NULL
+*/
+static GRAPH_VERTEX *_find_vertex (GRAPHSTORE *gsp, GRAPH_VERTEXID id)
+{
+ /* just loop through the list to find id */
+ while (gsp != NULL && gsp->vertex->id != id)
+ gsp = gsp->next;
+
+ /* return ptr to vertex, or NULL */
+ return (gsp != NULL ? gsp->vertex : NULL);
+}
+
+
+/*
+ add edge
+ both vertices must already exist; graphstore_insert() does this
+
+ return 1 for ok, 0 for error (already exists, alloc error, etc)
+*/
+static int _add_edge (GRAPHSTORE *gsp, GRAPH_VERTEXID origid, GRAPH_VERTEXID destid, GRAPH_WEIGHT weight)
+{
+ GRAPH_VERTEX *origvp, *destvp;
+ GRAPH_EDGE *ep, *newep;
+
+ /* find both vertices */
+ if ((origvp = _find_vertex(gsp,origid)) == NULL ||
+ (destvp = _find_vertex(gsp,destid)) == NULL)
+ return 0;
+
+ /* check if edge already exists */
+ for (ep = origvp->forward_edge; ep != NULL; ep = ep->next_edge) {
+ if (ep->vertex->id == destid)
+ return 0;
+ }
+
+ /* allocate and initialise new edge */
+ if ((newep = my_malloc(sizeof (GRAPH_EDGE),MYF(MY_ZEROFILL))) == NULL)
+ return 0;
+
+ newep->vertex = destvp;
+ newep->weight = weight;
+
+ /* insert new edge at start of chain, that's easiest */
+ ep = origvp->forward_edge;
+ origvp->forward_edge = newep;
+ newep->next_edge = ep;
+
+ /* ok */
+ return 1;
+}
+
+
+/*
+ create a new row, and add it to the graph set (or start set)
+ NOTE! gsetpp is ptr to base ptr
+
+ returns 1 for ok, 0 for error
+*/
+static int _add_graph_set (GRAPH_SET **gsetpp, GRAPH_TUPLE *gtp)
+{
+ GRAPH_SET *newgsetp;
+ GRAPH_SET *gsetcurp;
+
+ if (gsetpp == NULL || gtp == NULL)
+ return 0;
+
+ /* allocate and initialise */
+ if ((newgsetp = my_malloc(sizeof (GRAPH_SET),MYF(MY_ZEROFILL))) == NULL)
+ return 0;
+
+ /* put in the data */
+ memcpy(&newgsetp->tuple,gtp,sizeof (GRAPH_TUPLE));
+
+ /* add new row to end of set */
+ if (*gsetpp != NULL) {
+ for (gsetcurp = *gsetpp; gsetcurp->next != NULL; gsetcurp = gsetcurp->next);
+ gsetcurp->next = newgsetp;
+ }
+ else { /* new set */
+ *gsetpp = newgsetp;
+ }
+
+ /* ok */
+ return 1;
+}
+
+
+/*
+ free a graph set (release memory)
+
+ returns 1 for ok, 0 for error
+*/
+int free_graph_set (GRAPH_SET *gsetp)
+{
+ GRAPH_SET *nextgsetp;
+
+ if (gsetp == NULL)
+ return 0;
+
+ while (gsetp != NULL) {
+ nextgsetp = gsetp->next;
+ /* free() is a void function, nothing to check */
+ my_free(gsetp,MYF(0));
+ gsetp = nextgsetp;
+ }
+
+ /* ok */
+ return 1;
+}
+
+
+/*
+ insert new data into graphstore
+ this can be either a vertex or an edge, depending on the params
+ NOTE! gspp is ptr to base ptr
+
+ returns 1 for ok, 0 for error
+*/
+int graphstore_insert (GRAPHSTORE **gspp, GRAPH_TUPLE *gtp)
+{
+ if (gspp == NULL)
+ return 0;
+
+ /* if nada or no orig vertex, we can't do anything */
+ if (gtp == NULL || !gtp->origid)
+ return 0;
+
+#if 0
+printf("inserting: origid=%lu destid=%lu weight=%lu\n",gtp->origid,gtp->destid,gtp->weight);
+#endif
+
+ if (!gtp->destid) /* no edge param so just adding vertex */
+ return _add_vertex(gspp,gtp->origid);
+
+ /*
+ add an edge
+ first add both vertices just in case they didn't yet exist...
+ not checking result there: if there's a prob, _add_edge() will catch.
+ */
+ _add_vertex(gspp,gtp->origid);
+ _add_vertex(gspp,gtp->destid);
+ return _add_edge(*gspp,gtp->origid,gtp->destid,gtp->weight);
+}
+
+
+/*
+ this is an internal function used by graphstore_query()
+
+ find any path from originating vertex to destid
+ if found, add to the result set on the way back
+ NOTE: recursive function!
+
+ returns 1 for hit, 0 for nothing, -1 for error
+*/
+int _find_any_path(GRAPH_SET **gsetpp, GRAPH_VERTEXID origid, GRAPH_VERTEXID destid, GRAPH_VERTEX *gvp, GRAPH_SEQ depth)
+{
+ GRAPH_EDGE *gep;
+ GRAPH_TUPLE tup;
+ int res;
+
+ if (gvp->id == destid) {
+ /* found target! */
+ bzero(&tup,sizeof (GRAPH_TUPLE));
+ tup.origid = origid;
+ tup.destid = destid;
+ tup.seq = depth;
+ tup.linkid = gvp->id;
+ return (_add_graph_set(gsetpp,&tup) ? 1 : -1);
+ }
+
+ /* walk through all edges for this vertex */
+ for (gep = gvp->forward_edge; gep; gep = gep->next_edge) {
+ /* recurse */
+ res = _find_any_path(gsetpp,origid,destid,gep->vertex,depth+1);
+ if (res < 0)
+ return res;
+ if (res > 0) {
+ /* found somewhere below this one, insert ourselves and return */
+ bzero(&tup,sizeof (GRAPH_TUPLE));
+ tup.origid = origid;
+ tup.destid = destid;
+ tup.weight = gep->weight;
+ tup.seq = depth;
+ tup.linkid = gvp->id;
+ return (_add_graph_set(gsetpp,&tup) ? 1 : -1);
+ }
+ }
+
+ /* nothing found but no error */
+ return 0;
+}
+
+
+/*
+ query graphstore
+ latch specifies what operation to perform
+
+ we need to feed the conditions in... (through engine condition pushdown)
+ for now we just presume one condition per field so we just feed in a tuple
+ this also means we can just find constants, not ranges
+
+ return ptr to GRAPH_SET
+ caller must free with free_graph_set()
+*/
+GRAPH_SET *graphstore_query (GRAPHSTORE *gsp, GRAPH_TUPLE *gtp)
+{
+ GRAPH_SET *gsetp = NULL;
+ GRAPH_SET *gsetcurp;
+ GRAPH_SET *newgsetp;
+
+ if (gsp == NULL || gtp == NULL)
+ return (NULL);
+
+ switch (gtp->latch) {
+ case 0: /* return all vertices/edges */
+ {
+ GRAPHSTORE *gscurp;
+ GRAPH_EDGE *gep;
+ GRAPH_TUPLE tup;
+
+ /* walk through all vertices */
+ for (gscurp = gsp; gscurp != NULL; gscurp = gscurp->next) {
+ /* check for condition */
+ if (gtp->origid && gscurp->vertex->id != gtp->origid)
+ continue;
+
+ bzero(&tup,sizeof (GRAPH_TUPLE));
+ tup.origid = gscurp->vertex->id;
+
+ /* no edges? */
+ if (gscurp->vertex->forward_edge == NULL) {
+ /* just add vertex to set */
+ if (!_add_graph_set(&gsetp,&tup)) {
+ if (gsetp != NULL) /* clean up */
+ my_free(gsetp,MYF(0));
+ return (NULL);
+ }
+ }
+ else {
+ /* walk through all edges */
+ for (gep = gscurp->vertex->forward_edge; gep; gep = gep->next_edge) {
+ tup.destid = gep->vertex->id;
+ tup.weight = gep->weight;
+
+ /* just add vertex to set */
+ if (!_add_graph_set(&gsetp,&tup)) {
+ if (gsetp != NULL) /* clean up */
+ my_free(gsetp,MYF(0));
+ return (NULL);
+ }
+ }
+ }
+ }
+ }
+ break;
+
+ case 1: /* find a path between origid and destid */
+ /* yes it'll just go with the first path it finds! */
+ {
+ GRAPHSTORE *gscurp;
+ GRAPH_VERTEX *origvp;
+ GRAPH_TUPLE tup;
+
+ if (!gtp->origid || !gtp->destid)
+ return NULL;
+
+ /* find both vertices */
+ if ((origvp = _find_vertex(gsp,gtp->origid)) == NULL ||
+ _find_vertex(gsp,gtp->destid) == NULL)
+ return NULL;
+
+ if (_find_any_path(&gsetp,gtp->origid,gtp->destid,origvp,0) < 0) { /* error? */
+ if (gsetp != NULL) /* clean up */
+ my_free(gsetp,MYF(0));
+ return NULL;
+ }
+ }
+ break;
+
+ default:
+ /* this ends up being an empty set */
+ break;
+ }
+
+ /* Fix up latch column with the proper value - to be relationally correct */
+ for (gsetcurp = gsetp; gsetcurp != NULL; gsetcurp = gsetcurp->next)
+ gsetcurp->tuple.latch = gtp->latch;
+
+ return gsetp;
+}
+
+
+
+/* end of graphstore.c */ \ No newline at end of file
diff --git a/storage/oqgraph/graphstore.h b/storage/oqgraph/graphstore.h
new file mode 100644
index 00000000000..61862221455
--- /dev/null
+++ b/storage/oqgraph/graphstore.h
@@ -0,0 +1,90 @@
+/*
+ * Graph Engine - Copyright (C) 2007 by Arjen Lentz (arjen@openquery.com.au)
+ * graphstore.h internal storage system
+ */
+//typedef unsigned short uint16;
+//typedef unsigned long long uint64;
+
+
+/*
+ This is essentially what a GRAPH engine table looks like on the MySQL end:
+ CREATE TABLE foo (
+ latch SMALLINT UNSIGNED NULL,
+ origid BIGINT UNSIGNED NULL,
+ destid BIGINT UNSIGNED NULL,
+ weight BIGINT UNSIGNED NULL,
+ seq BIGINT UNSIGNED NULL,
+ linkid BIGINT UNSIGNED NULL
+ ) ENGINE=OQGRAPH
+*/
+
+
+/*
+ We represent the above in C in the following way:
+*/
+typedef uint16 GRAPH_LATCH;
+typedef uint64 GRAPH_VERTEXID;
+typedef uint64 GRAPH_WEIGHT;
+typedef uint64 GRAPH_SEQ;
+
+typedef struct graph_tuple {
+ GRAPH_LATCH latch; /* function */
+ GRAPH_VERTEXID origid; /* vertex (should be != 0) */
+ GRAPH_VERTEXID destid; /* edge */
+ GRAPH_WEIGHT weight; /* weight */
+ GRAPH_SEQ seq; /* seq# within (origid) */
+ GRAPH_VERTEXID linkid; /* current step between origid/destid */
+} GRAPH_TUPLE;
+
+typedef struct graph_set {
+ GRAPH_TUPLE tuple;
+ struct graph_set *next;
+} GRAPH_SET;
+
+
+/*
+ Internally, sets look nothing like the above
+
+ - We have vertices, connected by edges.
+ - Each vertex' edges are maintained in a linked list.
+ - Edges can be weighted.
+
+ There are some issues with this structure, it'd be a pest to do a delete
+ So for now, let's just not support deletes!
+*/
+/* the below is half-gross and will likely change */
+typedef struct graph_edge {
+ struct graph_vertex {
+ GRAPH_VERTEXID id;
+ struct graph_edge *forward_edge;
+ } *vertex;
+ GRAPH_WEIGHT weight;
+ struct graph_edge *next_edge;
+} GRAPH_EDGE;
+
+typedef struct graph_vertex GRAPH_VERTEX;
+
+
+/*
+ A rough internal storage system for a set
+*/
+/* this below is fully gross and will definitely change */
+typedef struct graphstore {
+ GRAPH_VERTEX *vertex; /* changed to ptr when integrating into MySQL */
+ struct graphstore *next;
+} GRAPHSTORE;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* public function declarations */
+int graphstore_insert (GRAPHSTORE **gspp, GRAPH_TUPLE *gtp);
+GRAPH_SET *graphstore_query (GRAPHSTORE *gsp, GRAPH_TUPLE *gtp);
+int free_graph_set (GRAPH_SET *gsetp);
+
+#ifdef __cplusplus
+}
+#endif
+
+/* end of graphstore.h */ \ No newline at end of file
diff --git a/storage/oqgraph/ha_oqgraph.cc b/storage/oqgraph/ha_oqgraph.cc
new file mode 100644
index 00000000000..fb1d029f47e
--- /dev/null
+++ b/storage/oqgraph/ha_oqgraph.cc
@@ -0,0 +1,1040 @@
+/* Copyright (C) 2007-2009 Arjen G Lentz & Antony T Curtis for Open Query
+ Portions of this file copyright (C) 2000-2006 MySQL AB
+
+ 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.
+
+ 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.II 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
+ ======================================================================
+*/
+
+#ifdef USE_PRAGMA_IMPLEMENTATION
+#pragma implementation // gcc: Class implementation
+#endif
+
+#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"
+
+#define OQGRAPH_STATS_UPDATE_THRESHOLD 10
+
+using namespace open_query;
+
+
+struct oqgraph_info_st
+{
+ THR_LOCK lock;
+ oqgraph_share *graph;
+ uint use_count;
+ uint key_stat_version;
+ uint records;
+ bool dropped;
+ char name[FN_REFLEN+1];
+};
+
+static const char oqgraph_description[]=
+ "Open Query Graph Computation Engine, stored in memory "
+ "(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)
+{
+ return new (mem_root) ha_oqgraph(hton, 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_DEFAULT;
+ hton->create= oqgraph_create_handler;
+ hton->flags= HTON_NO_FLAGS;
+#endif
+ 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)
+{
+ switch (res)
+ {
+ case oqgraph::OK:
+ return 0;
+ case oqgraph::NO_MORE_DATA:
+ return HA_ERR_END_OF_FILE;
+ case oqgraph::EDGE_NOT_FOUND:
+ return HA_ERR_KEY_NOT_FOUND;
+ case oqgraph::INVALID_WEIGHT:
+ return HA_ERR_AUTOINC_ERANGE;
+ case oqgraph::DUPLICATE_EDGE:
+ return HA_ERR_FOUND_DUPP_KEY;
+ case oqgraph::CANNOT_ADD_VERTEX:
+ case oqgraph::CANNOT_ADD_EDGE:
+ return HA_ERR_RECORD_FILE_FULL;
+ case oqgraph::MISC_FAIL:
+ default:
+ return HA_ERR_CRASHED_ON_USAGE;
+ }
+}
+
+/**
+ * Check if table complies with our designated structure
+ *
+ * ColName Type Attributes
+ * ======= ======== =============
+ * latch SMALLINT UNSIGNED NULL
+ * origid BIGINT UNSIGNED NULL
+ * destid BIGINT UNSIGNED NULL
+ * weight DOUBLE NULL
+ * seq BIGINT UNSIGNED NULL
+ * linkid BIGINT UNSIGNED NULL
+ * =================================
+ *
+ CREATE TABLE foo (
+ latch SMALLINT UNSIGNED NULL,
+ origid BIGINT UNSIGNED NULL,
+ destid BIGINT UNSIGNED NULL,
+ weight DOUBLE NULL,
+ seq BIGINT UNSIGNED NULL,
+ linkid BIGINT UNSIGNED NULL,
+ KEY (latch, origid, destid) USING HASH,
+ KEY (latch, destid, origid) USING HASH
+ ) ENGINE=OQGRAPH
+
+ */
+static int oqgraph_check_table_structure (TABLE *table_arg)
+{
+ int i;
+ struct { const char *colname; int coltype; } skel[] = {
+ { "latch" , MYSQL_TYPE_SHORT },
+ { "origid", MYSQL_TYPE_LONGLONG },
+ { "destid", MYSQL_TYPE_LONGLONG },
+ { "weight", MYSQL_TYPE_DOUBLE },
+ { "seq" , MYSQL_TYPE_LONGLONG },
+ { "linkid", MYSQL_TYPE_LONGLONG },
+ { NULL , 0}
+ };
+
+ DBUG_ENTER("ha_oqgraph::table_structure_ok");
+
+ Field **field= table_arg->field;
+ for (i= 0; *field && skel[i].colname; i++, field++) {
+ /* Check Column Type */
+ if ((*field)->type() != skel[i].coltype)
+ DBUG_RETURN(-1);
+ if (skel[i].coltype != MYSQL_TYPE_DOUBLE) {
+ /* Check Is UNSIGNED */
+ if (!((*field)->flags & UNSIGNED_FLAG ))
+ DBUG_RETURN(-1);
+ }
+ /* Check THAT NOT NULL isn't set */
+ if ((*field)->flags & NOT_NULL_FLAG)
+ DBUG_RETURN(-1);
+ /* Check the column name */
+ if (strcmp(skel[i].colname,(*field)->field_name))
+ DBUG_RETURN(-1);
+ }
+
+ if (skel[i].colname || *field || !table_arg->key_info || !table_arg->s->keys)
+ DBUG_RETURN(-1);
+
+ KEY *key= table_arg->key_info;
+ for (uint i= 0; i < table_arg->s->keys; ++i, ++key)
+ {
+ Field **field= table_arg->field;
+ /* check that the first key part is the latch and it is a hash key */
+ if (!(field[0] == key->key_part[0].field &&
+ HA_KEY_ALG_HASH == key->algorithm))
+ DBUG_RETURN(-1);
+ if (key->key_parts == 3)
+ {
+ /* KEY (latch, origid, destid) USING HASH */
+ /* KEY (latch, destid, origid) USING HASH */
+ if (!(field[1] == key->key_part[1].field &&
+ field[2] == key->key_part[2].field) &&
+ !(field[1] == key->key_part[2].field &&
+ field[2] == key->key_part[1].field))
+ DBUG_RETURN(-1);
+ }
+ else
+ DBUG_RETURN(-1);
+ }
+
+ DBUG_RETURN(0);
+}
+
+/*****************************************************************************
+** 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)
+{ }
+
+
+static const char *ha_oqgraph_exts[] =
+{
+ NullS
+};
+
+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);
+}
+
+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)
+{
+ pthread_mutex_lock(&LOCK_oqgraph);
+ if ((share = get_share(name, table)))
+ {
+ ref_length= oqgraph::sizeof_ref;
+ }
+
+ if (share)
+ {
+ /* 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;
+ }
+ pthread_mutex_unlock(&LOCK_oqgraph);
+
+ return (share ? 0 : 1);
+}
+
+int ha_oqgraph::close(void)
+{
+ pthread_mutex_lock(&LOCK_oqgraph);
+ oqgraph::free(graph); graph= 0;
+ int res= free_share(share);
+ pthread_mutex_unlock(&LOCK_oqgraph);
+ return error_code(res);
+}
+
+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)
+ {
+ 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;
+}
+
+
+int ha_oqgraph::write_row(byte * buf)
+{
+ int res= oqgraph::MISC_FAIL;
+ Field ** const field= table->field;
+ STATISTIC_INCREMENT(ha_write_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)
+ {
+ field[1]->MOVE(ptrdiff);
+ field[2]->MOVE(ptrdiff);
+ field[3]->MOVE(ptrdiff);
+ }
+
+ 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;
+
+ if (!field[3]->is_null())
+ weight= (EdgeWeight) field[3]->val_real();
+
+ if (!(res= graph->insert_edge(orig_id, dest_id, weight, replace_dups)))
+ {
+ ++records_changed;
+ share->records++;
+ }
+ if (res == oqgraph::DUPLICATE_EDGE && ignore_dups && !insert_dups)
+ res= oqgraph::OK;
+ }
+
+ if (ptrdiff)
+ {
+ field[1]->MOVE(-ptrdiff);
+ field[2]->MOVE(-ptrdiff);
+ field[3]->MOVE(-ptrdiff);
+ }
+#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)
+ {
+ /*
+ 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::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)
+ {
+ field[0]->MOVE(ptrdiff);
+ field[1]->MOVE(ptrdiff);
+ field[2]->MOVE(ptrdiff);
+ field[3]->MOVE(ptrdiff);
+ }
+
+ if (inited == INDEX || inited == RND)
+ {
+ 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 (!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;
+ }
+
+ field[0]->MOVE(-ptrdiff2);
+ field[1]->MOVE(-ptrdiff2);
+ field[2]->MOVE(-ptrdiff2);
+ field[3]->MOVE(-ptrdiff2);
+ }
+
+ if (ptrdiff)
+ {
+ field[0]->MOVE(-ptrdiff);
+ field[1]->MOVE(-ptrdiff);
+ field[2]->MOVE(-ptrdiff);
+ field[3]->MOVE(-ptrdiff);
+ }
+#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)
+ {
+ /*
+ 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::delete_row(const byte * buf)
+{
+ int res= oqgraph::EDGE_NOT_FOUND;
+ Field **field= table->field;
+ STATISTIC_INCREMENT(ha_delete_count);
+
+ if (inited == INDEX || inited == RND)
+ {
+ if ((res= graph->delete_edge(oqgraph::current_row())) == oqgraph::OK)
+ {
+ ++records_changed;
+ share->records--;
+ }
+ }
+ 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);
+ }
+
+ if (field[0]->is_null() && !field[1]->is_null() && !field[2]->is_null())
+ {
+ 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)
+ {
+ ++records_changed;
+ share->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
+ }
+
+ 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::index_read(byte * buf, const byte * key, uint key_len,
+ enum ha_rkey_function find_flag)
+{
+ DBUG_ASSERT(inited==INDEX);
+ return index_read_idx(buf, active_index, key, key_len, find_flag);
+}
+
+int ha_oqgraph::index_next_same(byte *buf, const byte *key, uint key_len)
+{
+ int res;
+ open_query::row row;
+ DBUG_ASSERT(inited==INDEX);
+ STATISTIC_INCREMENT(ha_read_key_count);
+ if (!(res= graph->fetch_row(row)))
+ res= fill_record(buf, row);
+ table->status= res ? STATUS_NOT_FOUND : 0;
+ return error_code(res);
+}
+
+int ha_oqgraph::index_read_idx(byte * buf, uint index, const byte * key,
+ uint key_len, enum ha_rkey_function find_flag)
+{
+ Field **field= table->field;
+ KEY *key_info= table->key_info + index;
+ int res;
+ VertexID orig_id, dest_id;
+ int latch;
+ VertexID *orig_idp=0, *dest_idp=0;
+ int *latchp=0;
+ open_query::row row;
+ STATISTIC_INCREMENT(ha_read_key_count);
+
+ 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)
+ {
+ field[0]->MOVE(ptrdiff);
+ field[1]->MOVE(ptrdiff);
+ field[2]->MOVE(ptrdiff);
+ }
+
+ if (!field[0]->is_null())
+ {
+ latch= (int) field[0]->val_int();
+ latchp= &latch;
+ }
+
+ if (!field[1]->is_null())
+ {
+ orig_id= (VertexID) field[1]->val_int();
+ orig_idp= &orig_id;
+ }
+
+ if (!field[2]->is_null())
+ {
+ dest_id= (VertexID) field[2]->val_int();
+ dest_idp= &dest_id;
+ }
+
+ 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
+
+ res= graph->search(latchp, orig_idp, dest_idp);
+
+ if (!res && !(res= graph->fetch_row(row)))
+ res= fill_record(buf, row);
+ table->status = res ? STATUS_NOT_FOUND : 0;
+ return error_code(res);
+}
+
+int ha_oqgraph::fill_record(byte *record, const open_query::row &row)
+{
+ Field **field= table->field;
+
+ 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)
+ {
+ field[0]->MOVE(ptrdiff);
+ field[1]->MOVE(ptrdiff);
+ field[2]->MOVE(ptrdiff);
+ field[3]->MOVE(ptrdiff);
+ field[4]->MOVE(ptrdiff);
+ field[5]->MOVE(ptrdiff);
+ }
+
+ // just each field specifically, no sense iterating
+ if (row.latch_indicator)
+ {
+ field[0]->set_notnull();
+ field[0]->store((longlong) row.latch);
+ }
+
+ if (row.orig_indicator)
+ {
+ field[1]->set_notnull();
+ field[1]->store((longlong) row.orig);
+ }
+
+ if (row.dest_indicator)
+ {
+ field[2]->set_notnull();
+ field[2]->store((longlong) row.dest);
+ }
+
+ if (row.weight_indicator)
+ {
+ field[3]->set_notnull();
+ field[3]->store((double) row.weight);
+ }
+
+ if (row.seq_indicator)
+ {
+ field[4]->set_notnull();
+ field[4]->store((longlong) row.seq);
+ }
+
+ if (row.link_indicator)
+ {
+ field[5]->set_notnull();
+ field[5]->store((longlong) row.link);
+ }
+
+ if (ptrdiff)
+ {
+ field[0]->MOVE(-ptrdiff);
+ field[1]->MOVE(-ptrdiff);
+ field[2]->MOVE(-ptrdiff);
+ field[3]->MOVE(-ptrdiff);
+ 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)
+{
+ return error_code(graph->random(scan));
+}
+
+int ha_oqgraph::rnd_next(byte *buf)
+{
+ int res;
+ open_query::row row;
+ STATISTIC_INCREMENT(ha_read_rnd_next_count);
+ if (!(res= graph->fetch_row(row)))
+ res= fill_record(buf, row);
+ table->status= res ? STATUS_NOT_FOUND: 0;
+ return error_code(res);
+}
+
+int ha_oqgraph::rnd_pos(byte * buf, byte *pos)
+{
+ int res;
+ open_query::row row;
+ STATISTIC_INCREMENT(ha_read_rnd_count);
+ if (!(res= graph->fetch_row(row, pos)))
+ res= fill_record(buf, row);
+ table->status=res ? STATUS_NOT_FOUND: 0;
+ return error_code(res);
+}
+
+void ha_oqgraph::position(const byte *record)
+{
+ graph->row_ref((void*) ref); // Ref is aligned
+}
+
+int ha_oqgraph::cmp_ref(const byte *ref1, const byte *ref2)
+{
+ return memcmp(ref1, ref2, oqgraph::sizeof_ref);
+}
+
+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
+ /*
+ 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();
+ 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;
+}
+
+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);
+}
+
+int ha_oqgraph::external_lock(THD *thd, int lock_type)
+{
+ return 0; // No external locking
+}
+
+
+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;
+}
+
+/*
+ We have to ignore ENOENT entries as the HEAP table is created on open and
+ not when doing a CREATE on the table.
+*/
+
+int ha_oqgraph::delete_table(const char *name)
+{
+ 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);
+}
+
+int ha_oqgraph::rename_table(const char * from, const char * to)
+{
+ 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;
+}
+
+
+ha_rows ha_oqgraph::records_in_range(uint inx, key_range *min_key,
+ key_range *max_key)
+{
+ KEY *key=table->key_info+inx;
+ //if (key->algorithm == HA_KEY_ALG_BTREE)
+ // return btree_records_in_range(file, inx, min_key, max_key);
+
+ if (!min_key || !max_key ||
+ min_key->length != max_key->length ||
+ min_key->length < key->key_length - key->key_part[2].store_length ||
+ min_key->flag != HA_READ_KEY_EXACT ||
+ max_key->flag != HA_READ_AFTER_KEY)
+ {
+ if (min_key->length == key->key_part[0].store_length)
+ {
+ // If latch is not null and equals 0, return # nodes
+ DBUG_ASSERT(key->key_part[0].store_length == 3);
+ if (key->key_part[0].null_bit && !min_key->key[0] &&
+ !min_key->key[1] && !min_key->key[2])
+ return graph->vertices_count();
+ }
+ return HA_POS_ERROR; // Can only use exact keys
+ }
+
+ if (RECORDS <= 1)
+ 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];
+
+ return result;
+}
+
+
+int ha_oqgraph::create(const char *name, TABLE *table_arg,
+ HA_CREATE_INFO *create_info)
+{
+ int res = -1;
+ OQGRAPH_INFO *share;
+
+ 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 (this->share)
+ info(HA_STATUS_NO_LOCK | HA_STATUS_CONST | HA_STATUS_VARIABLE);
+ return error_code(res);
+}
+
+
+void ha_oqgraph::update_create_info(HA_CREATE_INFO *create_info)
+{
+ table->file->info(HA_STATUS_AUTO);
+ //if (!(create_info->used_fields & HA_CREATE_USED_AUTO))
+ // 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 };
+
+mysql_declare_plugin(oqgraph)
+{
+ MYSQL_STORAGE_ENGINE_PLUGIN,
+ &oqgraph_storage_engine,
+ "OQGRAPH",
+ "Arjen Lentz & Antony T Curtis, Open Query",
+ oqgraph_description,
+ PLUGIN_LICENSE_GPL,
+ (int (*)(void*)) oqgraph_init, /* Plugin Init */
+ oqgraph_fini, /* Plugin Deinit */
+ 0x0200, /* Version: 2.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
new file mode 100644
index 00000000000..dcc14b074da
--- /dev/null
+++ b/storage/oqgraph/ha_oqgraph.h
@@ -0,0 +1,114 @@
+/* Copyright (C) 2007-2009 Arjen G Lentz & Antony T Curtis for Open Query
+ Portions of this file copyright (C) 2000-2006 MySQL AB
+
+ 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.
+
+ 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.II 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
+ ======================================================================
+*/
+
+#ifdef USE_PRAGMA_INTERFACE
+#pragma interface /* gcc class implementation */
+#endif
+
+
+typedef struct oqgraph_info_st OQGRAPH_INFO;
+
+#if MYSQL_VERSION_ID >= 50120
+typedef uchar byte;
+#endif
+
+namespace open_query
+{
+ struct row;
+ class oqgraph;
+}
+
+/* class for the the Open Query Graph handler */
+
+class ha_oqgraph: public handler
+{
+ OQGRAPH_INFO *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&);
+
+public:
+#if MYSQL_VERSION_ID >= 50100
+ ha_oqgraph(handlerton *hton, TABLE_SHARE *table);
+ ulonglong table_flags() const;
+#else
+ ha_oqgraph(TABLE *table);
+ ulong table_flags() const;
+#endif
+ ~ha_oqgraph() {}
+ const char *table_type() const
+ {
+ return "OQGRAPH";
+ }
+ const char *index_type(uint inx)
+ {
+ return "HASH";
+ }
+ /* Rows also use a fixed-size format */
+ enum row_type get_row_type() const { return ROW_TYPE_FIXED; }
+ const char **bas_ext() const;
+ ulong index_flags(uint inx, uint part, bool all_parts) const;
+ uint max_supported_keys() const { return MAX_KEY; }
+ uint max_supported_key_part_length() const { return MAX_KEY_LENGTH; }
+ double scan_time() { return (double) 1000000000; }
+ double read_time(uint index, uint ranges, ha_rows rows)
+ { return 1; }
+
+ int open(const char *name, int mode, uint test_if_locked);
+ int close(void);
+ int write_row(byte * buf);
+ int update_row(const byte * old_data, byte * new_data);
+ int delete_row(const byte * buf);
+ int index_read(byte * buf, const byte * key,
+ uint key_len, enum ha_rkey_function find_flag);
+ int index_read_idx(byte * buf, uint idx, const byte * key,
+ uint key_len, enum ha_rkey_function find_flag);
+ int index_next_same(byte * buf, const byte * key, uint key_len);
+ int rnd_init(bool scan);
+ int rnd_next(byte *buf);
+ int rnd_pos(byte * buf, byte *pos);
+ void position(const byte *record);
+ int info(uint);
+ int extra(enum ha_extra_function operation);
+ int external_lock(THD *thd, int lock_type);
+ int delete_all_rows(void);
+ ha_rows records_in_range(uint inx, key_range *min_key, key_range *max_key);
+ int delete_table(const char *from);
+ int rename_table(const char * from, const char * to);
+ int create(const char *name, TABLE *form, HA_CREATE_INFO *create_info);
+ void update_create_info(HA_CREATE_INFO *create_info);
+
+ 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);
+private:
+ void update_key_stats();
+};
diff --git a/storage/oqgraph/oqgraph_config.h.in b/storage/oqgraph/oqgraph_config.h.in
new file mode 100644
index 00000000000..18dad70a75d
--- /dev/null
+++ b/storage/oqgraph/oqgraph_config.h.in
@@ -0,0 +1,73 @@
+/* src/oqgraph_config.h.in. Generated from configure.in by autoheader. */
+
+/* Define to 1 if you have the <dlfcn.h> header file. */
+#undef HAVE_DLFCN_H
+
+/* Enables DTRACE Support */
+#undef HAVE_DTRACE
+
+/* Define to 1 if you have the <inttypes.h> header file. */
+#undef HAVE_INTTYPES_H
+
+/* Define to 1 if you have the <limits.h> header file. */
+#undef HAVE_LIMITS_H
+
+/* Define to 1 if you have the <memory.h> header file. */
+#undef HAVE_MEMORY_H
+
+/* Define to 1 if you have the <stdint.h> header file. */
+#undef HAVE_STDINT_H
+
+/* Define to 1 if you have the <stdlib.h> header file. */
+#undef HAVE_STDLIB_H
+
+/* Define to 1 if you have the <strings.h> header file. */
+#undef HAVE_STRINGS_H
+
+/* Define to 1 if you have the <string.h> header file. */
+#undef HAVE_STRING_H
+
+/* Define to 1 if you have the <syslimits.h> header file. */
+#undef HAVE_SYSLIMITS_H
+
+/* Define to 1 if you have the <sys/stat.h> header file. */
+#undef HAVE_SYS_STAT_H
+
+/* Define to 1 if you have the <sys/types.h> header file. */
+#undef HAVE_SYS_TYPES_H
+
+/* Define to 1 if you have the <unistd.h> header file. */
+#undef HAVE_UNISTD_H
+
+/* Source directory for MySQL */
+#undef MYSQL_SRC
+
+/* Name of package */
+#undef PACKAGE
+
+/* Define to the address where bug reports for this package should be sent. */
+#undef PACKAGE_BUGREPORT
+
+/* Define to the full name of this package. */
+#undef PACKAGE_NAME
+
+/* Define to the full name and version of this package. */
+#undef PACKAGE_STRING
+
+/* Define to the one symbol short name of this package. */
+#undef PACKAGE_TARNAME
+
+/* Define to the version of this package. */
+#undef PACKAGE_VERSION
+
+/* Define to 1 if you have the ANSI C header files. */
+#undef STDC_HEADERS
+
+/* Version number of package */
+#undef VERSION
+
+/* Define to empty if `const' does not conform to ANSI C. */
+#undef const
+
+/* Define to `unsigned int' if <sys/types.h> does not define. */
+#undef size_t
diff --git a/storage/oqgraph/oqgraph_probes.d b/storage/oqgraph/oqgraph_probes.d
new file mode 100644
index 00000000000..bfdee29ba6e
--- /dev/null
+++ b/storage/oqgraph/oqgraph_probes.d
@@ -0,0 +1,19 @@
+/* Copyright (C) 2004-2005 MySQL AB
+
+ 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.
+
+ 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 */
+
+provider oqgraph {
+ probe open();
+ probe close();
+};
diff --git a/storage/oqgraph/oqgraph_probes.h b/storage/oqgraph/oqgraph_probes.h
new file mode 100644
index 00000000000..5169ccf320a
--- /dev/null
+++ b/storage/oqgraph/oqgraph_probes.h
@@ -0,0 +1,45 @@
+/*
+ * Generated by dtrace(1M).
+ */
+
+#ifndef _OQGRAPH_PROBES_H
+#define _OQGRAPH_PROBES_H
+
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#if _DTRACE_VERSION
+
+#define OQGRAPH_CLOSE() \
+ __dtrace_oqgraph___close()
+#define OQGRAPH_CLOSE_ENABLED() \
+ __dtraceenabled_oqgraph___close()
+#define OQGRAPH_OPEN() \
+ __dtrace_oqgraph___open()
+#define OQGRAPH_OPEN_ENABLED() \
+ __dtraceenabled_oqgraph___open()
+
+
+extern void __dtrace_oqgraph___close(void);
+extern int __dtraceenabled_oqgraph___close(void);
+extern void __dtrace_oqgraph___open(void);
+extern int __dtraceenabled_oqgraph___open(void);
+
+#else
+
+#define OQGRAPH_CLOSE()
+#define OQGRAPH_CLOSE_ENABLED() (0)
+#define OQGRAPH_OPEN()
+#define OQGRAPH_OPEN_ENABLED() (0)
+
+#endif
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _OQGRAPH_PROBES_H */
diff --git a/storage/oqgraph/plug.in b/storage/oqgraph/plug.in
new file mode 100644
index 00000000000..a39015c07b7
--- /dev/null
+++ b/storage/oqgraph/plug.in
@@ -0,0 +1,32 @@
+MYSQL_STORAGE_ENGINE(oqgraph,,[Graph Storage Engine],
+ [Open Query Graph Computation Engine], [])
+MYSQL_PLUGIN_DYNAMIC(oqgraph, [oqgraph_engine.la])
+MYSQL_PLUGIN_DEPENDS_ON_MYSQL_INTERNALS(oqgraph, [ha_oqgraph.cc])
+AM_CONDITIONAL([BUILD_OQGRAPH_FOR_MYSQL], true)
+AM_CONDITIONAL([BUILD_OQGRAPH_STANDALONE], false)
+AM_CONDITIONAL([HAVE_DTRACE], false)
+
+AC_LANG_PUSH([C++])
+AC_CHECK_HEADER([boost/graph/properties.hpp],[:],[
+ mysql_plugin_oqgraph=no
+ with_plugin_oqgraph=no
+])
+
+save_CXXFLAGS="${CXXFLAGS}"
+CXXFLAGS="-fexceptions -fimplicit-templates -O3 -fstrict-aliasing -falign-loops -fvisibility-inlines-hidden -funroll-loops -fno-trapping-math"
+
+AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[
+ #include <boost/graph/graph_traits.hpp>
+ #include <boost/graph/adjacency_list.hpp>
+ #include <boost/graph/dijkstra_shortest_paths.hpp>
+
+ using namespace boost;
+]],[[
+ typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
+ Graph g(10);
+]])],[],[
+ mysql_plugin_oqgraph=no
+ with_plugin_oqgraph=no
+])
+CXXFLAGS="${save_CXXFLAGS}"
+AC_LANG_POP()
View Lorry Controller Status