summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--CodingReadme8
-rw-r--r--kernel/hashlib.h87
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<T>. 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<K, T> and pool<T> 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<K, T> &operator*() { return ptr->entries[index].udata; }
- std::pair<K, T> *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<K, T> &operator*() const { return ptr->entries[index].udata; }
const std::pair<K, T> *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<K, T> &operator*() { return ptr->entries[index].udata; }
+ std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
const std::pair<K, T> *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<typename K, typename OPS = hash_ops<K>>
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);