ndb - Test program for new bitmask functions

ndb/include/util/Bitmask.hpp:
  Add general set/getField
ndb/src/common/util/Bitmask.cpp:
  Test program for bitmask
ndb/src/common/util/Makefile.am:
  Test program for bitmask

3 files changed, 229 insertions, 5 deletions

diff --git a/ndb/include/util/Bitmask.hpp b/ndb/include/util/Bitmask.hpp
index 6d932cac7c5..b6bc6e3d5e3 100644
--- a/ndb/include/util/Bitmask.hpp
+++ b/ndb/include/util/Bitmask.hpp
@@ -148,6 +148,9 @@ public:
    * getText - Return as hex-digits (only for debug routines).
    */
   static char* getText(unsigned size, const Uint32 data[], char* buf);
+private:
+  static void getFieldImpl(const Uint32 data[], unsigned, unsigned, Uint32 []);
+  static void setFieldImpl(Uint32 data[], unsigned, unsigned, const Uint32 []);
 };
 
 inline bool
@@ -820,7 +823,7 @@ BitmaskImpl::getField(unsigned size, const Uint32 data[],
     dst[0] = (data[word] >> offset) & ((1 << len) - 1);
     return;
   }
-  abort();
+  getFieldImpl(data, pos, len, dst);
 }
 
 inline void
@@ -831,13 +834,13 @@ BitmaskImpl::setField(unsigned size, Uint32 data[],
   assert(pos + len < (size << 5));
   Uint32 word = pos >> 5;
   Uint32 offset = pos & 31;
+  Uint32 mask = ((1 << len) - 1) << offset;
+  data[word] = (data[word] & ~mask) | ((src[0] << offset) & mask);
   if(offset + len <= 32)
   {
-    Uint32 mask = ((1 << len) - 1) << offset;
-    data[word] = (data[word] & ~mask) | ((src[0] << offset) & mask);
     return;
   }
-  abort();
+  setFieldImpl(data, pos, len, src);
 }
 
 
