List:Commits« Previous MessageNext Message »
From:Martin Hansson Date:January 13 2011 12:48pm
Subject:bzr commit into mysql-trunk-bugfixing branch (martin.hansson:3263)
View as plain text  
#At file:///data0/martin/bzrroot/refactoring-Bitmap_set/n-mr-o-t/ based on revid:tor.didriksen@stripped

 3263 Martin Hansson	2011-01-13
      The Bitmap_set class. The class hides the bitmaps that represent sets
      frequently used in our source code behind an STL-like container interface. The
      benefits are safer type checks, less boilerplate code, an optimized iterator
      and a familiar and consistent interface.

    added:
      sql/sql_set.h
      unittest/gunit/sql_set-t.cc
    modified:
      unittest/gunit/CMakeLists.txt
=== added file 'sql/sql_set.h'
--- a/sql/sql_set.h	1970-01-01 00:00:00 +0000
+++ b/sql/sql_set.h	2011-01-13 12:48:09 +0000
@@ -0,0 +1,140 @@
+#ifndef INCLUDES_MYSQL_SQL_SET_H
+#define INCLUDES_MYSQL_SQL_SET_H
+/* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved.
+
+   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 */
+
+#include "sql_bitmap.h"
+#include "my_global.h"
+
+template <class T> class Bitmap_set_iterator;
+template <class T> class Bitmap_set_reverse_iterator;
+
+/**
+   A set implemented as a bitmap. Due to this implementation, operations that
+   normally are quite expensive, typically having O(n log n) complexity, are
+   extremely cheap. A set consists of a bitmap and mechanisms for lookup in
+   both directions. 
+
+   - In order to find an element of class T given its bit index, a lookup
+     array of pointers is employed.
+
+   - In order to find the bit representing an element of type T, a pointer to
+     a bitmap member is employed.
+
+   The n:th bit in the bitmap represents the member at position n in the
+   lookup array, where the first member has position 0. A set consisting of
+   this element is represented by the bitmap 1.
+
+   For obvious reasons, it cannot be allowed to perform a set operation on two
+   sets that have different lookup arrays, even if they are of the same
+   type. Attempts at such operations will result in failed assertions.
+ */
+template <class T> class Bitmap_set
+{
+
+private:
+  ulonglong m_map;
+  T*const* const m_lookup_array;
+  const ulonglong T::*m_map_member;
+
+protected:
+  inline ulonglong get_map(const T& t) const { return t.*m_map_member; }
+  inline T* lookup(uint bit) const { return m_lookup_array[bit]; }
+
+public:
+
+  /**
+     Creates a set from the given bitmap.
+
+     @param The bitmap for initializing the set.
+
+     @param lookup_array Pointer to an array of pointers for looking up
+     elements given a bit index.
+
+     @param map_member Pointer (offset) to the member of T that holds a bitmap
+     representing the set of that element.
+   */
+  Bitmap_set(ulonglong map, T*const* lookup_array, const ulonglong T::*map_member) :
+    m_map(map), m_lookup_array(lookup_array), m_map_member(map_member) {}
+    
+  inline bool is_empty() const { return m_map == 0; }
+  inline bool contains(const T *t) const { return ((get_map(*t)) & m_map) != 0; }
+  
+  /**
+     Adds the new element to the set.
+
+     @retval false If the element was already in the set.
+     @retval true  If the element was not in the set prior to insertion.
+   */
+  inline bool add(T *t)
+  { 
+    bool was_there= contains(t);
+    m_map|= get_map(*t);
+    return !was_there;
+  }
+  
+  /**
+     Removes the element from the set.
+
+     @retval true If the element was in the set prior to removal.
+     @retval false If the element was not in the set.
+   */
+  inline bool remove(T *t) {
+    bool was_there= contains(t);
+    m_map&= ~get_map(*t);
+    return was_there;
+  }
+  
+  Bitmap_set<T> set_union(const Bitmap_set<T>& other) const
+  {
+    DBUG_ASSERT(m_lookup_array == other.m_lookup_array);
+    return Bitmap_set<T>(m_map | other.m_map, m_lookup_array, m_map_member);
+  }
+  
+  Bitmap_set<T> set_intersection(const Bitmap_set<T>& other) const
+  {
+    DBUG_ASSERT(m_lookup_array == other.m_lookup_array);
+    return Bitmap_set<T>(m_map & other.m_map, m_lookup_array, m_map_member);
+  }
+  
+  friend class Bitmap_set_iterator<T>;
+  friend class Bitmap_set_reverse_iterator<T>;
+};
+
+
+template <class T> class Bitmap_set_iterator {
+private:
+  const Bitmap_set<T>& m_set;
+  Table_map_iterator m_it;
+  
+public:
+  Bitmap_set_iterator(const Bitmap_set<T>& set) :
+    m_set(set), m_it(m_set.m_map) {}
+
+  /**
+     Returns the next element in the set, or NULL if there are no more elements.
+
+     @retval NULL If all elements have been iterated through.
+     @retval element If there was at least one element left.
+   */
+  inline T* operator++(int) {
+    uint next_bit= m_it.next_bit();
+    if (next_bit == Table_map_iterator::BITMAP_END)
+      return NULL;
+    return m_set.lookup(next_bit);
+  }
+};
+
+#endif // INCLUDES_MYSQL_SQL_SET_H

