bzr commit into mysql-5.1-telco-7.0 branch (magnus.blaudd:2878)

[Magnus Blåudd]

#At file:///home/msvensson/mysql/bug44488/ based on revid:magnus.blaudd@stripped326jsst302lygx3

 2878 Magnus Blåudd	2009-05-13
      ndb - HashMap 
       - Hash container for storing key value pairs
       - Add HashMap-t unit test
       - Add get_key function to BaseString to be used when
         BaseString is used as key in HashMap
       - Add convinience macro to NdbTap.hpp for checking requirements

    added:
      storage/ndb/include/util/HashMap.hpp
      storage/ndb/src/common/util/HashMap.cpp
    modified:
      storage/ndb/include/util/BaseString.hpp
      storage/ndb/include/util/NdbTap.hpp
      storage/ndb/src/common/util/Makefile.am
=== modified file 'storage/ndb/include/util/BaseString.hpp'
--- a/storage/ndb/include/util/BaseString.hpp	2009-01-30 15:08:46 +0000
+++ b/storage/ndb/include/util/BaseString.hpp	2009-05-13 09:06:43 +0000
@@ -188,6 +188,17 @@ public:
   static int snprintf(char *str, size_t size, const char *format, ...)
     ATTRIBUTE_FORMAT(printf, 3, 4);
   static int vsnprintf(char *str, size_t size, const char *format, va_list ap);
+
+  /**
+   * Return pointer and length for key to use when BaseString is
+   * used as Key in HashMap
+   */
+  static const void* get_key(const void* key, size_t* key_length) {
+    const BaseString* str = (const BaseString*)key;
+    *key_length = str->length();
+    return str->c_str();
+  }
+
 private:
   char* m_chr;
   unsigned m_len;

=== added file 'storage/ndb/include/util/HashMap.hpp'
--- a/storage/ndb/include/util/HashMap.hpp	1970-01-01 00:00:00 +0000
+++ b/storage/ndb/include/util/HashMap.hpp	2009-05-13 09:06:43 +0000
@@ -0,0 +1,159 @@
+/* Copyright (C) 2009 Sun Microsystems Inc.
+
+   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 */
+
+
+#ifndef NDB_HASHMAP_HPP
+#define NDB_HASHMAP_HPP
+
+#include <ndb_global.h>
+#include <my_sys.h>
+#include <hash.h>
+
+
+/*
+  Default implementation for extracting key_ptr and
+  key_length from type K. Used when the entire type
+  K should be used as key.
+
+  NOTE! Optimized inside HashMap so that it's never
+  actually called
+*/
+
+inline const void* HashMap__get_key(const void* key_ptr, size_t* key_length)
+{
+  key_length = key_length;
+  return key_ptr;

+}
+
+
+/*
+  Hash container for storing key value pairs
+*/
+
+template<typename K, typename T,
+         const void* G(const void*, size_t*) = HashMap__get_key >
+class HashMap {
+  class Entry {
+  public:
+    K m_key;
+    T m_value;
+    Entry(const K& k, const T& v) : m_key(k), m_value(v) {};
+  };
+
+  HASH m_hash;
+
+  static void free_element(void * ptr) {
+    Entry* entry = (Entry*)ptr;
+    delete entry;
+  }
+
+  /*
+    Callback function which is installed into 'my_hash'
+    and thus called once for each key in the hash that need to
+    be compared. Should return a pointer to where the key
+    start and the key's length.
+  */
+  static uchar* _get_key(const uchar* ptr,
+                         size_t* key_length, my_bool first) {
+    Entry* entry = (Entry*)ptr;
+    const void* key_ptr = G((const void*)&entry->m_key, key_length);
+    return (uchar*)key_ptr;
+  }
+
+  const void* get_key_ptr(const K* key, size_t *key_length) const {
+    if (G == HashMap__get_key)
+      return key;
+    return _get_key((const uchar*)key, key_length, false);
+  }
+
+public:
+  HashMap(ulong initial_size = 1024, uint grow_size = 256) {
+
+    assert(my_init_done);
+
+    if (my_hash_init2(&m_hash,
+                      grow_size,
+                      &my_charset_bin, // charset
+                      initial_size,    // default_array_elements
+                      0,               // key_offset
+                      sizeof(K),       // key_length
+                      G == HashMap__get_key ? NULL : _get_key, // get_key,
+                      free_element,    // free_element
+                      HASH_UNIQUE      // flags
+                      ))
+      abort();
+  }
+
+  ~HashMap() {
+    my_hash_free(&m_hash);
+  }
+
+  bool insert(const K& k, const T& v, bool replace = false) {
+    Entry* entry = new Entry(k, v);
+    if (my_hash_insert(&m_hash, (const uchar*)entry) != 0) {
+      // An entry already existed
+
+      delete entry;
+
+      T* p;
+      if (replace && search(k, &p)) {
+        *p = v;
+        return true;
+      }
+      return false;
+    }
+    return true;

+  }
+
+  bool search(const K& k, T& v) const {
+    T* p;
+    if (!search(k, &p))
+      return false;
+    v = *p;
+    return true;
+  }
+
+  bool search(const K& k, T** v) const {
+    size_t key_length = sizeof(K);
+    const void *key = get_key_ptr(&k, &key_length);
+    Entry* entry= (Entry*)my_hash_search(&m_hash,
+                                         (const uchar*)key, key_length);
+    if (entry == NULL)
+      return false;
+
+    *v = &(entry->m_value);
+    return true;
+  }
+
+  bool remove(const K& k) {
+    size_t key_length = sizeof(K);
+    const void *key = get_key_ptr(&k, &key_length);
+    Entry* entry= (Entry*)my_hash_search(&m_hash,
+                                         (const uchar*)key, key_length);
+    if (entry == NULL)
+      return false;
+
+    if (my_hash_delete(&m_hash, (uchar*)entry))
+      return false;
+    return true;
+  }
+
+  size_t entries(void) const {
+    return m_hash.records;
+  }
+
+};
+
+#endif

