Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx at d7d946a [master] Reimplement Array<Bool>.

susumu.yata null+****@clear*****
Fri Sep 5 11:34:18 JST 2014

• Previous message: [Groonga-commit] groonga/grnxx at 5c856c3 [master] Add tests for Array<Bool>.
• Next message: [Groonga-commit] droonga/droonga-engine at a0b785e [master] Call id in exist_user()
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2014-09-05 11:34:18 +0900 (Fri, 05 Sep 2014)

  New Revision: d7d946a09d74ed55b1605309c0d761004f99d9ca
  https://github.com/groonga/grnxx/commit/d7d946a09d74ed55b1605309c0d761004f99d9ca

  Message:
    Reimplement Array<Bool>.

  Added files:
    include/grnxx/array/bool.hpp
  Modified files:
    include/grnxx/array.hpp
    lib/grnxx/array.cpp

  Modified: include/grnxx/array.hpp (+2 -366)
===================================================================
--- include/grnxx/array.hpp    2014-09-05 11:30:58 +0900 (3749892)
+++ include/grnxx/array.hpp    2014-09-05 11:34:18 +0900 (b0b9ea8)
@@ -287,372 +287,6 @@ class Array {
   std::vector<Value> values_;
 };
 
-//class BoolReference {
-// public:
-//  BoolReference(uint64_t *block, uint64_t mask)
-//      : block_(block),
-//        mask_(mask) {}
-
-//  operator Bool() const {
-//    return (*block_ & mask_) != 0;
-//  }
-
-//  BoolReference operator=(Bool rhs) {
-//    if (rhs) {
-//      *block_ |= mask_;
-//    } else {
-//      *block_ &= ~mask_;
-//    }
-//    return *this;
-//  }
-//  BoolReference operator=(BoolReference rhs) {
-//    if (rhs) {
-//      *block_ |= mask_;
-//    } else {
-//      *block_ &= ~mask_;
-//    }
-//    return *this;
-//  }
-
-// private:
-//  uint64_t *block_;
-//  uint64_t mask_;
-//};
-
-//inline bool operator==(const BoolReference &lhs, Bool rhs) {
-//  return static_cast<Bool>(lhs) == rhs;
-//}
-
-//inline bool operator!=(const BoolReference &lhs, Bool rhs) {
-//  return static_cast<Bool>(lhs) != rhs;
-//}
-
-// ArrayCRef<Bool> is specialized because a bit does not have its own unique
-// address and thus a pointer type for Bool is not available.
-template <>
-class ArrayCRef<Bool> {
- public:
-  using Value = Bool;
-
-  ArrayCRef() = default;
-  ArrayCRef(const ArrayCRef &) = default;
-
-  ArrayCRef &operator=(const ArrayCRef &) = default;
-
-  bool operator==(ArrayCRef<Value> rhs) const {
-    return (blocks_ == rhs.blocks_) &&
-           (offset_ == rhs.offset_) &&
-           (size_ == rhs.size_);
-  }
-  bool operator!=(ArrayCRef<Value> rhs) const {
-    return (blocks_ != rhs.blocks_) ||
-           (offset_ != rhs.offset_) ||
-           (size_ != rhs.size_);
-  }
-
-  ArrayCRef ref(Int offset = 0) const {
-    return ArrayCRef(blocks_, offset + offset_, size() - offset);
-  }
-  ArrayCRef ref(Int offset, Int size) const {
-    return ArrayCRef(blocks_, offset + offset_, size);
-  }
-
-  Value get(Int i) const {
-    i += static_cast<Int>(offset_);
-    return (blocks_[i / 64] & (uint64_t(1) << (i % 64))) != 0;
-  }
-
-  Value operator[](Int i) const {
-    i += static_cast<Int>(offset_);
-    return (blocks_[i / 64] & (uint64_t(1) << (i % 64))) != 0;
-  }
-
-  // TODO: For optimization.
-//  const uint64_t *blocks() const {
-//    return blocks_;
-//  }
-//  Int offset() const {
-//    return static_cast<Int>(offset_);
-//  }
-
-  Int size() const {
-    return static_cast<Int>(size_);
-  }
-
- private:
-  const uint64_t *blocks_;
-  struct {
-    uint64_t offset_:16;
-    uint64_t size_:48;
-  };
-
-  ArrayCRef(const uint64_t *blocks, Int offset, Int size)
-      : blocks_(blocks + (offset / 64)),
-        offset_(static_cast<uint64_t>(offset % 64)),
-        size_(static_cast<uint64_t>(size)) {}
-
-  friend class ArrayRef<Value>;
-  friend class Array<Value>;
-};
-
-// ArrayRef<Bool> is specialized because a bit does not have its own unique
-// address and thus a pointer type for Bool is not available.
-template <>
-class ArrayRef<Bool> {
- public:
-  using Value = Bool;
-
-  ArrayRef() = default;
-  ArrayRef(const ArrayRef &) = default;
-
-  ArrayRef &operator=(const ArrayRef &) = default;
-
-
-  bool operator==(ArrayCRef<Value> rhs) const {
-    return (blocks_ == rhs.blocks_) &&
-           (offset_ == rhs.offset_) &&
-           (size_ == rhs.size_);
-  }
-  bool operator==(ArrayRef<Value> rhs) const {
-    return (blocks_ == rhs.blocks_) &&
-           (offset_ == rhs.offset_) &&
-           (size_ == rhs.size_);
-  }
-
-  bool operator!=(ArrayCRef<Value> rhs) const {
-    return (blocks_ != rhs.blocks_) ||
-           (offset_ != rhs.offset_) ||
-           (size_ != rhs.size_);
-  }
-  bool operator!=(ArrayRef<Value> rhs) const {
-    return (blocks_ == rhs.blocks_) ||
-           (offset_ == rhs.offset_) ||
-           (size_ == rhs.size_);
-  }
-
-  operator ArrayCRef<Value>() const {
-    return ref();
-  }
-
-  ArrayCRef<Value> ref(Int offset = 0) const {
-    return ArrayCRef<Value>(blocks_, offset + offset_, size() - offset);
-  }
-  ArrayCRef<Value> ref(Int offset, Int size) const {
-    return ArrayCRef<Value>(blocks_, offset + offset_, size);
-  }
-
-  ArrayRef ref(Int offset = 0) {
-    return ArrayRef(blocks_, offset + offset_, size() - offset);
-  }
-  ArrayRef ref(Int offset, Int size) {
-    return ArrayRef(blocks_, offset + offset_, size);
-  }
-
-  Value get(Int i) const {
-    i += static_cast<Int>(offset_);
-    return (blocks_[i / 64] & (uint64_t(1) << (i % 64))) != 0;
-  }
-  void set(Int i, Value value) {
-    i += static_cast<Int>(offset_);
-    if (value) {
-      blocks_[i / 64] |= uint64_t(1) << (i % 64);
-    } else {
-      blocks_[i / 64] &= ~(uint64_t(1) << (i % 64));
-    }
-  }
-
-//  BoolReference operator[](Int i) {
-//    i += static_cast<Int>(offset_);
-//    return BoolReference(&blocks_[i / 64], uint64_t(1) << (i % 64));
-//  }
-  Value operator[](Int i) const {
-    i += static_cast<Int>(offset_);
-    return (blocks_[i / 64] & (uint64_t(1) << (i % 64))) != 0;
-  }
-
-  // TODO: For optimization.
-//  uint64_t *blocks() const {
-//    return blocks_;
-//  }
-//  Int offset() const {
-//    return static_cast<Int>(offset_);
-//  }
-
-  Int size() const {
-    return static_cast<Int>(size_);
-  }
-
-  void swap(Int i, Int j) {
-    Bool temp = get(i);
-    set(i, get(j));
-    set(j, temp);
-  }
-
- private:
-  uint64_t *blocks_;
-  struct {
-    uint64_t offset_:16;
-    uint64_t size_:48;
-  };
-
-  ArrayRef(uint64_t *blocks, Int offset, Int size)
-      : blocks_(blocks + (offset / 64)),
-        offset_(static_cast<uint64_t>(offset % 64)),
-        size_(static_cast<uint64_t>(size)) {}
-
-  friend class Array<Value>;
-};
-
-// Array<Bool> is specialized because a bit does not have its own unique
-// address and thus a pointer type for Bool is not available.
-template <>
-class Array<Bool> {
- public:
-  using Value = Bool;
-
-  Array() : blocks_(), size_(0) {}
-  ~Array() {}
-
-  Array(Array &&array) : blocks_(std::move(array.blocks_)) {}
-
-  Array &operator=(Array &&array) {
-    blocks_ = std::move(array.blocks_);
-    return *this;
-  }
-
-  operator ArrayCRef<Value>() const {
-    return ref();
-  }
-  operator ArrayRef<Value>() {
-    return ref();
-  }
-
-  ArrayCRef<Value> ref(Int offset = 0) const {
-    return ArrayCRef<Value>(blocks_.data(), offset, size() - offset);
-  }
-  ArrayCRef<Value> ref(Int offset, Int size) const {
-    return ArrayCRef<Value>(blocks_.data(), offset, size);
-  }
-
-  ArrayRef<Value> ref(Int offset = 0) {
-    return ArrayRef<Value>(blocks_.data(), offset, size() - offset);
-  }
-  ArrayRef<Value> ref(Int offset, Int size) {
-    return ArrayRef<Value>(blocks_.data(), offset, size);
-  }
-
-  Value get(Int i) const {
-    return (blocks_[i / 64] & (uint64_t(1) << (i % 64))) != 0;
-  }
-  void set(Int i, Value value) {
-    if (value) {
-      blocks_[i / 64] |= uint64_t(1) << (i % 64);
-    } else {
-      blocks_[i / 64] &= ~(uint64_t(1) << (i % 64));
-    }
-  }
-
-//  BoolReference operator[](Int i) {
-//    return BoolReference(&blocks_[i / 64], uint64_t(1) << (i % 64));
-//  }
-  Value operator[](Int i) const {
-    return (blocks_[i / 64] & (uint64_t(1) << (i % 64))) != 0;
-  }
-
-//  BoolReference front() {
-//    return BoolReference(&blocks_[0], 1);
-//  }
-  Value front() const {
-    return (blocks_[0] & 1) != 0;
-  }
-
-//  BoolReference back() {
-//    return operator[](size_ - 1);
-//  }
-  Value back() const {
-    return operator[](size_ - 1);
-  }
-
-  // Instead of data().
-  uint64_t *blocks() {
-    return blocks_.data();
-  }
-  const uint64_t *blocks() const {
-    return blocks_.data();
-  }
-
-  Int size() const {
-    return size_;
-  }
-  Int capacity() const {
-    return blocks_.capacity() * 64;
-  }
-
-  bool reserve(Error *error, Int new_size) {
-    return blocks_.reserve(error, (new_size + 63) / 64);
-  }
-
-  bool resize(Error *error, Int new_size) {
-    if (!blocks_.resize(error, (new_size + 63) / 64)) {
-      return false;
-    }
-    size_ = new_size;
-    return true;
-  }
-  bool resize(Error *error, Int new_size, Value value) {
-    if (!blocks_.resize(error, (new_size + 63) / 64,
-                        value ? ~uint64_t(0) : uint64_t(0))) {
-      return false;
-    }
-    size_ = new_size;
-    return true;
-  }
-
-  bool shrink_to_fit(Error *error) {
-    return blocks_.shrink_to_fit(error);
-  }
-
-  void clear() {
-    blocks_.clear();
-    size_ = 0;
-  }
-
-//  void erase(Int i) {
-//    values_.erase(values_.begin() + i);
-//  }
-
-  bool push_back(Error *error, Value value) {
-    if ((size_ % 64) == 0) {
-      if (!blocks_.push_back(error, 0)) {
-        return false;
-      }
-    }
-    if (value) {
-      blocks_[size_ / 64] |= uint64_t(1) << (size_ % 64);
-    } else {
-      blocks_[size_ / 64] &= ~(uint64_t(1) << (size_ % 64));
-    }
-    ++size_;
-    return true;
-  }
-  void pop_back() {
-    if ((size_ % 64) == 1) {
-      blocks_.pop_back();
-    }
-    --size_;
-  }
-
-  void swap(Int i, Int j) {
-    Bool temp = get(i);
-    set(i, get(j));
-    set(j, temp);
-  }
-
- private:
-  Array<uint64_t> blocks_;
-  Int size_;
-};
-
 template <>
 class ArrayCRef<Record> {
  public:
@@ -921,4 +555,6 @@ class Array<Record> {
 
 }  // namespace grnxx
 
+#include "grnxx/array/bool.hpp"
+
 #endif  // GRNXX_ARRAY_HPP

  Added: include/grnxx/array/bool.hpp (+341 -0) 100644
===================================================================
--- /dev/null
+++ include/grnxx/array/bool.hpp    2014-09-05 11:34:18 +0900 (720f411)
@@ -0,0 +1,341 @@
+#ifndef GRNXX_ARRAY_BOOL_HPP
+#define GRNXX_ARRAY_BOOL_HPP
+
+#include "grnxx/types.hpp"
+
+namespace grnxx {
+
+// ArrayCRef<Bool> is specialized because each Bool value does not have its own
+// unique address and thus a pointer type for Bool is not available.
+template <>
+class ArrayCRef<Bool> {
+ public:
+  using Value = Bool;
+  using Block = uint64_t;
+
+  ArrayCRef() = default;
+  ArrayCRef(const ArrayCRef &) = default;
+
+  ArrayCRef &operator=(const ArrayCRef &) = default;
+
+  bool operator==(ArrayCRef<Value> rhs) const {
+    return (blocks_ == rhs.blocks_) &&
+           (offset_ == rhs.offset_) &&
+           (size_ == rhs.size_);
+  }
+  bool operator!=(ArrayCRef<Value> rhs) const {
+    return (blocks_ != rhs.blocks_) ||
+           (offset_ != rhs.offset_) ||
+           (size_ != rhs.size_);
+  }
+
+  ArrayCRef ref(Int offset = 0) const {
+    return ArrayCRef(blocks_, offset + offset_, size_ - offset);
+  }
+  ArrayCRef ref(Int offset, Int size) const {
+    return ArrayCRef(blocks_, offset + offset_, size);
+  }
+
+  Value get(Int i) const {
+    i += offset_;
+    return (blocks_[i / 64] & (Block(1) << (i % 64))) != 0;
+  }
+
+  Value operator[](Int i) const {
+    i += offset_;
+    return (blocks_[i / 64] & (Block(1) << (i % 64))) != 0;
+  }
+
+  Block get_block(Int i) const {
+    return blocks_[i];
+  }
+
+  Int offset() const {
+    return offset_;
+  }
+  Int size() const {
+    return size_;
+  }
+
+ private:
+  const Block *blocks_;
+  Int offset_;
+  Int size_;
+
+  ArrayCRef(const Block *blocks, Int offset, Int size)
+      : blocks_(blocks + (offset / 64)),
+        offset_(offset % 64),
+        size_(size) {}
+
+  friend class ArrayRef<Value>;
+  friend class Array<Value>;
+};
+
+// ArrayRef<Bool> is specialized because each Bool value does not have its own
+// unique address and thus a pointer type for Bool is not available.
+template <>
+class ArrayRef<Bool> {
+ public:
+  using Value = Bool;
+  using Block = uint64_t;
+
+  ArrayRef() = default;
+  ArrayRef(const ArrayRef &) = default;
+
+  ArrayRef &operator=(const ArrayRef &) = default;
+
+  bool operator==(ArrayCRef<Value> rhs) const {
+    return (blocks_ == rhs.blocks_) &&
+           (offset_ == rhs.offset_) &&
+           (size_ == rhs.size_);
+  }
+  bool operator==(ArrayRef<Value> rhs) const {
+    return (blocks_ == rhs.blocks_) &&
+           (offset_ == rhs.offset_) &&
+           (size_ == rhs.size_);
+  }
+
+  bool operator!=(ArrayCRef<Value> rhs) const {
+    return (blocks_ != rhs.blocks_) ||
+           (offset_ != rhs.offset_) ||
+           (size_ != rhs.size_);
+  }
+  bool operator!=(ArrayRef<Value> rhs) const {
+    return (blocks_ == rhs.blocks_) ||
+           (offset_ == rhs.offset_) ||
+           (size_ == rhs.size_);
+  }
+
+  operator ArrayCRef<Value>() const {
+    return ref();
+  }
+
+  ArrayCRef<Value> ref(Int offset = 0) const {
+    return ArrayCRef<Value>(blocks_, offset + offset_, size_ - offset);
+  }
+  ArrayCRef<Value> ref(Int offset, Int size) const {
+    return ArrayCRef<Value>(blocks_, offset + offset_, size);
+  }
+
+  ArrayRef ref(Int offset = 0) {
+    return ArrayRef(blocks_, offset + offset_, size_ - offset);
+  }
+  ArrayRef ref(Int offset, Int size) {
+    return ArrayRef(blocks_, offset + offset_, size);
+  }
+
+  Value get(Int i) const {
+    i += offset_;
+    return (blocks_[i / 64] & (Block(1) << (i % 64))) != 0;
+  }
+  void set(Int i, Value value) {
+    i += offset_;
+    if (value) {
+      blocks_[i / 64] |= Block(1) << (i % 64);
+    } else {
+      blocks_[i / 64] &= ~(Block(1) << (i % 64));
+    }
+  }
+
+  Value operator[](Int i) const {
+    i += offset_;
+    return (blocks_[i / 64] & (Block(1) << (i % 64))) != 0;
+  }
+
+  Block get_block(Int i) const {
+    return blocks_[i];
+  }
+  void set_block(Int i, Block block) {
+    blocks_[i] = block;
+  }
+
+  Int offset() const {
+    return offset_;
+  }
+  Int size() const {
+    return size_;
+  }
+
+  void swap(Int i, Int j) {
+    Value temp = get(i);
+    set(i, get(j));
+    set(j, temp);
+  }
+
+ private:
+  Block *blocks_;
+  Int offset_;
+  Int size_;
+
+  ArrayRef(Block *blocks, Int offset, Int size)
+      : blocks_(blocks + (offset / 64)),
+        offset_(offset % 64),
+        size_(size) {}
+
+  friend class Array<Value>;
+};
+
+// Array<Bool> is specialized because each Bool value does not have its own
+// unique address and thus a pointer type for Bool is not available.
+template <>
+class Array<Bool> {
+ public:
+  using Value = Bool;
+  using Block = uint64_t;
+
+  Array() : blocks_(), size_(0), capacity_(0) {}
+  ~Array() {}
+
+  Array(Array &&array)
+      : blocks_(std::move(array.blocks_)),
+        size_(array.size_),
+        capacity_(array.capacity_) {
+    array.size_ = 0;
+    array.capacity_ = 0;
+  }
+
+  Array &operator=(Array &&array) {
+    blocks_ = std::move(array.blocks_);
+    size_ = array.size_;
+    capacity_ = array.capacity_;
+    array.size_ = 0;
+    array.capacity_ = 0;
+    return *this;
+  }
+
+  operator ArrayCRef<Value>() const {
+    return ref();
+  }
+
+  ArrayCRef<Value> ref(Int offset = 0) const {
+    return ArrayCRef<Value>(blocks_.get(), offset, size_ - offset);
+  }
+  ArrayCRef<Value> ref(Int offset, Int size) const {
+    return ArrayCRef<Value>(blocks_.get(), offset, size);
+  }
+
+  ArrayRef<Value> ref(Int offset = 0) {
+    return ArrayRef<Value>(blocks_.get(), offset, size_ - offset);
+  }
+  ArrayRef<Value> ref(Int offset, Int size) {
+    return ArrayRef<Value>(blocks_.get(), offset, size);
+  }
+
+  Value get(Int i) const {
+    return (blocks_[i / 64] & (Block(1) << (i % 64))) != 0;
+  }
+  void set(Int i, Value value) {
+    if (value) {
+      blocks_[i / 64] |= Block(1) << (i % 64);
+    } else {
+      blocks_[i / 64] &= ~(Block(1) << (i % 64));
+    }
+  }
+
+  Value operator[](Int i) const {
+    return (blocks_[i / 64] & (Block(1) << (i % 64))) != 0;
+  }
+
+  Block get_block(Int i) const {
+    return blocks_[i];
+  }
+  void set_block(Int i, Block block) {
+    blocks_[i] = block;
+  }
+
+  Value front() const {
+    return (blocks_[0] & 1) != 0;
+  }
+  Value back() const {
+    return get(size_ - 1);
+  }
+
+  Int size() const {
+    return size_;
+  }
+  Int capacity() const {
+    return capacity_;
+  }
+
+  bool reserve(Error *error, Int new_size) {
+    if (new_size <= capacity_) {
+      return true;
+    }
+    return resize_blocks(error, new_size);
+  }
+
+  bool resize(Error *error, Int new_size) {
+    if (new_size <= capacity_) {
+      size_ = new_size;
+      return true;
+    }
+    if (!resize_blocks(error, new_size)) {
+      return false;
+    }
+    size_ = new_size;
+    return true;
+  }
+  bool resize(Error *error, Int new_size, Value value) {
+    if (new_size <= capacity_) {
+      size_ = new_size;
+      return true;
+    }
+    if (!resize_blocks(error, new_size)) {
+      return false;
+    }
+    if ((size_ % 64) != 0) {
+      if (value) {
+        blocks_[size_ / 64] |= ~Block(0) << (size_ % 64);
+      } else {
+        blocks_[size_ / 64] &= ~(~Block(0) << (size_ % 64));
+      }
+      size_ = (size_ + 63) & ~Int(63);
+    }
+    Block block = value ? ~Block(0) : Block(0);
+    for (Int i = size_; i < new_size; i += 64) {
+      blocks_[i / 64] = block;
+    }
+    size_ = new_size;
+    return true;
+  }
+
+  void clear() {
+    size_ = 0;
+  }
+
+  bool push_back(Error *error, Value value) {
+    if (size_ == capacity_) {
+      if (!resize_blocks(error, size_ + 1)) {
+        return false;
+      }
+    }
+    if (value) {
+      blocks_[size_ / 64] |= Block(1) << (size_ % 64);
+    } else {
+      blocks_[size_ / 64] &= ~(Block(1) << (size_ % 64));
+    }
+    ++size_;
+    return true;
+  }
+  void pop_back() {
+    --size_;
+  }
+
+  void swap(Int i, Int j) {
+    Value temp = get(i);
+    set(i, get(j));
+    set(j, temp);
+  }
+
+ private:
+  unique_ptr<Block[]> blocks_;
+  Int size_;
+  Int capacity_;
+
+  // Assume new_size > capacity_.
+  bool resize_blocks(Error *error, Int new_size);
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_ARRAY_HPP

  Modified: lib/grnxx/array.cpp (+19 -0)
===================================================================
--- lib/grnxx/array.cpp    2014-09-05 11:30:58 +0900 (cc2fd79)
+++ lib/grnxx/array.cpp    2014-09-05 11:34:18 +0900 (0e34845)
@@ -8,4 +8,23 @@ void ArrayErrorReporter::report_memory_error(Error *error) {
   GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed");
 }
 
+bool Array<Bool>::resize_blocks(Error *error, Int new_size) {
+  Int new_capacity = capacity_ * 2;
+  if (new_size > new_capacity) {
+    new_capacity = (new_size + 63) & ~Int(63);
+  }
+  unique_ptr<Block[]> new_blocks(new (nothrow) Block[new_capacity / 64]);
+  if (!new_blocks) {
+    GRNXX_ERROR_SET(error, NO_MEMORY, "Memory allocation failed");
+    return false;
+  }
+  Int num_valid_blocks = (size_ + 63) / 64;
+  for (Int i = 0; i < num_valid_blocks; ++i) {
+    new_blocks[i] = blocks_[i];
+  }
+  blocks_ = std::move(new_blocks);
+  capacity_ = new_capacity;
+  return true;
+}
+
 }  // namespace grnxx
-------------- next part --------------
HTML����������������������������...
Download 

• Previous message: [Groonga-commit] groonga/grnxx at 5c856c3 [master] Add tests for Array<Bool>.
• Next message: [Groonga-commit] droonga/droonga-engine at a0b785e [master] Call id in exist_user()
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]