#At lp:maria 2764 knielsen@knielsen-hq.org 2010-01-04 Import OQGraph engine into MariaDB. added: mysql-test/suite/oqgraph/ mysql-test/suite/oqgraph/include/ mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc mysql-test/suite/oqgraph/r/ mysql-test/suite/oqgraph/r/basic.result mysql-test/suite/oqgraph/t/ mysql-test/suite/oqgraph/t/basic-master.opt mysql-test/suite/oqgraph/t/basic.test storage/oqgraph/ storage/oqgraph/CMakeFiles.txt storage/oqgraph/Makefile.am storage/oqgraph/graphcore-graph.h storage/oqgraph/graphcore-types.h storage/oqgraph/graphcore.cc storage/oqgraph/graphcore.h storage/oqgraph/graphstore.c storage/oqgraph/graphstore.h storage/oqgraph/ha_oqgraph.cc storage/oqgraph/ha_oqgraph.h storage/oqgraph/oqgraph_config.h.in storage/oqgraph/oqgraph_probes.d storage/oqgraph/oqgraph_probes.h storage/oqgraph/plug.in modified: BUILD/SETUP.sh mysql-test/mysql-test-run.pl === modified file 'BUILD/SETUP.sh' --- a/BUILD/SETUP.sh 2009-10-29 00:04:56 +0000 +++ b/BUILD/SETUP.sh 2010-01-04 08:27:50 +0000 @@ -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) === modified file 'mysql-test/mysql-test-run.pl' --- a/mysql-test/mysql-test-run.pl 2009-11-06 17:24:38 +0000 +++ b/mysql-test/mysql-test-run.pl 2010-01-04 08:27:50 +0000 @@ -126,7 +126,7 @@ my $path_config_file; # The ge # 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 # ---------------------------------------------------- === added directory 'mysql-test/suite/oqgraph' === added directory 'mysql-test/suite/oqgraph/include' === added file 'mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc' --- a/mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc 1970-01-01 00:00:00 +0000 +++ b/mysql-test/suite/oqgraph/include/have_oqgraph_engine.inc 2010-01-04 08:27:50 +0000 @@ -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; === added directory 'mysql-test/suite/oqgraph/r' === added file 'mysql-test/suite/oqgraph/r/basic.result' --- a/mysql-test/suite/oqgraph/r/basic.result 1970-01-01 00:00:00 +0000 +++ b/mysql-test/suite/oqgraph/r/basic.result 2010-01-04 08:27:50 +0000 @@ -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; === added directory 'mysql-test/suite/oqgraph/t' === added file 'mysql-test/suite/oqgraph/t/basic-master.opt' --- a/mysql-test/suite/oqgraph/t/basic-master.opt 1970-01-01 00:00:00 +0000 +++ b/mysql-test/suite/oqgraph/t/basic-master.opt 2010-01-04 08:27:50 +0000 @@ -0,0 +1,2 @@ +$OQGRAPH_PLUGIN_OPT +$OQGRAPH_PLUGIN_LOAD === added file 'mysql-test/suite/oqgraph/t/basic.test' --- a/mysql-test/suite/oqgraph/t/basic.test 1970-01-01 00:00:00 +0000 +++ b/mysql-test/suite/oqgraph/t/basic.test 2010-01-04 08:27:50 +0000 @@ -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; === added directory 'storage/oqgraph' === added file 'storage/oqgraph/CMakeFiles.txt' --- a/storage/oqgraph/CMakeFiles.txt 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/CMakeFiles.txt 2010-01-04 08:27:50 +0000 @@ -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) === added file 'storage/oqgraph/Makefile.am' --- a/storage/oqgraph/Makefile.am 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/Makefile.am 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/graphcore-graph.h' --- a/storage/oqgraph/graphcore-graph.h 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/graphcore-graph.h 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/graphcore-types.h' --- a/storage/oqgraph/graphcore-types.h 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/graphcore-types.h 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/graphcore.cc' --- a/storage/oqgraph/graphcore.cc 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/graphcore.cc 2010-01-04 08:27:50 +0000 @@ -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(); + } +} === added file 'storage/oqgraph/graphcore.h' --- a/storage/oqgraph/graphcore.h 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/graphcore.h 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/graphstore.c' --- a/storage/oqgraph/graphstore.c 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/graphstore.c 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/graphstore.h' --- a/storage/oqgraph/graphstore.h 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/graphstore.h 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/ha_oqgraph.cc' --- a/storage/oqgraph/ha_oqgraph.cc 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/ha_oqgraph.cc 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/ha_oqgraph.h' --- a/storage/oqgraph/ha_oqgraph.h 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/ha_oqgraph.h 2010-01-04 08:27:50 +0000 @@ -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(); +}; === added file 'storage/oqgraph/oqgraph_config.h.in' --- a/storage/oqgraph/oqgraph_config.h.in 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/oqgraph_config.h.in 2010-01-04 08:27:50 +0000 @@ -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 === added file 'storage/oqgraph/oqgraph_probes.d' --- a/storage/oqgraph/oqgraph_probes.d 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/oqgraph_probes.d 2010-01-04 08:27:50 +0000 @@ -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(); +}; === added file 'storage/oqgraph/oqgraph_probes.h' --- a/storage/oqgraph/oqgraph_probes.h 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/oqgraph_probes.h 2010-01-04 08:27:50 +0000 @@ -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 */ === added file 'storage/oqgraph/plug.in' --- a/storage/oqgraph/plug.in 1970-01-01 00:00:00 +0000 +++ b/storage/oqgraph/plug.in 2010-01-04 08:27:50 +0000 @@ -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()