diff options
author | Christian Grothoff <christian@grothoff.org> | 2011-03-11 16:58:27 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2011-03-11 16:58:27 +0000 |
commit | 562b33143ee9fa431a68ea6741e4feb3ba388f83 (patch) | |
tree | 6318eb2c56ff76730708a4791804842c63cf1f81 /src/fs/gnunet-service-fs_pe.c | |
parent | 64821d4ae43b03b30de3dd136137598c0d5a2ab2 (diff) | |
download | gnunet-562b33143ee9fa431a68ea6741e4feb3ba388f83.tar.gz gnunet-562b33143ee9fa431a68ea6741e4feb3ba388f83.zip |
changing heap remove node api to not pass heap; more fs hacking
Diffstat (limited to 'src/fs/gnunet-service-fs_pe.c')
-rw-r--r-- | src/fs/gnunet-service-fs_pe.c | 207 |
1 files changed, 107 insertions, 100 deletions
diff --git a/src/fs/gnunet-service-fs_pe.c b/src/fs/gnunet-service-fs_pe.c index e7608653e..306bb948c 100644 --- a/src/fs/gnunet-service-fs_pe.c +++ b/src/fs/gnunet-service-fs_pe.c | |||
@@ -28,13 +28,51 @@ | |||
28 | #include "gnunet-service-fs_pe.h" | 28 | #include "gnunet-service-fs_pe.h" |
29 | #include "gnunet-service-fs_pr.h" | 29 | #include "gnunet-service-fs_pr.h" |
30 | 30 | ||
31 | |||
32 | /** | ||
33 | * Information we keep per request per peer. This is a doubly-linked | ||
34 | * list (with head and tail in the 'struct GSF_PendingRequestData') | ||
35 | * with one entry in each heap of each 'struct PeerPlan'. Each | ||
36 | * entry tracks information relevant for this request and this peer. | ||
37 | */ | ||
38 | struct GSF_RequestPlan | ||
39 | { | ||
40 | |||
41 | /** | ||
42 | * This is a doubly-linked list. | ||
43 | */ | ||
44 | struct GSF_RequestPlan *next; | ||
45 | |||
46 | /** | ||
47 | * This is a doubly-linked list. | ||
48 | */ | ||
49 | struct GSF_RequestPlan *prev; | ||
50 | |||
51 | /** | ||
52 | * Heap node associated with this request and this peer. | ||
53 | */ | ||
54 | struct GNUNET_CONTAINER_HeapNode *hn; | ||
55 | |||
56 | /** | ||
57 | * Associated pending request. | ||
58 | */ | ||
59 | struct GSF_PendingRequest *pr; | ||
60 | |||
61 | /** | ||
62 | * Earliest time we'd be happy to transmit this request. | ||
63 | */ | ||
64 | struct GNUNET_TIME_Absolute earliest_transmission; | ||
65 | |||
66 | }; | ||
67 | |||
68 | |||
31 | /** | 69 | /** |
32 | * Transmission plan for a peer. | 70 | * Transmission plan for a peer. |
33 | */ | 71 | */ |
34 | struct PeerPlan | 72 | struct PeerPlan |
35 | { | 73 | { |
36 | /** | 74 | /** |
37 | * Heap with pending queries, smaller weights mean higher priority. | 75 | * Heap with pending queries (struct GSF_RequestPlan), smaller weights mean higher priority. |
38 | */ | 76 | */ |
39 | struct GNUNET_CONTAINER_Heap *heap; | 77 | struct GNUNET_CONTAINER_Heap *heap; |
40 | 78 | ||
@@ -62,6 +100,28 @@ static struct GNUNET_CONTAINER_MultiHashMap *plans; | |||
62 | 100 | ||
63 | 101 | ||
64 | /** | 102 | /** |
103 | * Insert the given request plan into the heap with the appropriate weight. | ||
104 | * | ||
105 | * @param pp associated peer's plan | ||
106 | * @param rp request to plan | ||
107 | */ | ||
108 | static void | ||
109 | plan (struct PeerPlan *pp, | ||
110 | struct GSF_RequestPlan *rp) | ||
111 | { | ||
112 | GNUNET_CONTAINER_HeapCostType weight; | ||
113 | struct GSF_PendingRequestData *prd; | ||
114 | |||
115 | prd = GSF_pending_request_get_data_ (rp->pr); | ||
116 | weight = 0; // FIXME: calculate real weight! | ||
117 | // FIXME: calculate 'rp->earliest_transmission'! | ||
118 | rp->hn = GNUNET_CONTAINER_heap_insert (pp->heap, | ||
119 | rp, | ||
120 | weight); | ||
121 | } | ||
122 | |||
123 | |||
124 | /** | ||
65 | * Figure out when and how to transmit to the given peer. | 125 | * Figure out when and how to transmit to the given peer. |
66 | * | 126 | * |
67 | * @param cls the 'struct GSF_ConnectedPeer' for transmission | 127 | * @param cls the 'struct GSF_ConnectedPeer' for transmission |
@@ -86,7 +146,7 @@ transmit_message_callback (void *cls, | |||
86 | void *buf) | 146 | void *buf) |
87 | { | 147 | { |
88 | struct PeerPlan *pp = cls; | 148 | struct PeerPlan *pp = cls; |
89 | struct GSF_PendingRequest *pr; | 149 | struct GSF_RequestPlan *rp; |
90 | size_t msize; | 150 | size_t msize; |
91 | 151 | ||
92 | if (NULL == buf) | 152 | if (NULL == buf) |
@@ -95,8 +155,8 @@ transmit_message_callback (void *cls, | |||
95 | pp->task = GNUNET_SCHEDULER_add_now (&schedule_peer_transmission, pp); | 155 | pp->task = GNUNET_SCHEDULER_add_now (&schedule_peer_transmission, pp); |
96 | return 0; | 156 | return 0; |
97 | } | 157 | } |
98 | pr = GNUNET_CONTAINER_heap_peek (pp->heap); | 158 | rp = GNUNET_CONTAINER_heap_peek (pp->heap); |
99 | msize = GSF_pending_request_get_message_ (pr, buf_size, buf); | 159 | msize = GSF_pending_request_get_message_ (rp->pr, buf_size, buf); |
100 | if (msize > buf_size) | 160 | if (msize > buf_size) |
101 | { | 161 | { |
102 | /* buffer to small (message changed), try again */ | 162 | /* buffer to small (message changed), try again */ |
@@ -104,8 +164,9 @@ transmit_message_callback (void *cls, | |||
104 | return 0; | 164 | return 0; |
105 | } | 165 | } |
106 | /* remove from root, add again elsewhere... */ | 166 | /* remove from root, add again elsewhere... */ |
107 | GNUNET_assert (pr == GNUNET_CONTAINER_heap_remove_root (pp->heap)); | 167 | GNUNET_assert (rp == GNUNET_CONTAINER_heap_remove_root (pp->heap)); |
108 | GSF_plan_add_ (pp->cp, pr); | 168 | rp->hn = NULL; |
169 | plan (pp, rp); | ||
109 | return msize; | 170 | return msize; |
110 | } | 171 | } |
111 | 172 | ||
@@ -121,7 +182,8 @@ schedule_peer_transmission (void *cls, | |||
121 | const struct GNUNET_SCHEDULER_TaskContext *tc) | 182 | const struct GNUNET_SCHEDULER_TaskContext *tc) |
122 | { | 183 | { |
123 | struct PeerPlan *pp = cls; | 184 | struct PeerPlan *pp = cls; |
124 | struct GSF_PendingRequest *pr; | 185 | struct GSF_RequestPlan *rp; |
186 | struct GSF_PendingRequestData *prd; | ||
125 | size_t msize; | 187 | size_t msize; |
126 | struct GNUNET_TIME_Relative delay; | 188 | struct GNUNET_TIME_Relative delay; |
127 | 189 | ||
@@ -131,17 +193,17 @@ schedule_peer_transmission (void *cls, | |||
131 | if (0 == GNUNET_CONTAINER_heap_get_size (pp->heap)) | 193 | if (0 == GNUNET_CONTAINER_heap_get_size (pp->heap)) |
132 | return; | 194 | return; |
133 | GNUNET_assert (NULL == pp->pth); | 195 | GNUNET_assert (NULL == pp->pth); |
134 | pr = GNUNET_CONTAINER_heap_peek (pp->heap); | 196 | rp = GNUNET_CONTAINER_heap_peek (pp->heap); |
135 | if (0) // FIXME: if (re)transmission should wait, wait... | 197 | prd = GSF_pending_request_get_data_ (rp->pr); |
198 | delay = GNUNET_TIME_absolute_get_remaining (rp->earliest_transmission); | ||
199 | if (delay.rel_value > 0) | ||
136 | { | 200 | { |
137 | delay = GNUNET_TIME_UNIT_SECONDS; | ||
138 | // FIXME | ||
139 | pp->task = GNUNET_SCHEDULER_add_delayed (delay, | 201 | pp->task = GNUNET_SCHEDULER_add_delayed (delay, |
140 | &schedule_peer_transmission, | 202 | &schedule_peer_transmission, |
141 | pp); | 203 | pp); |
142 | return; | 204 | return; |
143 | } | 205 | } |
144 | msize = GSF_pending_request_get_message_ (pr, 0, NULL); | 206 | msize = GSF_pending_request_get_message_ (rp->pr, 0, NULL); |
145 | pp->pth = GSF_peer_transmit_ (pp->cp, | 207 | pp->pth = GSF_peer_transmit_ (pp->cp, |
146 | GNUNET_YES, | 208 | GNUNET_YES, |
147 | 0 /* FIXME: pr->priority? */, | 209 | 0 /* FIXME: pr->priority? */, |
@@ -165,7 +227,8 @@ GSF_plan_add_ (const struct GSF_ConnectedPeer *cp, | |||
165 | { | 227 | { |
166 | struct GNUNET_PeerIdentity id; | 228 | struct GNUNET_PeerIdentity id; |
167 | struct PeerPlan *pp; | 229 | struct PeerPlan *pp; |
168 | GNUNET_CONTAINER_HeapCostType weight; | 230 | struct GSF_PendingRequestData *prd; |
231 | struct GSF_RequestPlan *rp; | ||
169 | 232 | ||
170 | GSF_connected_peer_get_identity_ (cp, &id); | 233 | GSF_connected_peer_get_identity_ (cp, &id); |
171 | pp = GNUNET_CONTAINER_multihashmap_get (plans, | 234 | pp = GNUNET_CONTAINER_multihashmap_get (plans, |
@@ -179,13 +242,16 @@ GSF_plan_add_ (const struct GSF_ConnectedPeer *cp, | |||
179 | pp, | 242 | pp, |
180 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); | 243 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); |
181 | } | 244 | } |
182 | weight = 0; // FIXME: calculate real weight! | 245 | prd = GSF_pending_request_get_data_ (pr); |
183 | GNUNET_CONTAINER_heap_insert (pp->heap, | 246 | rp = GNUNET_malloc (sizeof (struct GSF_RequestPlan)); |
184 | pr, | 247 | rp->pr = pr; |
185 | weight); | 248 | GNUNET_CONTAINER_DLL_insert (prd->rp_head, |
249 | prd->rp_tail, | ||
250 | rp); | ||
251 | plan (pp, rp); | ||
186 | if (pp->pth != NULL) | 252 | if (pp->pth != NULL) |
187 | { | 253 | { |
188 | if (pr != GNUNET_CONTAINER_heap_peek (pp->heap)) | 254 | if (rp != GNUNET_CONTAINER_heap_peek (pp->heap)) |
189 | return; | 255 | return; |
190 | GSF_peer_transmit_cancel_ (pp->pth); | 256 | GSF_peer_transmit_cancel_ (pp->pth); |
191 | pp->pth = NULL; | 257 | pp->pth = NULL; |
@@ -208,6 +274,8 @@ GSF_plan_notify_peer_disconnect_ (const struct GSF_ConnectedPeer *cp) | |||
208 | { | 274 | { |
209 | struct GNUNET_PeerIdentity id; | 275 | struct GNUNET_PeerIdentity id; |
210 | struct PeerPlan *pp; | 276 | struct PeerPlan *pp; |
277 | struct GSF_RequestPlan *rp; | ||
278 | struct GSF_PendingRequestData *prd; | ||
211 | 279 | ||
212 | GSF_connected_peer_get_identity_ (cp, &id); | 280 | GSF_connected_peer_get_identity_ (cp, &id); |
213 | pp = GNUNET_CONTAINER_multihashmap_get (plans, | 281 | pp = GNUNET_CONTAINER_multihashmap_get (plans, |
@@ -219,101 +287,40 @@ GSF_plan_notify_peer_disconnect_ (const struct GSF_ConnectedPeer *cp) | |||
219 | GSF_peer_transmit_cancel_ (pp->pth); | 287 | GSF_peer_transmit_cancel_ (pp->pth); |
220 | if (GNUNET_SCHEDULER_NO_TASK != pp->task) | 288 | if (GNUNET_SCHEDULER_NO_TASK != pp->task) |
221 | GNUNET_SCHEDULER_cancel (pp->task); | 289 | GNUNET_SCHEDULER_cancel (pp->task); |
222 | GNUNET_CONTAINER_heap_destroy (pp->heap); | 290 | while (NULL != (rp = GNUNET_CONTAINER_heap_remove_root (pp->heap))) |
223 | GNUNET_free (pp); | ||
224 | } | ||
225 | |||
226 | |||
227 | /** | ||
228 | * Closure for 'find_request'. | ||
229 | */ | ||
230 | struct FindRequestClosure | ||
231 | { | ||
232 | /** | ||
233 | * Place to store the node that was found (NULL for none). | ||
234 | */ | ||
235 | struct GNUNET_CONTAINER_HeapNode *node; | ||
236 | |||
237 | /** | ||
238 | * Value we're looking for | ||
239 | */ | ||
240 | const struct GSF_PendingRequest *pr; | ||
241 | }; | ||
242 | |||
243 | |||
244 | /** | ||
245 | * Find a heap node where the value matches the | ||
246 | * pending request given in the closure. | ||
247 | * | ||
248 | * @param cls the 'struct FindRequestClosure' | ||
249 | * @param node heap structure we're looking for on a match | ||
250 | * @param element the pending request stored in the heap | ||
251 | * @param cost weight of the request | ||
252 | * @return GNUNET_YES to continue looking | ||
253 | */ | ||
254 | static int | ||
255 | find_request (void *cls, | ||
256 | struct GNUNET_CONTAINER_HeapNode *node, | ||
257 | void *element, | ||
258 | GNUNET_CONTAINER_HeapCostType cost) | ||
259 | { | ||
260 | struct FindRequestClosure *frc = cls; | ||
261 | struct GSF_PendingRequest *pr = element; | ||
262 | |||
263 | if (pr == frc->pr) | ||
264 | { | ||
265 | frc->node = node; | ||
266 | return GNUNET_NO; | ||
267 | } | ||
268 | return GNUNET_YES; | ||
269 | } | ||
270 | |||
271 | |||
272 | /** | ||
273 | * Remove the given request from all heaps. * FIXME: O(n) -- inefficient! | ||
274 | * | ||
275 | * @param cls 'struct GSF_PendingRequest' to purge | ||
276 | * @param key identity of the peer we're currently looking at (unused) | ||
277 | * @param value PeerPlan for the given peer to search for the 'cls' | ||
278 | * @return GNUNET_OK (continue iteration) | ||
279 | */ | ||
280 | static int | ||
281 | remove_request (void *cls, | ||
282 | const GNUNET_HashCode *key, | ||
283 | void *value) | ||
284 | { | ||
285 | const struct GSF_PendingRequest *pr = cls; | ||
286 | struct PeerPlan *pp = value; | ||
287 | struct GNUNET_CONTAINER_Heap *h = pp->heap; | ||
288 | struct FindRequestClosure frc; | ||
289 | |||
290 | frc.pr = pr; | ||
291 | do | ||
292 | { | 291 | { |
293 | frc.node = NULL; | 292 | prd = GSF_pending_request_get_data_ (rp->pr); |
294 | GNUNET_CONTAINER_heap_iterate (h, &find_request, &frc); | 293 | GNUNET_CONTAINER_DLL_remove (prd->rp_head, |
295 | if (frc.node != NULL) | 294 | prd->rp_tail, |
296 | GNUNET_CONTAINER_heap_remove_node (h, frc.node); | 295 | rp); |
296 | GNUNET_free (rp); | ||
297 | } | 297 | } |
298 | while (NULL != frc.node); | 298 | GNUNET_CONTAINER_heap_destroy (pp->heap); |
299 | return GNUNET_OK; | 299 | GNUNET_free (pp); |
300 | } | 300 | } |
301 | 301 | ||
302 | 302 | ||
303 | /** | 303 | /** |
304 | * Notify the plan about a request being done; destroy all entries | 304 | * Notify the plan about a request being done; destroy all entries |
305 | * associated with this request. Note that this implementation is | 305 | * associated with this request. |
306 | * currently terribly inefficient (O(n)) and could instead be done in | ||
307 | * O(1). But for now, I first want to see it work correctly... | ||
308 | * | 306 | * |
309 | * @param pr request that is done | 307 | * @param pr request that is done |
310 | */ | 308 | */ |
311 | void | 309 | void |
312 | GSF_plan_notify_request_done_ (const struct GSF_PendingRequest *pr) | 310 | GSF_plan_notify_request_done_ (const struct GSF_PendingRequest *pr) |
313 | { | 311 | { |
314 | GNUNET_CONTAINER_multihashmap_iterate (plans, | 312 | struct GSF_RequestPlan *rp; |
315 | &remove_request, | 313 | struct GSF_PendingRequestData *prd; |
316 | (void*) pr); | 314 | |
315 | while (NULL != (rp = prd->rp_head)) | ||
316 | { | ||
317 | prd = GSF_pending_request_get_data_ (rp->pr); | ||
318 | GNUNET_CONTAINER_heap_remove_node (rp->hn); | ||
319 | GNUNET_CONTAINER_DLL_remove (prd->rp_head, | ||
320 | prd->rp_tail, | ||
321 | rp); | ||
322 | GNUNET_free (rp); | ||
323 | } | ||
317 | } | 324 | } |
318 | 325 | ||
319 | 326 | ||