// license:GPL-2.0+ // copyright-holders:Couriersud /* * plists.h * */ #pragma once #ifndef PLISTS_H_ #define PLISTS_H_ #include #include #include #include #include #include "palloc.h" #include "pstring.h" PLIB_NAMESPACE_START() // ---------------------------------------------------------------------------------------- // parray_t: dynamic array // ---------------------------------------------------------------------------------------- template class array_t { public: ATTR_COLD array_t(std::size_t numElements) : m_list(0), m_capacity(0) { set_capacity(numElements); } ATTR_COLD array_t(const array_t &rhs) : m_list(0), m_capacity(0) { set_capacity(rhs.size()); for (std::size_t i=0; i 0) m_list = palloc_array(new_capacity); else m_list = nullptr; m_capacity = new_capacity; } private: LC * m_list; int m_capacity; }; // ---------------------------------------------------------------------------------------- // plist_t: a simple list // ---------------------------------------------------------------------------------------- template class pvector_t : public std::vector { public: pvector_t() : std::vector() {} void clear_and_free() { for (LC i : *this) { pfree(i); } this->clear(); } bool contains(const LC &elem) const { return (std::find(this->begin(), this->end(), elem) != this->end()); } void remove(const LC &elem) { this->erase(std::remove(this->begin(), this->end(), elem), this->end()); } ATTR_HOT void insert_at(const std::size_t index, const LC &elem) { this->insert(this->begin() + index, elem); } ATTR_HOT void remove_at(const std::size_t pos) { this->erase(this->begin() + pos); } int indexof(const LC &elem) const { for (unsigned i = 0; i < this->size(); i++) { if (this->at(i) == elem) return i; } return -1; } }; // ---------------------------------------------------------------------------------------- // plinkedlist_t: a simple linked list // the list allows insertions / deletions if used properly // ---------------------------------------------------------------------------------------- template class linkedlist_t; #if 1 template struct plinkedlist_element_t { public: friend class linkedlist_t; plinkedlist_element_t() : m_next(nullptr) {} LC *next() const { return m_next; } //private: LC * m_next; }; template class linkedlist_t { public: linkedlist_t() : m_head(nullptr) {} #if 0 ATTR_HOT void insert(const LC &before, LC &elem) { if (m_head == &before) { elem.m_next = m_head; m_head = &elem; } else { LC *p = m_head; while (p != nullptr) { if (p->m_next == &before) { elem->m_next = &before; p->m_next = &elem; return; } p = p->m_next; } //throw pexception("element not found"); } } #endif ATTR_HOT void insert(LC &elem) { elem.m_next = m_head; m_head = &elem; } ATTR_HOT void add(LC &elem) { LC **p = &m_head; while (*p != nullptr) { p = &((*p)->m_next); } *p = &elem; elem.m_next = nullptr; } ATTR_HOT void remove(const LC &elem) { LC **p; for (p = &m_head; *p != &elem; p = &((*p)->m_next)) { //nl_assert(*p != nullptr); } (*p) = elem.m_next; } ATTR_HOT LC *first() const { return m_head; } ATTR_HOT void clear() { m_head = nullptr; } ATTR_HOT bool is_empty() const { return (m_head == nullptr); } //private: LC *m_head; }; #else template struct plinkedlist_element_t { public: friend class linkedlist_t; plinkedlist_element_t() : m_next(nullptr), m_prev(nullptr) {} LC *next() const { return m_next; } private: LC * m_next; LC * m_prev; }; template class linkedlist_t { public: linkedlist_t() : m_head(nullptr), m_tail(nullptr) {} ATTR_HOT void insert(LC &elem) { if (m_head != nullptr) m_head->m_prev = &elem; elem.m_next = m_head; elem.m_prev = nullptr; m_head = &elem; if (m_tail == nullptr) m_tail = &elem; } ATTR_HOT void add(LC &elem) { if (m_tail != nullptr) m_tail->m_next = &elem; elem.m_prev = m_tail; m_tail = &elem; elem.m_next = nullptr; if (m_head == nullptr) m_head = &elem; } ATTR_HOT void remove(const LC &elem) { if (prev(elem) == nullptr) { m_head = next(elem); if (m_tail == &elem) m_tail = nullptr; } else prev(elem)->m_next = next(elem); if (next(elem) == nullptr) { m_tail = prev(elem); if (m_head == &elem) m_head = nullptr; } else next(elem)->m_prev = prev(elem); } ATTR_HOT static LC *next(const LC &elem) { return static_cast(elem.m_next); } ATTR_HOT static LC *next(const LC *elem) { return static_cast(elem->m_next); } ATTR_HOT static LC *prev(const LC &elem) { return static_cast(elem.m_prev); } ATTR_HOT static LC *prev(const LC *elem) { return static_cast(elem->m_prev); } ATTR_HOT LC *first() const { return m_head; } ATTR_HOT void clear() { m_head = m_tail = nullptr; } ATTR_HOT bool is_empty() const { return (m_head == nullptr); } private: LC *m_head; LC *m_tail; }; #endif // ---------------------------------------------------------------------------------------- // string list // ---------------------------------------------------------------------------------------- class pstring_vector_t : public pvector_t { public: pstring_vector_t() : pvector_t() { } pstring_vector_t(const pstring &str, const pstring &onstr, bool ignore_empty = false) : pvector_t() { int p = 0; int pn; pn = str.find(onstr, p); while (pn>=0) { pstring t = str.substr(p, pn - p); if (!ignore_empty || t.len() != 0) this->push_back(t); p = pn + onstr.len(); pn = str.find(onstr, p); } if (p < (int) str.len()) { pstring t = str.substr(p); if (!ignore_empty || t.len() != 0) this->push_back(t); } } pstring_vector_t(const pstring &str, const pstring_vector_t &onstrl) : pvector_t() { pstring col = ""; unsigned i = 0; while (i=0) { if (col != "") this->push_back(col); col = ""; this->push_back(onstrl[p]); i += onstrl[p].blen(); } else { pstring::traits::code_t c = pstring::traits::code(str.cstr() + i); col += c; i+=pstring::traits::codelen(c); } } if (col != "") this->push_back(col); } }; // ---------------------------------------------------------------------------------------- // hashmap list // ---------------------------------------------------------------------------------------- template struct hash_functor { hash_functor() : m_hash(0) {} hash_functor(const C &v) : m_hash(v) { } friend unsigned operator%(const hash_functor &lhs, const unsigned &rhs) { return lhs.m_hash % rhs; } bool operator==(const hash_functor &lhs) const { return (m_hash == lhs.m_hash); } private: unsigned m_hash; }; template <> struct hash_functor { hash_functor() : m_hash(0) {} hash_functor(const pstring &v) { /* modified djb2 */ const pstring::mem_t *string = v.cstr(); unsigned result = 5381; for (pstring::mem_t c = *string; c != 0; c = *string++) result = ((result << 5) + result ) ^ (result >> (32 - 5)) ^ c; //result = (result*33) ^ c; m_hash = result; } friend unsigned operator%(const hash_functor &lhs, const unsigned &rhs) { return lhs.m_hash % rhs; } unsigned operator()() { return m_hash; } bool operator==(const hash_functor &lhs) const { return (m_hash == lhs.m_hash); } private: unsigned m_hash; }; #if 0 #if 0 unsigned hash(const pstring &v) const { /* Fowler???Noll???Vo hash - FNV-1 */ const char *string = v.cstr(); unsigned result = 2166136261; for (UINT8 c = *string++; c != 0; c = *string++) result = (result * 16777619) ^ c; // result = (result ^ c) * 16777619; FNV 1a return result; } #else unsigned hash(const pstring &v) const { /* jenkins one at a time algo */ unsigned result = 0; const char *string = v.cstr(); while (*string) { result += *string; string++; result += (result << 10); result ^= (result >> 6); } result += (result << 3); result ^= (result >> 11); result += (result << 15); return result; } #endif #endif template > class hashmap_t { public: hashmap_t() : m_hash(37) { for (unsigned i=0; i= 0) cnt++; const unsigned s = m_values.size(); if (s>0) printf("phashmap: %d elements %d hashsize, percent in overflow: %d\n", s, (unsigned) m_hash.size(), (s - cnt) * 100 / s); else printf("phashmap: No elements .. \n"); } #endif m_values.clear(); for (unsigned i=0; i= 0); } int index_of(const K &key) const { return get_idx(key); } unsigned size() const { return m_values.size(); } bool add(const K &key, const V &value) { /* * we are using the Euler prime function here * * n * n + n + 41 | 40 >= n >=0 * * and accept that outside we will not have a prime * */ if (m_values.size() * 3 / 2 > m_hash.size()) { unsigned n = std::sqrt( 2 * m_hash.size()); n = n * n + n + 41; m_hash.resize(n); rebuild(); } const H hash(key); const unsigned pos = hash % m_hash.size(); if (m_hash[pos] == -1) { unsigned vpos = m_values.size(); m_values.push_back(element_t(key, hash, value)); m_hash[pos] = vpos; } else { int ep = m_hash[pos]; for (; ep != -1; ep = m_values[ep].m_next) { if (m_values[ep].m_hash == hash && m_values[ep].m_key == key ) return false; /* duplicate */ } unsigned vpos = m_values.size(); m_values.push_back(element_t(key, hash, value)); m_values[vpos].m_next = m_hash[pos]; m_hash[pos] = vpos; } return true; } V& operator[](const K &key) { int p = get_idx(key); if (p == -1) { p = m_values.size(); add(key, V()); } return m_values[p].m_value; } V& value_at(const unsigned pos) { return m_values[pos].m_value; } const V& value_at(const unsigned pos) const { return m_values[pos].m_value; } V& key_at(const unsigned pos) { return m_values[pos].m_key; } private: int get_idx(const K &key) const { H hash(key); const unsigned pos = hash % m_hash.size(); for (int ep = m_hash[pos]; ep != -1; ep = m_values[ep].m_next) if (m_values[ep].m_hash == hash && m_values[ep].m_key == key ) return ep; return -1; } void rebuild() { for (unsigned i=0; i m_values; array_t m_hash; }; // ---------------------------------------------------------------------------------------- // sort a list ... slow, I am lazy // elements must support ">" operator. // ---------------------------------------------------------------------------------------- template static inline void sort_list(T &sl) { for(unsigned i = 0; i < sl.size(); i++) { for(unsigned j = i + 1; j < sl.size(); j++) if(sl[i] > sl[j]) std::swap(sl[i], sl[j]); } } PLIB_NAMESPACE_END() #endif /* PLISTS_H_ */