/* * Copyright (C) 1996-2023 The Squid Software Foundation and contributors * * Squid software is distributed under GPLv2+ license and includes * contributions from numerous individuals and organizations. * Please see the COPYING and CONTRIBUTORS files for details. */ #ifndef SQUID_SRC_BASE_CBDATALIST_H #define SQUID_SRC_BASE_CBDATALIST_H #include "cbdata.h" template class CbDataList { CBDATA_CLASS(CbDataList); public: CbDataList(C const &); ~CbDataList(); /// If element is already in the list, returns false. /// Otherwise, adds the element to the end of the list and returns true. /// Exists to avoid double iteration of find() and push() combo. bool push_back_unique(C const &element); bool find(C const &)const; bool findAndTune(C const &); /// Iterates the entire list to return the last element holder. CbDataList *tail(); CbDataList *next; C element; bool empty() const { return this == NULL; } }; template class CbDataListContainer { public: CbDataListContainer(); ~CbDataListContainer(); CbDataList *push_back (C const &); C pop_front(); bool empty() const; CbDataList *head; }; template class CbDataListIterator { public: CbDataListIterator(CbDataListContainer const &list) : next_entry(list.head) {} const C & next() { CbDataList *entry = next_entry; if (entry) next_entry = entry->next; return entry->element; } bool end() { return next_entry == nullptr; } private: CbDataList *next_entry; }; /** \cond AUTODOCS_IGNORE */ template cbdata_type CbDataList::CBDATA_CbDataList = CBDATA_UNKNOWN; /** \endcond */ template CbDataList::CbDataList(C const &value) : next(nullptr), element (value) {} template CbDataList::~CbDataList() { if (next) delete next; } template bool CbDataList::push_back_unique(C const &toAdd) { CbDataList *last; for (last = this; last->next; last = last->next) { if (last->element == toAdd) return false; } last->next = new CbDataList(toAdd); return true; } template CbDataList * CbDataList::tail() { CbDataList *last; for (last = this; last->next; last = last->next); return last; } template bool CbDataList::find (C const &toFind) const { CbDataList const *node = nullptr; for (node = this; node; node = node->next) if (node->element == toFind) return true; return false; } template bool CbDataList::findAndTune(C const & toFind) { CbDataList *prev = NULL; for (CbDataList *node = this; node; node = node-> next) { if (node->element == toFind) { if (prev != NULL) { /* shift the element just found to the second position * in the list */ prev->next = node->next; node->next = this->next; this->next = node; } return true; } prev = node; } return false; } template CbDataListContainer::CbDataListContainer() : head (nullptr) {} template CbDataListContainer::~CbDataListContainer() { if (head) delete head; } template CbDataList * CbDataListContainer::push_back (C const &element) { CbDataList *node = new CbDataList (element); if (head) { CbDataList *tempNode = nullptr; for (tempNode = head; tempNode->next; tempNode = tempNode->next); tempNode->next = node; } else head = node; return node; } template C CbDataListContainer::pop_front() { if (head) { C result = head->element; CbDataList *node = head; head = head->next; node->next = NULL; delete node; return result; } return C(); } template bool CbDataListContainer::empty() const { return head == nullptr; } #endif /* SQUID_SRC_BASE_CBDATALIST_H */