1 /* vim: set expandtab ts=4 sw=4: */
2 /*
3 * You may redistribute this program and/or modify it under the terms of
4 * the GNU General Public License as published by the Free Software Foundation,
5 * either version 3 of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <https://www.gnu.org/licenses/>.
14 */
15 #include "dht/Address.h"
16 #include "dht/dhtcore/SearchStore.h"
17 #include "util/Bits.h"
18 #include "util/log/Log.h"
19 #include "util/AverageRoller.h"
20 #include "util/Endian.h"
21 #include "util/events/Time.h"
22
23 /*--------------------Structures--------------------*/
24
25 /** An outstanding search for a target. */
26 struct SearchStore_Search_pvt
27 {
28 struct SearchStore_Search pub;
29
30 /** Numbert of Address's in searchStack. */
31 uint16_t searchStackSize;
32
33 /** The index to insert the next node in nodesAsked, this will wrap. */
34 uint16_t nodesAskedIndex;
35
36 /** The ID of what we are looking for. */
37 uint8_t searchTarget[16];
38
39 /** The nodes to ask when performing the search. */
40 struct Address searchStack[SearchStore_SEARCH_NODES];
41
42 /** The nodes which have already been queried in this search. */
43 struct SearchStore_Node nodesAsked[SearchStore_SEARCH_NODES];
44 };
45
46 /*--------------------Functions--------------------*/
47
48 /** See: SearchStore.h */
SearchStore_new(struct Allocator * allocator,struct Log * logger)49 struct SearchStore* SearchStore_new(struct Allocator* allocator, struct Log* logger)
50 {
51 return Allocator_clone(allocator, (&(struct SearchStore) {
52 .allocator = allocator,
53 .logger = logger
54 }));
55 }
56
57 /** See: SearchStore.h */
SearchStore_newSearch(uint8_t searchTarget[16],struct SearchStore * store,struct Allocator * alloc)58 struct SearchStore_Search* SearchStore_newSearch(uint8_t searchTarget[16],
59 struct SearchStore* store,
60 struct Allocator* alloc)
61 {
62 struct SearchStore_Search_pvt* search =
63 Allocator_clone(alloc, (&(struct SearchStore_Search_pvt) {
64 .pub = {
65 .callbackContext = NULL,
66 .store = store,
67 .alloc = alloc
68 }
69 }));
70 Bits_memcpy(search->searchTarget, searchTarget, Address_SEARCH_TARGET_SIZE);
71
72 return &search->pub;
73 }
74
75 /** See: SearchStore.h */
SearchStore_addNodeToSearch(struct Address * addr,struct SearchStore_Search * search)76 int SearchStore_addNodeToSearch(struct Address* addr, struct SearchStore_Search* search)
77 {
78 struct SearchStore_Search_pvt* pvtSearch = (struct SearchStore_Search_pvt*) search;
79 for (int i = 0; i < SearchStore_SEARCH_NODES; i++) {
80 if (!Bits_memcmp(addr->key, pvtSearch->nodesAsked[i].address.key, 32)) {
81 // Already bugged this node, skip.
82 return -1;
83 } else if (i == pvtSearch->nodesAskedIndex
84 && Bits_isZero(pvtSearch->nodesAsked[i].address.key, 32))
85 {
86 // short circuit a common case where the nodesAskedIndex has not yet wrapped.
87 break;
88 }
89 }
90
91 const uint16_t index =
92 (pvtSearch->searchStackSize < SearchStore_SEARCH_NODES)
93 // add it to the end...
94 ? pvtSearch->searchStackSize++
95
96 // nodes are added worst-to-best so replace the last entry.
97 : pvtSearch->searchStackSize - 1;
98
99 Bits_memcpy(&pvtSearch->searchStack[index], addr, Address_SIZE);
100
101 return 0;
102 }
103
104 /** See: SearchStore.h */
SearchStore_getNextNode(struct SearchStore_Search * search)105 struct SearchStore_Node* SearchStore_getNextNode(struct SearchStore_Search* search)
106 {
107 struct SearchStore_Search_pvt* pvtSearch = (struct SearchStore_Search_pvt*) search;
108 if (!pvtSearch->searchStackSize) {
109 return NULL;
110 }
111
112 struct SearchStore_Node* nn = &pvtSearch->nodesAsked[pvtSearch->nodesAskedIndex];
113 Bits_memcpy(&nn->address,
114 &pvtSearch->searchStack[--pvtSearch->searchStackSize],
115 sizeof(struct Address));
116 nn->search = search;
117
118 pvtSearch->nodesAskedIndex = (pvtSearch->nodesAskedIndex + 1) % SearchStore_SEARCH_NODES;
119 return nn;
120 }
121