Adding upstream version 1:10.11.6.upstream/1%10.11.6

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 490 insertions, 0 deletions

diff --git a/storage/oqgraph/oqgraph_shim.h b/storage/oqgraph/oqgraph_shim.h
new file mode 100644
index 00000000..93c4e5fe
--- /dev/null
+++ b/storage/oqgraph/oqgraph_shim.h
@@ -0,0 +1,490 @@
+/* Copyright (C) 2007-2013 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
+
+/* ======================================================================
+   Open Query Graph Computation Engine, based on a concept by Arjen Lentz
+   v3 implementation by Antony Curtis, Arjen Lentz, Andrew McDonnell
+   For more information, documentation, support, enhancement engineering,
+   see http://openquery.com/graph or contact graph@openquery.com
+   ======================================================================
+*/
+
+#pragma once
+
+#include "oqgraph_judy.h"
+#include "oqgraph_thunk.h"
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/adjacency_iterator.hpp>
+
+namespace open_query
+{
+  struct OQGraphTraversalCategory
+    : public boost::bidirectional_graph_tag
+    , public boost::adjacency_graph_tag
+    , public boost::edge_list_graph_tag
+  { };
+
+}
+
+namespace oqgraph3
+{
+  struct traversal_category
+    : public boost::adjacency_graph_tag
+    , public boost::bidirectional_graph_tag
+    , public boost::edge_list_graph_tag
+  { };
+
+  struct edge_iterator
+  {
+    typedef edge_iterator self;
+    typedef edge_info value_type;
+    typedef edge_info& reference;
+    typedef edge_info pointer;
+    typedef std::ptrdiff_t difference_type;
+    typedef std::input_iterator_tag iterator_category;
+    edge_iterator() { }
+    edge_iterator(const graph_ptr& graph, size_t offset=0)
+      : _graph(graph)
+      , _offset(offset) { }
+    value_type operator*();
+    self& operator+=(size_t n) { _offset+= n; return *this; }
+    self& operator++() { ++_offset; return *this; }
+    self operator++(int)
+    { size_t temp= _offset++; return edge_iterator(_graph, temp); }
+    bool seek();
+    bool operator==(const self& x);
+    bool operator!=(const self& x);
+    graph_ptr _graph;
+    size_t _offset;
+  };
+
+  struct vertex_iterator
+  {
+    typedef vertex_iterator self;
+    typedef vertex_id value_type;
+    typedef vertex_id& reference;
+    typedef vertex_id pointer;
+    typedef std::ptrdiff_t difference_type;
+    typedef std::input_iterator_tag iterator_category;
+    vertex_iterator() { }
+    vertex_iterator(const cursor_ptr& pos) : _cursor(pos.operator->()) { }
+    vertex_id operator*() const
+    {
+      edge_info edge(*_cursor);
+      if (!_seen.test(edge.origid()))
+        return edge.origid();
+      else
+        return edge.destid();
+    }
+
+    self& operator++()
+    {
+      edge_info edge(*_cursor);
+      if (!_seen.test(edge.origid()))
+      {
+        _seen.set(edge.origid());
+      }
+      else
+      {
+        _seen.set(edge.destid());
+      }
+
+      while (_seen.test(edge.origid()) && _seen.test(edge.destid()))
+      {
+        if (_cursor->seek_next())
+          break;
+        edge= _cursor;
+      }
+      return *this;
+    }
+    self operator++(int) { cursor* t(new cursor(*_cursor)); ++(*this); return vertex_iterator(t); }
+    bool operator==(const self& x) { return *_cursor == *x._cursor; }
+    bool operator!=(const self& x) { return *_cursor != *x._cursor; }
+    cursor_ptr _cursor;
+    open_query::judy_bitset _seen;
+  };
+
+
+  struct out_edge_iterator
+  {
+    typedef out_edge_iterator self;
+    typedef edge_info value_type;
+    typedef edge_info& reference;
+    typedef edge_info pointer;
+    typedef std::ptrdiff_t difference_type;
+    typedef std::input_iterator_tag iterator_category;
+    out_edge_iterator() { }
+    out_edge_iterator(const cursor_ptr& cursor) : _cursor(cursor) { }
+    value_type operator*() { return value_type(_cursor); }
+    self& operator++() { _cursor->seek_next(); return *this; }
+    self operator++(int)
+    { cursor_ptr t(new cursor(*_cursor)); ++(*this); return out_edge_iterator(t); }
+    bool operator==(const self& x) { return _cursor == x._cursor; }
+    bool operator!=(const self& x) { return _cursor != x._cursor; }
+    cursor_ptr _cursor;
+  };
+
+  struct in_edge_iterator
+  {
+    typedef in_edge_iterator self;
+    typedef edge_info value_type;
+    typedef edge_info& reference;
+    typedef edge_info pointer;
+    typedef std::ptrdiff_t difference_type;
+    typedef std::input_iterator_tag iterator_category;
+    in_edge_iterator() { }
+    in_edge_iterator(const cursor_ptr& cursor) : _cursor(cursor) { }
+    value_type operator*() const { return value_type(_cursor); }
+    self& operator++() { _cursor->seek_next(); return *this; }
+    self operator++(int)
+    { cursor_ptr t(new cursor(*_cursor)); ++(*this); return in_edge_iterator(t); }
+    bool operator==(const self& x) const { return _cursor == x._cursor; }
+    bool operator!=(const self& x) const { return _cursor != x._cursor; }
+    cursor_ptr _cursor;
+  };
+
+  struct vertex_index_property_map
+  {
+    typedef vertex_id value_type;
+    typedef value_type reference;
+    typedef vertex_id key_type;
+    typedef boost::readable_property_map_tag category;
+    vertex_index_property_map(const graph& g) : _g(g) { }
+    const graph& _g;
+
+    friend inline reference
+    get(const vertex_index_property_map&, key_type key)
+    { return key; }
+  };
+
+  struct edge_weight_property_map
+  {
+    typedef weight_t value_type;
+    typedef value_type reference;
+    typedef edge_info key_type;
+    typedef boost::readable_property_map_tag category;
+    edge_weight_property_map(const graph& g) : _g(g) { }
+    friend inline reference
+    get(const edge_weight_property_map& p, const key_type& key)
+    { return key.weight(); }
+
+    const graph& _g;
+  };
+
+  struct edge_index_property_map
+  {
+    typedef cursor_ptr value_type;
+    typedef cursor_ptr reference;
+    typedef edge_info key_type;
+    typedef boost::readable_property_map_tag category;
+    edge_index_property_map(const graph& g) : _g(g) { }
+    const graph& _g;
+  };
+}
+
+namespace boost
+{
+
+  template<>
+  struct graph_traits<oqgraph3::graph>
+  {
+    typedef oqgraph3::vertex_id vertex_descriptor;
+    typedef oqgraph3::edge_info edge_descriptor;
+    typedef boost::adjacency_iterator_generator<
+        oqgraph3::graph,
+        oqgraph3::vertex_id,
+        oqgraph3::out_edge_iterator>::type adjacency_iterator;
+    typedef oqgraph3::out_edge_iterator out_edge_iterator;
+    typedef oqgraph3::in_edge_iterator in_edge_iterator;
+    typedef oqgraph3::vertex_iterator vertex_iterator;
+    typedef oqgraph3::edge_iterator edge_iterator;
+
+    typedef boost::directed_tag directed_category;
+    typedef boost::allow_parallel_edge_tag edge_parallel_category;
+    typedef oqgraph3::traversal_category traversal_category;
+
+    typedef oqgraph3::vertices_size_type vertices_size_type;
+    typedef oqgraph3::edges_size_type edges_size_type;
+    typedef oqgraph3::degree_size_type degree_size_type;
+
+    static inline oqgraph3::vertex_id null_vertex()
+    { return oqgraph3::vertex_id(-1); }
+  };
+
+  template<>
+  struct graph_traits<const oqgraph3::graph>
+    : public graph_traits<oqgraph3::graph>
+  { };
+
+  template <>
+  struct graph_property_type<oqgraph3::graph>
+  {
+    typedef no_property type;
+  };
+
+  template <>
+  struct vertex_property_type<oqgraph3::graph>
+  {
+    typedef no_property type;
+  };
+
+  template <>
+  struct edge_property_type<oqgraph3::graph>
+  {
+    typedef no_property type;
+  };
+
+#if BOOST_VERSION < 106000 && BOOST_VERSION >= 104601
+  template <>
+  struct graph_bundle_type<oqgraph3::graph>
+  {
+    typedef no_graph_bundle type;
+  };
+
+  template <>
+  struct vertex_bundle_type<oqgraph3::graph>
+  {
+    typedef no_vertex_bundle type;
+  };
+
+  template <>
+  struct edge_bundle_type<oqgraph3::graph>
+  {
+    typedef no_edge_bundle type;
+  };
+#endif
+
+  template<>
+  struct property_map<oqgraph3::graph, edge_weight_t>
+  {
+    typedef void type;
+    typedef oqgraph3::edge_weight_property_map const_type;
+  };
+
+  template<>
+  struct property_map<oqgraph3::graph, vertex_index_t>
+  {
+    typedef void type;
+    typedef oqgraph3::vertex_index_property_map const_type;
+  };
+
+  template<>
+  struct property_map<oqgraph3::graph, edge_index_t>
+  {
+    typedef void type;
+    typedef oqgraph3::edge_index_property_map const_type;
+  };
+
+}
+
+namespace oqgraph3
+{
+  using namespace boost;
+
+  inline graph_traits<oqgraph3::graph>::vertex_descriptor
+  source(
+      const graph_traits<oqgraph3::graph>::edge_descriptor& e,
+      const oqgraph3::graph&)
+  { return e.origid(); }
+
+  inline graph_traits<oqgraph3::graph>::vertex_descriptor
+  target(
+      const graph_traits<oqgraph3::graph>::edge_descriptor& e,
+      const oqgraph3::graph&)
+  { return e.destid(); }
+
+  inline std::pair<
+      graph_traits<oqgraph3::graph>::out_edge_iterator,
+      graph_traits<oqgraph3::graph>::out_edge_iterator>
+  out_edges(
+      graph_traits<oqgraph3::graph>::vertex_descriptor v,
+      const oqgraph3::graph& g)
+  {
+    oqgraph3::cursor*
+        end= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
+    oqgraph3::cursor*
+        start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
+    start->seek_to(v, boost::none);
+    return std::make_pair(
+        graph_traits<oqgraph3::graph>::out_edge_iterator(start),
+        graph_traits<oqgraph3::graph>::out_edge_iterator(end));
+  }
+
+  inline graph_traits<oqgraph3::graph>::degree_size_type
+  out_degree(
+      graph_traits<oqgraph3::graph>::vertex_descriptor v,
+      const oqgraph3::graph& g)
+  {
+    std::size_t count = 0;
+    for (std::pair<
+            graph_traits<oqgraph3::graph>::out_edge_iterator,
+            graph_traits<oqgraph3::graph>::out_edge_iterator> i= out_edges(v, g);
+        i.first != i.second; ++i.first)
+    {
+      ++count;
+    }
+    return count;
+  }
+
+
+  inline std::pair<
+      graph_traits<oqgraph3::graph>::in_edge_iterator,
+      graph_traits<oqgraph3::graph>::in_edge_iterator>
+  in_edges(
+      graph_traits<oqgraph3::graph>::vertex_descriptor v,
+      const oqgraph3::graph& g)
+  {
+    oqgraph3::cursor*
+        end= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
+    oqgraph3::cursor*
+        start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
+    start->seek_to(boost::none, v);
+    return std::make_pair(
+        graph_traits<oqgraph3::graph>::in_edge_iterator(start),
+        graph_traits<oqgraph3::graph>::in_edge_iterator(end));
+  }
+
+  inline graph_traits<oqgraph3::graph>::degree_size_type
+  in_degree(
+      graph_traits<oqgraph3::graph>::vertex_descriptor v,
+      const oqgraph3::graph& g)
+  {
+    std::size_t count = 0;
+    for (std::pair<
+            graph_traits<oqgraph3::graph>::in_edge_iterator,
+            graph_traits<oqgraph3::graph>::in_edge_iterator> it= in_edges(v, g);
+        it.first != it.second; ++it.first)
+    {
+      ++count;
+    }
+    return count;
+  }
+
+
+  // EdgeListGraph concepts
+  inline std::pair<
+      graph_traits<oqgraph3::graph>::edge_iterator,
+      graph_traits<oqgraph3::graph>::edge_iterator>
+  edges(const oqgraph3::graph& g)
+  {
+    std::size_t end= std::size_t(-1);
+    std::size_t start= end;
+
+    if (g.num_edges())
+      start= 0;
+
+    return std::make_pair(
+        graph_traits<oqgraph3::graph>::edge_iterator(
+            const_cast<oqgraph3::graph*>(&g), start),
+        graph_traits<oqgraph3::graph>::edge_iterator(
+            const_cast<oqgraph3::graph*>(&g), end));
+  }
+
+  inline std::pair<
+      graph_traits<oqgraph3::graph>::vertex_iterator,
+      graph_traits<oqgraph3::graph>::vertex_iterator>
+  vertices(const oqgraph3::graph& g)
+  {
+    oqgraph3::cursor*
+        start= new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
+    start->seek_to(boost::none, boost::none);
+    return std::make_pair(
+        graph_traits<oqgraph3::graph>::vertex_iterator(start),
+        graph_traits<oqgraph3::graph>::vertex_iterator(
+            new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g))));
+  }
+
+  inline graph_traits<oqgraph3::graph>::vertices_size_type
+  num_vertices(const oqgraph3::graph& g)
+  {
+    std::size_t count = 0;
+    for (std::pair<
+            graph_traits<oqgraph3::graph>::vertex_iterator,
+            graph_traits<oqgraph3::graph>::vertex_iterator> i= vertices(g);
+        i.first != i.second; ++i.first)
+    {
+      ++count;
+    }
+    return count;
+  }
+
+  inline property_map<
+      oqgraph3::graph,
+      edge_weight_t>::const_type::reference
+  get(
+      edge_weight_t,
+      const oqgraph3::graph& g,
+      const property_map<
+          oqgraph3::graph,
+          edge_weight_t>::const_type::key_type& key)
+  { return key.weight(); }
+
+  inline property_map<
+      oqgraph3::graph,
+      edge_weight_t>::const_type
+  get(edge_weight_t,
+      const oqgraph3::graph& g)
+  { return property_map<oqgraph3::graph, edge_weight_t>::const_type(g); }
+
+  inline property_map<
+      oqgraph3::graph,
+      edge_index_t>::const_type::reference
+  get(edge_index_t,
+      const oqgraph3::graph&,
+      const property_map<
+          oqgraph3::graph,
+          edge_index_t>::const_type::key_type& key)
+  { return key._cursor; }
+
+  inline property_map<oqgraph3::graph, edge_index_t>::const_type
+  get(edge_index_t, const oqgraph3::graph& g)
+  { return property_map<oqgraph3::graph, edge_index_t>::const_type(g); }
+
+  inline property_map<oqgraph3::graph, edge_index_t>::const_type::reference
+  get(const property_map<oqgraph3::graph, edge_index_t>::const_type&,
+      const property_map<oqgraph3::graph,
+      edge_index_t>::const_type::key_type& key)
+  { return key._cursor; }
+
+  inline property_map<oqgraph3::graph, vertex_index_t>::const_type::reference
+  get(vertex_index_t, const oqgraph3::graph&,
+      const property_map<oqgraph3::graph,
+      vertex_index_t>::const_type::key_type& key)
+  { return key; }
+
+  inline property_map<oqgraph3::graph, vertex_index_t>::const_type
+  get(vertex_index_t, const oqgraph3::graph& g)
+  { return property_map<oqgraph3::graph, vertex_index_t>::const_type(g); }
+
+  inline optional<graph_traits<oqgraph3::graph>::vertex_descriptor>
+  find_vertex(oqgraph3::vertex_id id, const oqgraph3::graph& g)
+  {
+    // Fix for https://bugs.launchpad.net/oqgraph/+bug/1196020 returning vertex even when not in graph
+    // Psuedocode for fix:
+    // if count(*) from g->TABLE where source=id or target=id > 0 then return id else return null
+    oqgraph3::cursor* found_cursor = new oqgraph3::cursor(const_cast<oqgraph3::graph*>(&g));
+    bool found = (found_cursor->seek_to(id, boost::none) && found_cursor->seek_to(boost::none, id));
+    delete found_cursor;
+    if (found) {
+      // id is neither a from or a to in a link
+      return optional<graph_traits<oqgraph3::graph>::vertex_descriptor>();
+    }
+    return id;
+  }
+
+}
+