src/base/CbDataList.h

   1 /*
   2  * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #ifndef SQUID_CBDATALIST_H
  10 #define SQUID_CBDATALIST_H
  11
  12 #include "cbdata.h"
  13
  14 template <class C>
  15 class CbDataList
  16 {
  17     CBDATA_CLASS(CbDataList);
  18
  19 public:
  20     CbDataList(C const &);
  21     ~CbDataList();
  22
  23     /// If element is already in the list, returns false.
  24     /// Otherwise, adds the element to the end of the list and returns true.
  25     /// Exists to avoid double iteration of find() and push() combo.
  26     bool push_back_unique(C const &element);
  27     bool find(C const &)const;
  28     bool findAndTune(C const &);
  29     /// Iterates the entire list to return the last element holder.
  30     CbDataList *tail();
  31     CbDataList *next;
  32     C element;
  33     bool empty() const { return this == NULL; }
  34 };
  35
  36 template<class C>
  37 class CbDataListContainer
  38 {
  39
  40 public:
  41     CbDataListContainer();
  42     ~CbDataListContainer();
  43     CbDataList<C> *push_back (C const &);
  44     C pop_front();
  45     bool empty() const;
  46
  47     CbDataList<C> *head;
  48 };
  49
  50 template<class C>
  51 class CbDataListIterator
  52 {
  53 public:
  54     CbDataListIterator(CbDataListContainer<C> const &list) : next_entry(list.head) {}
  55     const C & next() {
  56         CbDataList<C> *entry = next_entry;
  57         if (entry)
  58             next_entry = entry->next;
  59         return entry->element;
  60     }
  61     bool end() {
  62         return next_entry == nullptr;
  63     }
  64
  65 private:
  66     CbDataList<C> *next_entry;
  67 };
  68
  69 /** \cond AUTODOCS_IGNORE */
  70 template <class C>
  71 cbdata_type CbDataList<C>::CBDATA_CbDataList = CBDATA_UNKNOWN;
  72 /** \endcond */
  73
  74 template <class C>
  75 CbDataList<C>::CbDataList(C const &value) : next(nullptr), element (value)
  76 {}
  77
  78 template <class C>
  79 CbDataList<C>::~CbDataList()
  80 {
  81     if (next)
  82         delete next;
  83 }
  84
  85 template <class C>
  86 bool
  87 CbDataList<C>::push_back_unique(C const &toAdd)
  88 {
  89     CbDataList<C> *last;
  90     for (last = this; last->next; last = last->next) {
  91         if (last->element == toAdd)
  92             return false;
  93     }
  94
  95     last->next = new CbDataList<C>(toAdd);
  96     return true;
  97 }
  98
  99 template <class C>
 100 CbDataList<C> *
 101 CbDataList<C>::tail()
 102 {
 103     CbDataList<C> *last;
 104     for (last = this; last->next; last = last->next);
 105     return last;
 106 }
 107
 108 template <class C>
 109 bool
 110 CbDataList<C>::find (C const &toFind) const
 111 {
 112     CbDataList<C> const *node = nullptr;
 113
 114     for (node = this; node; node = node->next)
 115         if (node->element == toFind)
 116             return true;
 117
 118     return false;
 119 }
 120
 121 template <class C>
 122 bool
 123 CbDataList<C>::findAndTune(C const & toFind)
 124 {
 125     CbDataList<C> *prev = NULL;
 126
 127     for (CbDataList<C> *node = this; node; node = node->
 128             next) {
 129         if (node->element == toFind) {
 130             if (prev != NULL) {
 131                 /* shift the element just found to the second position
 132                  * in the list */
 133                 prev->next = node->next;
 134                 node->next = this->next;
 135                 this->next = node;
 136             }
 137
 138             return true;
 139         }
 140
 141         prev = node;
 142     }
 143
 144     return false;
 145 }
 146
 147 template <class C>
 148 CbDataListContainer<C>::CbDataListContainer() : head (nullptr)
 149 {}
 150
 151 template <class C>
 152 CbDataListContainer<C>::~CbDataListContainer()
 153 {
 154     if (head)
 155         delete head;
 156 }
 157
 158 template <class C>
 159 CbDataList<C> *
 160 CbDataListContainer<C>::push_back (C const &element)
 161 {
 162     CbDataList<C> *node = new CbDataList<C> (element);
 163
 164     if (head) {
 165         CbDataList<C> *tempNode = nullptr;
 166
 167         for (tempNode = head; tempNode->next; tempNode = tempNode->next);
 168         tempNode->next = node;
 169     } else
 170         head = node;
 171
 172     return node;
 173 }
 174
 175 template <class C>
 176 C
 177 CbDataListContainer<C>::pop_front()
 178 {
 179     if (head) {
 180         C result = head->element;
 181         CbDataList<C> *node = head;
 182         head = head->next;
 183         node->next = NULL;
 184         delete node;
 185         return result;
 186     }
 187
 188     return C();
 189 }
 190
 191 template <class C>
 192 bool
 193 CbDataListContainer<C>::empty() const
 194 {
 195     return head == nullptr;
 196 }
 197
 198 #endif /* SQUID_CBDATALIST_H */
 199