From 1e08621e7e2c219169b3b6c5fe1d581052e4d429 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Wed, 31 Dec 2014 14:52:46 +0100 Subject: Added hashlib .count(key, iterator) and it1 < it2 --- CodingReadme | 8 +++++- kernel/hashlib.h | 87 ++++++++++++++++++++++++++++++++------------------------ 2 files changed, 57 insertions(+), 38 deletions(-) diff --git a/CodingReadme b/CodingReadme index 2349b2ee..92d54d28 100644 --- a/CodingReadme +++ b/CodingReadme @@ -63,8 +63,14 @@ replacement for std::unordered_set. The main characteristics are: begin(). i.e. only a new iterator that starts at begin() will see the inserted elements. + - the method .count(key, iterator) is like .count(key) but only + considers elements that can be reached via the iterator. + + - iterators can be compared. it1 < it2 means that the position of t2 + can be reached via t1 but not vice versa. + - dict and pool will have the same order of iteration across - all compilers and architectures. + all compilers, standard libraries and architectures. 2. Standard STL data types diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 29f4f68b..5e00e89d 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -287,38 +287,41 @@ class dict } public: - class iterator + class const_iterator { friend class dict; protected: - dict *ptr; + const dict *ptr; int index; + const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { } public: - iterator() { } - iterator(dict *ptr, int index) : ptr(ptr), index(index) { } - iterator operator++() { index--; return *this; } - bool operator==(const iterator &other) const { return index == other.index; } - bool operator!=(const iterator &other) const { return index != other.index; } - std::pair &operator*() { return ptr->entries[index].udata; } - std::pair *operator->() { return &ptr->entries[index].udata; } + const_iterator() { } + const_iterator operator++() { index--; return *this; } + bool operator<(const const_iterator &other) const { return index > other.index; } + bool operator==(const const_iterator &other) const { return index == other.index; } + bool operator!=(const const_iterator &other) const { return index != other.index; } const std::pair &operator*() const { return ptr->entries[index].udata; } const std::pair *operator->() const { return &ptr->entries[index].udata; } }; - class const_iterator + class iterator { friend class dict; protected: - const dict *ptr; + dict *ptr; int index; + iterator(dict *ptr, int index) : ptr(ptr), index(index) { } public: - const_iterator() { } - const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { } - const_iterator operator++() { index--; return *this; } - bool operator==(const const_iterator &other) const { return index == other.index; } - bool operator!=(const const_iterator &other) const { return index != other.index; } + iterator() { } + iterator operator++() { index--; return *this; } + bool operator<(const iterator &other) const { return index > other.index; } + bool operator==(const iterator &other) const { return index == other.index; } + bool operator!=(const iterator &other) const { return index != other.index; } + std::pair &operator*() { return ptr->entries[index].udata; } + std::pair *operator->() { return &ptr->entries[index].udata; } const std::pair &operator*() const { return ptr->entries[index].udata; } const std::pair *operator->() const { return &ptr->entries[index].udata; } + operator const_iterator() const { return const_iterator(ptr, index); } }; dict() @@ -398,6 +401,13 @@ public: return i < 0 ? 0 : 1; } + int count(const K &key, const_iterator it) const + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + return i < 0 || i > it.index ? 0 : 1; + } + iterator find(const K &key) { int hash = do_hash(key); @@ -475,13 +485,6 @@ public: const_iterator end() const { return const_iterator(nullptr, -1); } }; -// ******************************************************************************** -// ******************************************************************************** -// ******************************************************************************** -// ******************************************************************************** -// ******************************************************************************** - - template> class pool { @@ -606,36 +609,39 @@ class pool } public: - class iterator + class const_iterator { friend class pool; protected: - pool *ptr; + const pool *ptr; int index; + const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { } public: - iterator() { } - iterator(pool *ptr, int index) : ptr(ptr), index(index) { } - iterator operator++() { index--; return *this; } - bool operator==(const iterator &other) const { return index == other.index; } - bool operator!=(const iterator &other) const { return index != other.index; } + const_iterator() { } + const_iterator operator++() { index--; return *this; } + bool operator==(const const_iterator &other) const { return index == other.index; } + bool operator!=(const const_iterator &other) const { return index != other.index; } const K &operator*() const { return ptr->entries[index].udata; } const K *operator->() const { return &ptr->entries[index].udata; } }; - class const_iterator + class iterator { friend class pool; protected: - const pool *ptr; + pool *ptr; int index; + iterator(pool *ptr, int index) : ptr(ptr), index(index) { } public: - const_iterator() { } - const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { } - const_iterator operator++() { index--; return *this; } - bool operator==(const const_iterator &other) const { return index == other.index; } - bool operator!=(const const_iterator &other) const { return index != other.index; } + iterator() { } + iterator operator++() { index--; return *this; } + bool operator==(const iterator &other) const { return index == other.index; } + bool operator!=(const iterator &other) const { return index != other.index; } + K &operator*() { return ptr->entries[index].udata; } + K *operator->() { return &ptr->entries[index].udata; } const K &operator*() const { return ptr->entries[index].udata; } const K *operator->() const { return &ptr->entries[index].udata; } + operator const_iterator() const { return const_iterator(ptr, index); } }; pool() @@ -715,6 +721,13 @@ public: return i < 0 ? 0 : 1; } + int count(const K &key, const_iterator it) const + { + int hash = do_hash(key); + int i = do_lookup(key, hash); + return i < 0 || i > it.index ? 0 : 1; + } + iterator find(const K &key) { int hash = do_hash(key); -- cgit v1.2.3