lru_cache.cpp 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275
  1. /*
  2. * Copyright (C) 2011-2017 Intel Corporation. All rights reserved.
  3. *
  4. * Redistribution and use in source and binary forms, with or without
  5. * modification, are permitted provided that the following conditions
  6. * are met:
  7. *
  8. * * Redistributions of source code must retain the above copyright
  9. * notice, this list of conditions and the following disclaimer.
  10. * * Redistributions in binary form must reproduce the above copyright
  11. * notice, this list of conditions and the following disclaimer in
  12. * the documentation and/or other materials provided with the
  13. * distribution.
  14. * * Neither the name of Intel Corporation nor the names of its
  15. * contributors may be used to endorse or promote products derived
  16. * from this software without specific prior written permission.
  17. *
  18. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22. * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24. * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25. * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26. * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29. *
  30. */
  31. #include "lru_cache.h"
  32. lru_cache::lru_cache()
  33. {
  34. m_it = list.begin();
  35. }
  36. lru_cache::~lru_cache()
  37. {
  38. list_node_t* list_node;
  39. map_node_t* map_node;
  40. while (list.size() > 0)
  41. {
  42. list_node = list.front();
  43. map_node = map[list_node->key];
  44. map.erase(list_node->key);
  45. delete map_node;
  46. list.pop_front();
  47. delete list_node;
  48. }
  49. assert(list.empty() == true);
  50. assert(map.empty() == true);
  51. }
  52. void lru_cache::rehash(uint32_t size_)
  53. {
  54. map.rehash(size_);
  55. }
  56. bool lru_cache::add(uint64_t key, void* data)
  57. {
  58. map_node_t* map_node = NULL;
  59. list_node_t* list_node = NULL;
  60. try {
  61. map_node = new map_node_t();
  62. list_node = new list_node_t();
  63. }
  64. catch (std::bad_alloc e) {
  65. (void)e; // remove warning
  66. return false;
  67. }
  68. list_node->key = key;
  69. list.push_front(list_node);
  70. map_iterator map_it = map.find(key);
  71. assert(map_it == map.end());
  72. if (map_it != map.end())
  73. {
  74. // this indicates some fatal problem, perhaps race issue caused by bad locks...
  75. map_node_t* tmp_map_node = map_it->second;
  76. if (tmp_map_node != NULL)
  77. delete tmp_map_node;
  78. map.erase(map_it);
  79. }
  80. map_node->data = data;
  81. map_node->list_it = list.begin();
  82. map[key] = map_node;
  83. return true;
  84. }
  85. void* lru_cache::find(uint64_t key)
  86. {
  87. map_iterator map_it = map.find(key);
  88. if (map_it == map.end())
  89. return NULL;
  90. map_node_t* map_node = map_it->second;
  91. return map_node->data;
  92. }
  93. void* lru_cache::get(uint64_t key)
  94. {
  95. map_iterator map_it = map.find(key);
  96. if (map_it == map.end())
  97. return NULL;
  98. map_node_t* map_node = map_it->second;
  99. list_node_t* list_node = *(map_node->list_it);
  100. assert(list_node != NULL);
  101. if (list_node == NULL) // this should never happen, but just in case, code is here to fix it
  102. {
  103. try {
  104. list_node = new list_node_t();
  105. list_node->key = map_it->first;
  106. }
  107. catch (std::bad_alloc e) {
  108. (void)e; // remove warning
  109. return NULL;
  110. }
  111. }
  112. list.erase(map_node->list_it);
  113. list.push_front(list_node);
  114. map_node->list_it = list.begin();
  115. return map_node->data;
  116. }
  117. uint32_t lru_cache::size()
  118. {
  119. assert(list.size() == map.size());
  120. return (uint32_t)list.size();
  121. }
  122. void* lru_cache::get_first()
  123. {
  124. if (list.size() == 0)
  125. return NULL;
  126. m_it = list.begin();
  127. if (m_it == list.end())
  128. return NULL;
  129. list_node_t* list_node = (*m_it);
  130. assert(list_node != NULL);
  131. if (list_node == NULL)
  132. return NULL;
  133. map_iterator map_it = map.find(list_node->key);
  134. assert(map_it != map.end());
  135. if (map_it == map.end())
  136. return NULL;
  137. map_node_t* map_node = map_it->second;
  138. assert(map_node != NULL);
  139. if (map_node == NULL)
  140. return NULL;
  141. return map_node->data;
  142. }
  143. void* lru_cache::get_next()
  144. {
  145. if (list.size() == 0)
  146. return NULL;
  147. ++m_it;
  148. if (m_it == list.end())
  149. return NULL;
  150. list_node_t* list_node = (*m_it);
  151. assert(list_node != NULL);
  152. if (list_node == NULL)
  153. return NULL;
  154. map_iterator map_it = map.find(list_node->key);
  155. assert(map_it != map.end());
  156. if (map_it == map.end())
  157. return NULL;
  158. map_node_t* map_node = map_it->second;
  159. assert(map_node != NULL);
  160. if (map_node == NULL)
  161. return NULL;
  162. return map_node->data;
  163. }
  164. void* lru_cache::get_last()
  165. {
  166. if (list.size() == 0)
  167. return NULL;
  168. list_iterator it = list.end(); // pointer to the object past-the-end
  169. assert(it != list.begin());
  170. if (it == list.begin()) // the list is empty
  171. return NULL;
  172. --it; // now it points to the last object
  173. list_node_t* list_node = (*it);
  174. assert(list_node != NULL);
  175. if (list_node == NULL)
  176. return NULL;
  177. map_iterator map_it = map.find(list_node->key);
  178. assert(map_it != map.end());
  179. if (map_it == map.end())
  180. return NULL;
  181. map_node_t* map_node = map_it->second;
  182. assert(map_node != NULL);
  183. if (map_node == NULL)
  184. return NULL;
  185. return map_node->data;
  186. }
  187. void lru_cache::remove_last()
  188. {
  189. uint64_t key;
  190. list_iterator it = list.end(); // pointer to the object past-the-end
  191. if (it == list.begin()) // the list is empty
  192. return;
  193. --it; // now it points to the last object
  194. list_node_t* list_node = (*it);
  195. list.erase(it);
  196. assert(list_node != NULL);
  197. if (list_node == NULL) // unclear how this can happen...
  198. return;
  199. key = list_node->key;
  200. delete list_node;
  201. map_iterator map_it = map.find(key);
  202. assert(map_it != map.end());
  203. if (map_it == map.end())
  204. return;
  205. map_node_t* map_node = map_it->second;
  206. assert(map_node != NULL);
  207. if (map_node == NULL)
  208. return;
  209. map.erase(key);
  210. delete map_node;
  211. }