=== modified file 'storage/ndb/include/util/NdbTap.hpp'
--- a/storage/ndb/include/util/NdbTap.hpp	2008-11-20 16:36:23 +0000
+++ b/storage/ndb/include/util/NdbTap.hpp	2009-05-13 09:06:43 +0000
@@ -19,6 +19,12 @@
 #include <../../../unittest/mytap/tap.h>
 #include <../../../unittest/mytap/tap.c>
 
+#ifdef VM_TRACE
+#define OK(b) assert(b);
+#else
+#define OK(b) if (!(b)) abort();
+#endif
+
 #define TAPTEST(name)                           \
 int name##_test();                              \
 int main(int argc, const char** argv){          \

=== added file 'storage/ndb/src/common/util/HashMap.cpp'
--- a/storage/ndb/src/common/util/HashMap.cpp	1970-01-01 00:00:00 +0000
+++ b/storage/ndb/src/common/util/HashMap.cpp	2009-05-13 09:06:43 +0000
@@ -0,0 +1,138 @@
+/* Copyright (C) 2009 Sun Microsystems Inc.
+
+   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 */
+
+#include <HashMap.hpp>
+
+#ifdef TEST_HASH
+
+#include <BaseString.hpp>
+#include <NdbTap.hpp>
+
+struct NodePair { Uint32 node1; Uint32 node2; };
+
+TAPTEST(HashMap)
+{
+
+  OK(my_init() == 0); // Init mysys
+
+  printf("int -> int\n");
+  {
+    HashMap<int, int> hash1;
+    for (int i= 0; i < 100; i++)
+      OK(hash1.insert(i, i*34));
+
+    int int_val;
+    for (int i= 0; i < 100; i++)
+    {
+      OK(hash1.search(i, int_val));
+      OK(int_val == i*34);
+
+      OK(!hash1.search(i+100, int_val));
+    }
+
+    // Duplicate key insert disallowed
+    OK(!hash1.insert(32, 32));
+
+    // Value should not have changed
+    OK(hash1.search(32, int_val));
+    OK(int_val == 32*34);
+
+    // Duplicate key insert with replace flag
+    OK(hash1.insert(32, 37, true));
+
+    // Value should now have changed
+    OK(hash1.search(32, int_val));
+    OK(int_val == 37);
+
+  }
+
+  printf("int -> BaseString\n");
+  {
+    HashMap<int, BaseString> hash2;
+
+    // Insert value with key 32
+    BaseString str1("hej");
+    OK(hash2.insert(32, str1));
+
+    // Retrieve value with key 32 and check it's the same
+    BaseString str2;
+    OK(hash2.search(32, str2));
+    OK(str1 == str2);
+
+    // no value with key 33 inserted
+    OK(!hash2.search(33, str2));
+
+    for (int i= 100; i < 200; i++){
+      BaseString str;
+      str.assfmt("magnus%d", i);
+      OK(hash2.insert(i, str));
+    }
+
+    for (int i= 100; i < 200; i++){
+      BaseString str;
+      OK(hash2.search(i, str));
+    }
+
+    // Delete every second entry
+    for (int i= 100; i < 200; i+=2)
+      OK(hash2.remove(i));
+
+    BaseString str3;
+    OK(!hash2.search(102, str3));
+    OK(hash2.search(103, str3));
+  }
+
+  printf("struct NodePair -> Uint32\n");
+  {
+    HashMap<NodePair, Uint32> lookup;
+    NodePair pk;
+    pk.node1 = 1;
+    pk.node2 = 2;
+    OK(lookup.insert(pk, 37));
+
+    // Duplicate insert
+    OK(!lookup.insert(pk, 38));
+
+    Uint32 value;
+    OK(lookup.search(pk, value));
+    OK(value == 37);
+  }
+
+  printf("BaseString -> int\n");
+  {
+    HashMap<BaseString, int, BaseString::get_key > string_hash;
+    OK(string_hash.insert("magnus", 1));
+    OK(string_hash.insert("mas", 2));
+    int value;
+    OK(string_hash.search("mas", value));
+    OK(value == 2);
+
+    OK(string_hash.entries() == 2);
+
+    // Remove entry
+    OK(string_hash.remove("mas"));
+
+    // Check it does not exist
+    OK(!string_hash.search("mas", value));
+
+    OK(string_hash.entries() == 1);
+  }
+
+  my_end(0); // Bye mysys
+
+  return 1; // OK
+}
+
+#endif

=== modified file 'storage/ndb/src/common/util/Makefile.am'
--- a/storage/ndb/src/common/util/Makefile.am	2008-11-20 16:42:18 +0000
+++ b/storage/ndb/src/common/util/Makefile.am	2009-05-13 09:06:43 +0000
@@ -35,7 +35,7 @@ INCLUDES_LOC = @ZLIB_INCLUDES@
 libndbazio_la_SOURCES = azio.c
 libndbazio_la_LIBADD = @ZLIB_LIBS@
 
-noinst_PROGRAMS = BaseString-t
+noinst_PROGRAMS = BaseString-t HashMap-t
 
 BaseString_t_SOURCES = BaseString.cpp
 BaseString_t_CXXFLAGS = -DTEST_BASE_STRING
@@ -43,5 +43,14 @@ BaseString_t_LDADD = \
 	libgeneral.la \
 	$(top_builddir)/mysys/libmysyslt.la
 
+HashMap_t_SOURCES = HashMap.cpp
+HashMap_t_CXXFLAGS = -DTEST_HASH
+HashMap_t_LDADD = \
+	libgeneral.la \
+	$(top_builddir)/mysys/libmysyslt.la \
+	$(top_builddir)/dbug/libdbuglt.la \
+	$(top_builddir)/strings/libmystringslt.la
+
+
 include $(top_srcdir)/storage/ndb/config/common.mk.am
 include $(top_srcdir)/storage/ndb/config/type_util.mk.am

Attachment: [text/bzr-bundle] bzr/[e-mail]