=== modified file 'unittest/gunit/CMakeLists.txt'
--- a/unittest/gunit/CMakeLists.txt	2010-12-17 09:41:21 +0000
+++ b/unittest/gunit/CMakeLists.txt	2011-01-13 12:48:09 +0000
@@ -214,6 +214,7 @@ SET(TESTS
   mdl_mytap
   my_regex
   sql_list
+  sql_set
   thread_utils
   )
 

=== added file 'unittest/gunit/sql_set-t.cc'
--- a/unittest/gunit/sql_set-t.cc	1970-01-01 00:00:00 +0000
+++ b/unittest/gunit/sql_set-t.cc	2011-01-13 12:48:09 +0000
@@ -0,0 +1,136 @@
+#include "my_config.h"
+#include <gtest/gtest.h>
+
+#include "sql_set.h"
+
+
+namespace {
+
+  class A {
+  public:
+    const ulonglong map;
+    A(ulonglong map_arg) : map(map_arg) {}
+  };
+
+  class Sql_set_test : public ::testing::Test {
+
+  public:
+    static const uint SET_SIZE= sizeof(ulonglong) * 8;
+    A *a_store[SET_SIZE];
+
+    Sql_set_test() {
+      for (uint i= 0; i < SET_SIZE; i++)
+        a_store[i]= new A(1 << i);
+    }
+
+    ~Sql_set_test() {
+      for (uint i= 0; i < SET_SIZE; i++)
+        delete a_store[i];
+    }
+
+  };
+
+  TEST_F(Sql_set_test, self_test)
+  {
+    for (uint i= 0; i < SET_SIZE; i++)
+    {
+      // Test the map member
+      EXPECT_EQ(a_store[i]->map, 1 << i);
+    }
+  }
+
+  TEST_F(Sql_set_test, add)
+  {
+    Bitmap_set<A> as(0, a_store, &A::map);
+    EXPECT_TRUE(as.add(a_store[4]));
+    EXPECT_TRUE(as.contains(a_store[4]));
+    EXPECT_FALSE(as.add(a_store[4]));
+  }
+
+  TEST_F(Sql_set_test, remove)
+  {
+    Bitmap_set<A> as(1 << 5, a_store, &A::map);
+    EXPECT_TRUE(as.remove(a_store[5]));
+    EXPECT_FALSE(as.contains(a_store[5]));
+    EXPECT_FALSE(as.remove(a_store[5]));
+  }
+
+  TEST_F(Sql_set_test, contains)
+  {
+    const Bitmap_set<A> bs(1, a_store, &A::map);
+    EXPECT_TRUE(bs.contains(a_store[0]));
+  }
+
+  TEST_F(Sql_set_test, set_union)
+  {
+    const Bitmap_set<A> set_x(1 | 4 | 16,   a_store, &A::map);
+    const Bitmap_set<A> set_y(4 | 32 | 128, a_store, &A::map);
+
+    const Bitmap_set<A> the_union= set_x.set_union(set_y);
+
+    EXPECT_TRUE (the_union.contains(a_store[0]));
+    EXPECT_FALSE(the_union.contains(a_store[1]));
+    EXPECT_TRUE (the_union.contains(a_store[2]));
+    EXPECT_FALSE(the_union.contains(a_store[3]));
+    EXPECT_TRUE (the_union.contains(a_store[4]));
+    EXPECT_TRUE (the_union.contains(a_store[5]));
+    EXPECT_FALSE(the_union.contains(a_store[6]));
+    EXPECT_TRUE (the_union.contains(a_store[7]));
+    EXPECT_FALSE(the_union.contains(a_store[8]));
+    EXPECT_FALSE(the_union.contains(a_store[9]));
+  }
+
+  TEST_F(Sql_set_test, set_intersection)
+  {
+    const Bitmap_set<A> x(1 | 4 | 16,   a_store, &A::map);
+    const Bitmap_set<A> y(4 | 32 | 128, a_store, &A::map);
+
+    const Bitmap_set<A> z= x.set_intersection(y);
+
+    EXPECT_FALSE(z.contains(a_store[0]));
+    EXPECT_FALSE(z.contains(a_store[1]));
+    EXPECT_TRUE (z.contains(a_store[2]));
+    EXPECT_FALSE(z.contains(a_store[3]));
+    EXPECT_FALSE(z.contains(a_store[4]));
+    EXPECT_FALSE(z.contains(a_store[5]));
+    EXPECT_FALSE(z.contains(a_store[6]));
+    EXPECT_FALSE(z.contains(a_store[7]));
+    EXPECT_FALSE(z.contains(a_store[8]));
+    EXPECT_FALSE(z.contains(a_store[9]));
+  }
+
+  TEST_F(Sql_set_test, singleton_iterator)
+  {
+    const Bitmap_set<A> as(1, a_store, &A::map);
+    Bitmap_set_iterator<A> it(as);
+    EXPECT_EQ(a_store[0], it++);
+    EXPECT_EQ((A*)NULL, it++);
+
+    const Bitmap_set<A> a2(2, a_store, &A::map);
+    Bitmap_set_iterator<A> it2(a2);
+    EXPECT_EQ(it2++, a_store[1]);
+    EXPECT_EQ(it2++, (A*)NULL);
+
+    const Bitmap_set<A> as3(1ULL << (SET_SIZE - 1), a_store, &A::map);
+    Bitmap_set_iterator<A> it3(as3);
+    EXPECT_EQ(a_store[SET_SIZE - 1], it3++);
+    EXPECT_EQ((A*)NULL, it++);
+
+  }
+
+  TEST_F(Sql_set_test, iterator)
+  {
+    const Bitmap_set<A> x(1 | 4 | 16 | 32 | 128,   a_store, &A::map);
+
+    Bitmap_set_iterator<A> it(x);
+
+    EXPECT_EQ(a_store[0], it++);
+    EXPECT_EQ(a_store[2], it++);
+    EXPECT_EQ(a_store[4], it++);
+    EXPECT_EQ(a_store[5], it++);
+    EXPECT_EQ(a_store[7], it++);
+    EXPECT_EQ((A*)NULL, it++); 
+  }
+
+
+}


Attachment: [text/bzr-bundle] bzr/martin.hansson@oracle.com-20110113124809-mdn35tjkt4vyfky5.bundle
Thread
bzr commit into mysql-trunk-bugfixing branch (martin.hansson:3263) Martin Hansson13 Jan