diff --git a/ndb/src/common/util/Bitmask.cpp b/ndb/src/common/util/Bitmask.cpp
new file mode 100644
index 00000000000..536620ce305
--- /dev/null
+++ b/ndb/src/common/util/Bitmask.cpp
@@ -0,0 +1,204 @@
+#include <Bitmask.hpp>
+#include <NdbOut.hpp>
+
+#ifndef __TEST_BITMASK__
+void
+BitmaskImpl::getFieldImpl(const Uint32 data[],
+			  unsigned pos, unsigned l, Uint32 dst[])
+{
+  Uint32 word;
+  Uint32 offset;
+  int next_offset,i;
+  int len= l;
+  for(i=0,next_offset=0;len >0;i++)
+  {
+    word = pos >> 5;
+    offset = pos & 31;
+
+    if(i%32==0)
+      dst[i/32]=0;
+
+    if(!next_offset && (offset+len) > 32)
+    {
+      dst[i/32] = (data[word] >> offset) & ((1 << (32-offset)) - 1);
+      next_offset = 32-offset;
+    }
+    else
+    {
+      dst[i/32]|= ((data[word] >> offset) & ((1 << len) - 1)) << next_offset;
+      next_offset = 0;
+    }
+    
+    if(len < 32-offset)
+      break;
+    
+    len-=32-offset;
+    pos+=32-offset;
+  }
+}
+ 
+void
+BitmaskImpl::setFieldImpl(Uint32 data[],
+			  unsigned pos, unsigned l, const Uint32 src[])
+{
+  Uint32 word;
+  Uint32 offset;
+  Uint32 mask;
+  int i=0,stored=0;
+  int len= l;
+
+  while(len>0)
+  {
+    ndbout_c("len: %d", len);
+    word = pos >> 5;
+    offset = pos & 31;
+    
+    if(offset+len > 32)
+      stored = 32-offset;
+    else
+      stored = len;
+    
+    mask = ((1 << stored) - 1) << (i+offset)%32;
+    data[word] = (data[word] & ~mask) | ((src[i/32] << (i+offset)%32) & mask);
+    
+    i+=stored;
+    len-=32-offset;
+    pos+=32-offset;
+  }
+}
+
+#else
+
+#define DEBUG 0
+#include <Vector.hpp>
+void do_test(int bitmask_size);
+
+int
+main(int argc, char** argv)
+{
+  int loops = argc > 1 ? atoi(argv[1]) : 1000;
+  int max_size = argc > 2 ? atoi(argv[2]) : 1000;
+
+  
+  for(int i = 0; i<loops; i++)
+    do_test(1 + (rand() % max_size));
+}
+
+struct Alloc
+{
+  Uint32 pos;
+  Uint32 size;
+  Vector<Uint32> data;
+};
+
+void require(bool b)
+{
+  if(!b) abort();
+}
+
+void 
+do_test(int bitmask_size)
+{
+  Vector<Alloc> alloc_list;
+  bitmask_size = (bitmask_size + 31) & ~31;
+  Uint32 sz32 = (bitmask_size >> 5);
+  Vector<Uint32> alloc_mask;
+  Vector<Uint32> test_mask;
+  Vector<Uint32> tmp;
+  
+  ndbout_c("Testing bitmask of size %d", bitmask_size);
+  Uint32 zero = 0;
+  alloc_mask.fill(sz32, zero);
+  test_mask.fill(sz32, zero);
+  tmp.fill(sz32, zero);
+  
+  for(int i = 0; i<1000; i++)
+  {
+    int pos = rand() % (bitmask_size - 1);
+    int free = 0;
+    if(BitmaskImpl::get(sz32, alloc_mask.getBase(), pos))
+    {
+      // Bit was allocated
+      // 1) Look up allocation
+      // 2) Check data
+      // 3) free it
+      size_t j;
+      int min, max;
+      for(j = 0; j<alloc_list.size(); j++)
+      {
+	min = alloc_list[j].pos;
+	max = min + alloc_list[j].size;
+	if(pos >= min && pos < max)
+	{
+	  break;
+	}
+      }
+      if(DEBUG)
+	ndbout_c("freeing [ %d %d ]", min, max);
+
+      require(pos >= min && pos < max);
+      BitmaskImpl::getField(sz32, test_mask.getBase(), min, max-min, 
+			    tmp.getBase());
+      if(memcmp(tmp.getBase(), alloc_list[j].data.getBase(),
+		((max - min) + 31) >> 5) != 0)
+      {
+	printf("mask: ");
+	size_t k;
+	Alloc& a = alloc_list[j];
+	for(k = 0; k<a.data.size(); k++)
+	  printf("%.8x ", a.data[k]);
+	printf("\n");
+
+	printf("field: ");
+	for(k = 0; k<(((max - min)+31)>>5); k++)
+	  printf("%.8x ", tmp.getBase()[k]);
+	printf("\n");
+	abort();
+      }
+      while(min < max)
+	BitmaskImpl::clear(sz32, alloc_mask.getBase(), min++);
+      alloc_list.erase(j);
+    }
+    else
+    {
+      // Bit was free
+      // 1) Check how much space is avaiable
+      // 2) Create new allocation of random size
+      // 3) Fill data with random data
+      // 4) Update alloc mask
+      while(pos+free < bitmask_size && 
+	    !BitmaskImpl::get(sz32, alloc_mask.getBase(), pos+free))
+	free++;
+
+      Uint32 sz = (rand() % free); sz = sz ? sz : 1;
+      Alloc a;
+      a.pos = pos;
+      a.size = sz;
+      a.data.fill(sz >> 5, zero);
+      if(DEBUG)
+	ndbout_c("pos %d -> alloc [ %d %d ]", pos, pos, pos+sz);
+      for(size_t j = 0; j<sz; j++)
+      {
+	BitmaskImpl::set(sz32, alloc_mask.getBase(), pos+j);
+	if((rand() % 1000) > 500)
+	  BitmaskImpl::set((sz + 31) >> 5, a.data.getBase(), j);
+      }
+      if(DEBUG)
+      {
+	printf("mask: ");
+	size_t k;
+	for(k = 0; k<a.data.size(); k++)
+	  printf("%.8x ", a.data[k]);
+	printf("\n");
+      }
+      BitmaskImpl::setField(sz32, test_mask.getBase(), pos, sz, 
+			    a.data.getBase());
+      alloc_list.push_back(a);
+    }
+  }
+}
+
+template class Vector<Alloc>;
+template class Vector<Uint32>;
+
+#endif
diff --git a/ndb/src/common/util/Makefile.am b/ndb/src/common/util/Makefile.am
index 61fd7992002..1f62ca0d9d5 100644
--- a/ndb/src/common/util/Makefile.am
+++ b/ndb/src/common/util/Makefile.am
@@ -9,7 +9,24 @@ libgeneral_la_SOURCES = \
 	    NdbSqlUtil.cpp new.cpp \
             uucode.c random.c version.c \
             strdup.c \
-            ConfigValues.cpp ndb_init.c basestring_vsnprintf.c
+            ConfigValues.cpp ndb_init.c basestring_vsnprintf.c \
+            Bitmask.cpp
+
+EXTRA_PROGRAMS = testBitmask
+testBitmask_SOURCES =  testBitmask.cpp
+testBitmask_LDFLAGS = @ndb_bin_am_ldflags@ \
+  $(top_builddir)/ndb/src/libndbclient.la \
+         $(top_builddir)/dbug/libdbug.a \
+         $(top_builddir)/mysys/libmysys.a \
+         $(top_builddir)/strings/libmystrings.a
+
+testBitmask.cpp : Bitmask.cpp
+	rm -f testBitmask.cpp
+	@LN_CP_F@ Bitmask.cpp testBitmask.cpp
+
+testBitmask.o:	$(testBitmask_SOURCES)
+		$(CXXCOMPILE) -c $(INCLUDES) -D__TEST_BITMASK__ $<
+
 
 include $(top_srcdir)/ndb/config/common.mk.am
 include $(top_srcdir)/ndb/config/type_util.mk.am