1 // Copyright 2015-2016 Espressif Systems (Shanghai) PTE LTD
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "nvs_item_hash_list.hpp"
16
17 namespace nvs
18 {
19
HashList()20 HashList::HashList()
21 {
22 }
23
clear()24 void HashList::clear()
25 {
26 for (auto it = mBlockList.begin(); it != mBlockList.end();) {
27 auto tmp = it;
28 ++it;
29 mBlockList.erase(tmp);
30 delete static_cast<HashListBlock*>(tmp);
31 }
32 }
33
~HashList()34 HashList::~HashList()
35 {
36 clear();
37 }
38
HashListBlock()39 HashList::HashListBlock::HashListBlock()
40 {
41 static_assert(sizeof(HashListBlock) == HashListBlock::BYTE_SIZE,
42 "cache block size calculation incorrect");
43 }
44
insert(const Item & item,size_t index)45 esp_err_t HashList::insert(const Item& item, size_t index)
46 {
47 const uint32_t hash_24 = item.calculateCrc32WithoutValue() & 0xffffff;
48 // add entry to the end of last block if possible
49 if (mBlockList.size()) {
50 auto& block = mBlockList.back();
51 if (block.mCount < HashListBlock::ENTRY_COUNT) {
52 block.mNodes[block.mCount++] = HashListNode(hash_24, index);
53 return ESP_OK;
54 }
55 }
56 // if the above failed, create a new block and add entry to it
57 HashListBlock* newBlock = new (std::nothrow) HashListBlock;
58
59 if (!newBlock) return ESP_ERR_NO_MEM;
60
61 mBlockList.push_back(newBlock);
62 newBlock->mNodes[0] = HashListNode(hash_24, index);
63 newBlock->mCount++;
64
65 return ESP_OK;
66 }
67
erase(size_t index)68 bool HashList::erase(size_t index)
69 {
70 for (auto it = mBlockList.begin(); it != mBlockList.end();) {
71 bool haveEntries = false;
72 bool foundIndex = false;
73 for (size_t i = 0; i < it->mCount; ++i) {
74 if (it->mNodes[i].mIndex == index) {
75 it->mNodes[i].mIndex = 0xff;
76 foundIndex = true;
77 /* found the item and removed it */
78 }
79 if (it->mNodes[i].mIndex != 0xff) {
80 haveEntries = true;
81 }
82 if (haveEntries && foundIndex) {
83 /* item was found, and HashListBlock still has some items */
84 return true;
85 }
86 }
87 /* no items left in HashListBlock, can remove */
88 if (!haveEntries) {
89 auto tmp = it;
90 ++it;
91 mBlockList.erase(tmp);
92 delete static_cast<HashListBlock*>(tmp);
93 } else {
94 ++it;
95 }
96 if (foundIndex) {
97 /* item was found and empty HashListBlock was removed */
98 return true;
99 }
100 }
101
102 // item hasn't been present in cache");
103 return false;
104 }
105
find(size_t start,const Item & item)106 size_t HashList::find(size_t start, const Item& item)
107 {
108 const uint32_t hash_24 = item.calculateCrc32WithoutValue() & 0xffffff;
109 for (auto it = mBlockList.begin(); it != mBlockList.end(); ++it) {
110 for (size_t index = 0; index < it->mCount; ++index) {
111 HashListNode& e = it->mNodes[index];
112 if (e.mIndex >= start &&
113 e.mHash == hash_24 &&
114 e.mIndex != 0xff) {
115 return e.mIndex;
116 }
117 }
118 }
119 return SIZE_MAX;
120 }
121
122
123 } // namespace nvs
124
