diff options
Diffstat (limited to 'src/include/gnunet_container_lib.h')
-rw-r--r-- | src/include/gnunet_container_lib.h | 784 |
1 files changed, 784 insertions, 0 deletions
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h new file mode 100644 index 000000000..255f68a89 --- /dev/null +++ b/src/include/gnunet_container_lib.h | |||
@@ -0,0 +1,784 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 2, or (at your | ||
8 | option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file include/gnunet_container_lib.h | ||
23 | * @brief container classes for GNUnet | ||
24 | * | ||
25 | * @author Christian Grothoff | ||
26 | * @author Nils Durner | ||
27 | */ | ||
28 | |||
29 | #ifndef GNUNET_CONTAINER_LIB_H | ||
30 | #define GNUNET_CONTAINER_LIB_H | ||
31 | |||
32 | /* add error and config prototypes */ | ||
33 | #include "gnunet_crypto_lib.h" | ||
34 | #include <extractor.h> | ||
35 | |||
36 | #ifdef __cplusplus | ||
37 | extern "C" | ||
38 | { | ||
39 | #if 0 /* keep Emacsens' auto-indent happy */ | ||
40 | } | ||
41 | #endif | ||
42 | #endif | ||
43 | |||
44 | |||
45 | /* ******************* bloomfilter ***************** */ | ||
46 | |||
47 | /** | ||
48 | * @brief bloomfilter representation (opaque) | ||
49 | */ | ||
50 | struct GNUNET_CONTAINER_BloomFilter; | ||
51 | |||
52 | /** | ||
53 | * Iterator over HashCodes. | ||
54 | * | ||
55 | * @return GNUNET_YES if next was updated | ||
56 | * GNUNET_NO if there are no more entries | ||
57 | */ | ||
58 | typedef int (*GNUNET_HashCodeIterator) (GNUNET_HashCode * next, void *arg); | ||
59 | |||
60 | /** | ||
61 | * Load a bloom-filter from a file. | ||
62 | * @param filename the name of the file (or the prefix) | ||
63 | * @param size the size of the bloom-filter (number of | ||
64 | * bytes of storage space to use) | ||
65 | * @param k the number of GNUNET_CRYPTO_hash-functions to apply per | ||
66 | * element (number of bits set per element in the set) | ||
67 | * @return the bloomfilter | ||
68 | */ | ||
69 | struct GNUNET_CONTAINER_BloomFilter *GNUNET_CONTAINER_bloomfilter_load (const | ||
70 | char | ||
71 | *filename, | ||
72 | unsigned | ||
73 | int | ||
74 | size, | ||
75 | unsigned | ||
76 | int | ||
77 | k); | ||
78 | |||
79 | /** | ||
80 | * Create a bloom filter from raw bits. | ||
81 | * | ||
82 | * @param data the raw bits in memory (maybe NULL, | ||
83 | * in which case all bits should be considered | ||
84 | * to be zero). | ||
85 | * @param size the size of the bloom-filter (number of | ||
86 | * bytes of storage space to use); also size of data | ||
87 | * -- unless data is NULL. Must be a power of 2. | ||
88 | * @param k the number of GNUNET_CRYPTO_hash-functions to apply per | ||
89 | * element (number of bits set per element in the set) | ||
90 | * @return the bloomfilter | ||
91 | */ | ||
92 | struct GNUNET_CONTAINER_BloomFilter *GNUNET_CONTAINER_bloomfilter_init (const | ||
93 | char | ||
94 | *data, | ||
95 | unsigned | ||
96 | int | ||
97 | size, | ||
98 | unsigned | ||
99 | int | ||
100 | k); | ||
101 | |||
102 | /** | ||
103 | * Copy the raw data of this bloomfilter into | ||
104 | * the given data array. | ||
105 | * | ||
106 | * @param data where to write the data | ||
107 | * @param size the size of the given data array | ||
108 | * @return GNUNET_SYSERR if the data array of the wrong size | ||
109 | */ | ||
110 | int GNUNET_CONTAINER_bloomfilter_get_raw_data (struct | ||
111 | GNUNET_CONTAINER_BloomFilter | ||
112 | *bf, char *data, | ||
113 | unsigned int size); | ||
114 | |||
115 | /** | ||
116 | * Test if an element is in the filter. | ||
117 | * @param e the element | ||
118 | * @param bf the filter | ||
119 | * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not | ||
120 | */ | ||
121 | int GNUNET_CONTAINER_bloomfilter_test (struct GNUNET_CONTAINER_BloomFilter | ||
122 | *bf, const GNUNET_HashCode * e); | ||
123 | |||
124 | /** | ||
125 | * Add an element to the filter | ||
126 | * @param bf the filter | ||
127 | * @param e the element | ||
128 | */ | ||
129 | void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter | ||
130 | *bf, const GNUNET_HashCode * e); | ||
131 | |||
132 | /** | ||
133 | * Remove an element from the filter. | ||
134 | * @param bf the filter | ||
135 | * @param e the element to remove | ||
136 | */ | ||
137 | void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter | ||
138 | *bf, const GNUNET_HashCode * e); | ||
139 | |||
140 | /** | ||
141 | * Free the space associcated with a filter | ||
142 | * in memory, flush to drive if needed (do not | ||
143 | * free the space on the drive) | ||
144 | * @param bf the filter | ||
145 | */ | ||
146 | void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter | ||
147 | *bf); | ||
148 | |||
149 | /** | ||
150 | * Reset a bloom filter to empty. | ||
151 | * @param bf the filter | ||
152 | */ | ||
153 | void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter | ||
154 | *bf); | ||
155 | |||
156 | /** | ||
157 | * Or the entries of the given raw data array with the | ||
158 | * data of the given bloom filter. Assumes that | ||
159 | * the size of the data array and the current filter | ||
160 | * match. | ||
161 | * @param bf the filter | ||
162 | */ | ||
163 | int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, | ||
164 | const char *data, unsigned int size); | ||
165 | |||
166 | /** | ||
167 | * Resize a bloom filter. Note that this operation | ||
168 | * is pretty costly. Essentially, the bloom filter | ||
169 | * needs to be completely re-build. | ||
170 | * | ||
171 | * @param bf the filter | ||
172 | * @param iterator an iterator over all elements stored in the BF | ||
173 | * @param iterator_arg argument to the iterator function | ||
174 | * @param size the new size for the filter | ||
175 | * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element | ||
176 | */ | ||
177 | void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter | ||
178 | *bf, | ||
179 | GNUNET_HashCodeIterator iterator, | ||
180 | void *iterator_arg, | ||
181 | unsigned int size, unsigned int k); | ||
182 | |||
183 | /* ****************** metadata ******************* */ | ||
184 | |||
185 | /** | ||
186 | * Meta data to associate with a file, directory or namespace. | ||
187 | */ | ||
188 | struct GNUNET_CONTAINER_MetaData; | ||
189 | |||
190 | /** | ||
191 | * Iterator over meta data. | ||
192 | * @return GNUNET_OK to continue to iterate, GNUNET_SYSERR to abort | ||
193 | */ | ||
194 | typedef int (*GNUNET_CONTAINER_MetaDataProcessor) (EXTRACTOR_KeywordType type, | ||
195 | const char *data, | ||
196 | void *closure); | ||
197 | |||
198 | /** | ||
199 | * Create a fresh MetaData token. | ||
200 | */ | ||
201 | struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_create (void); | ||
202 | |||
203 | /** | ||
204 | * Duplicate a MetaData token. | ||
205 | */ | ||
206 | struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_duplicate (const | ||
207 | struct | ||
208 | GNUNET_CONTAINER_MetaData | ||
209 | *meta); | ||
210 | |||
211 | /** | ||
212 | * Free meta data. | ||
213 | */ | ||
214 | void GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData | ||
215 | *md); | ||
216 | |||
217 | /** | ||
218 | * Test if two MDs are equal. | ||
219 | */ | ||
220 | int GNUNET_CONTAINER_meta_data_test_equal (const struct | ||
221 | GNUNET_CONTAINER_MetaData *md1, | ||
222 | const struct | ||
223 | GNUNET_CONTAINER_MetaData *md2); | ||
224 | |||
225 | |||
226 | /** | ||
227 | * Extend metadata. | ||
228 | * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists | ||
229 | */ | ||
230 | int GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md, | ||
231 | EXTRACTOR_KeywordType type, | ||
232 | const char *data); | ||
233 | |||
234 | /** | ||
235 | * Remove an item. | ||
236 | * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md | ||
237 | */ | ||
238 | int GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md, | ||
239 | EXTRACTOR_KeywordType type, | ||
240 | const char *data); | ||
241 | |||
242 | /** | ||
243 | * Add the current time as the publication date | ||
244 | * to the meta-data. | ||
245 | */ | ||
246 | void GNUNET_CONTAINER_meta_data_add_publication_date (struct | ||
247 | GNUNET_CONTAINER_MetaData | ||
248 | *md); | ||
249 | |||
250 | /** | ||
251 | * Iterate over MD entries, excluding thumbnails. | ||
252 | * | ||
253 | * @return number of entries | ||
254 | */ | ||
255 | int GNUNET_CONTAINER_meta_data_get_contents (const struct | ||
256 | GNUNET_CONTAINER_MetaData *md, | ||
257 | GNUNET_CONTAINER_MetaDataProcessor | ||
258 | iterator, void *closure); | ||
259 | |||
260 | /** | ||
261 | * Get the first MD entry of the given type. | ||
262 | * @return NULL if we do not have any such entry, | ||
263 | * otherwise client is responsible for freeing the value! | ||
264 | */ | ||
265 | char *GNUNET_CONTAINER_meta_data_get_by_type (const struct | ||
266 | GNUNET_CONTAINER_MetaData *md, | ||
267 | EXTRACTOR_KeywordType type); | ||
268 | |||
269 | /** | ||
270 | * Get the first matching MD entry of the given types. | ||
271 | * @paarm ... -1-terminated list of types | ||
272 | * @return NULL if we do not have any such entry, | ||
273 | * otherwise client is responsible for freeing the value! | ||
274 | */ | ||
275 | char *GNUNET_CONTAINER_meta_data_get_first_by_types (const struct | ||
276 | GNUNET_CONTAINER_MetaData | ||
277 | *md, ...); | ||
278 | |||
279 | /** | ||
280 | * Get a thumbnail from the meta-data (if present). | ||
281 | * | ||
282 | * @param thumb will be set to the thumbnail data. Must be | ||
283 | * freed by the caller! | ||
284 | * @return number of bytes in thumbnail, 0 if not available | ||
285 | */ | ||
286 | size_t GNUNET_CONTAINER_meta_data_get_thumbnail (const struct | ||
287 | GNUNET_CONTAINER_MetaData | ||
288 | *md, unsigned char **thumb); | ||
289 | |||
290 | /** | ||
291 | * Extract meta-data from a file. | ||
292 | * | ||
293 | * @return GNUNET_SYSERR on error, otherwise the number | ||
294 | * of meta-data items obtained | ||
295 | */ | ||
296 | int GNUNET_CONTAINER_meta_data_extract_from_file (struct | ||
297 | GNUNET_CONTAINER_MetaData | ||
298 | *md, const char *filename, | ||
299 | EXTRACTOR_ExtractorList * | ||
300 | extractors); | ||
301 | |||
302 | enum GNUNET_CONTAINER_MetaDataSerializationOptions | ||
303 | { | ||
304 | GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = GNUNET_NO, | ||
305 | GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = GNUNET_YES, | ||
306 | GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2 | ||
307 | }; | ||
308 | |||
309 | |||
310 | |||
311 | /** | ||
312 | * Serialize meta-data to target. | ||
313 | * | ||
314 | * @param size maximum number of bytes available | ||
315 | * @param opt is it ok to just write SOME of the | ||
316 | * meta-data to match the size constraint, | ||
317 | * possibly discarding some data? | ||
318 | * @return number of bytes written on success, | ||
319 | * GNUNET_SYSERR on error (typically: not enough | ||
320 | * space) | ||
321 | */ | ||
322 | int GNUNET_CONTAINER_meta_data_serialize (const struct | ||
323 | GNUNET_CONTAINER_MetaData *md, | ||
324 | char *target, unsigned int size, | ||
325 | enum | ||
326 | GNUNET_CONTAINER_MetaDataSerializationOptions | ||
327 | opt); | ||
328 | |||
329 | /** | ||
330 | * Compute size of the meta-data in | ||
331 | * serialized form. | ||
332 | * @param opt is it ok to just write SOME of the | ||
333 | * meta-data to match the size constraint, | ||
334 | * possibly discarding some data? | ||
335 | */ | ||
336 | unsigned int GNUNET_CONTAINER_meta_data_get_serialized_size (const struct | ||
337 | GNUNET_CONTAINER_MetaData | ||
338 | *md, | ||
339 | enum | ||
340 | GNUNET_CONTAINER_MetaDataSerializationOptions | ||
341 | opt); | ||
342 | |||
343 | /** | ||
344 | * Deserialize meta-data. Initializes md. | ||
345 | * @param size number of bytes available | ||
346 | * @return MD on success, NULL on error (i.e. | ||
347 | * bad format) | ||
348 | */ | ||
349 | struct GNUNET_CONTAINER_MetaData | ||
350 | *GNUNET_CONTAINER_meta_data_deserialize (const char *input, | ||
351 | unsigned int size); | ||
352 | |||
353 | /** | ||
354 | * Does the meta-data claim that this is a directory? | ||
355 | * Checks if the mime-type is that of a GNUnet directory. | ||
356 | * | ||
357 | * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if | ||
358 | * we have no mime-type information (treat as 'GNUNET_NO') | ||
359 | */ | ||
360 | int GNUNET_CONTAINER_meta_data_test_for_directory (const struct | ||
361 | GNUNET_CONTAINER_MetaData | ||
362 | *md); | ||
363 | |||
364 | |||
365 | /* ******************************* HashMap **************************** */ | ||
366 | |||
367 | /** | ||
368 | * Opaque handle for a HashMap. | ||
369 | */ | ||
370 | struct GNUNET_CONTAINER_MultiHashMap; | ||
371 | |||
372 | /** | ||
373 | * Options for storing values in the HashMap. | ||
374 | */ | ||
375 | enum GNUNET_CONTAINER_MultiHashMapOption | ||
376 | { | ||
377 | /** | ||
378 | * If a value with the given key exists, replace it. | ||
379 | * Note that the old value would NOT be freed | ||
380 | * by replace (the application has to make sure that | ||
381 | * this happens if required). | ||
382 | */ | ||
383 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE, | ||
384 | |||
385 | /** | ||
386 | * Allow multiple values with the same key. | ||
387 | */ | ||
388 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, | ||
389 | |||
390 | /** | ||
391 | * There must only be one value per key; storing | ||
392 | * a value should fail if a value under the same | ||
393 | * key already exists. | ||
394 | */ | ||
395 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, | ||
396 | |||
397 | /** | ||
398 | * There must only be one value per key, but don't | ||
399 | * bother checking if a value already exists | ||
400 | * (faster than UNIQUE_ONLY; implemented just like | ||
401 | * MULTIPLE but this option documents better what | ||
402 | * is intended if UNIQUE is what is desired). | ||
403 | */ | ||
404 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST | ||
405 | }; | ||
406 | |||
407 | /** | ||
408 | * Iterator over HashCodes. | ||
409 | * | ||
410 | * @param key current key code | ||
411 | * @param value value in the hash map | ||
412 | * @param cls client-defined argument | ||
413 | * @return GNUNET_YES if we should continue to | ||
414 | * iterate, | ||
415 | * GNUNET_NO if not. | ||
416 | */ | ||
417 | typedef int (*GNUNET_CONTAINER_HashMapIterator) (const GNUNET_HashCode * key, | ||
418 | void *value, void *cls); | ||
419 | |||
420 | |||
421 | /** | ||
422 | * Create a multi hash map. | ||
423 | * | ||
424 | * @param map the map | ||
425 | * @param len initial size (map will grow as needed) | ||
426 | * @return NULL on error | ||
427 | */ | ||
428 | struct GNUNET_CONTAINER_MultiHashMap | ||
429 | *GNUNET_CONTAINER_multihashmap_create (unsigned int len); | ||
430 | |||
431 | /** | ||
432 | * Destroy a hash map. Will not free any values | ||
433 | * stored in the hash map! | ||
434 | * | ||
435 | * @param map the map | ||
436 | */ | ||
437 | void GNUNET_CONTAINER_multihashmap_destroy (struct | ||
438 | GNUNET_CONTAINER_MultiHashMap | ||
439 | *map); | ||
440 | |||
441 | /** | ||
442 | * Given a key find a value in the | ||
443 | * map matching the key. | ||
444 | * | ||
445 | * @param map the map | ||
446 | * @param key what to look for | ||
447 | * @return NULL if no value was found; note that | ||
448 | * this is indistinguishable from values that just | ||
449 | * happen to be NULL; use "contains" to test for | ||
450 | * key-value pairs with value NULL | ||
451 | */ | ||
452 | void *GNUNET_CONTAINER_multihashmap_get (const struct | ||
453 | GNUNET_CONTAINER_MultiHashMap *map, | ||
454 | const GNUNET_HashCode * key); | ||
455 | |||
456 | /** | ||
457 | * Remove the given key-value pair from the map. | ||
458 | * Note that if the key-value pair is in the map | ||
459 | * multiple times, only one of the pairs will be | ||
460 | * removed. | ||
461 | * | ||
462 | * @param map the map | ||
463 | * @param key key of the key-value pair | ||
464 | * @param value value of the key-value pair | ||
465 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | ||
466 | * is not in the map | ||
467 | */ | ||
468 | int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap | ||
469 | *map, const GNUNET_HashCode * key, | ||
470 | void *value); | ||
471 | |||
472 | /** | ||
473 | * Remove all entries for the given key from the map. | ||
474 | * Note that the values would not be "freed". | ||
475 | * | ||
476 | * @param map the map | ||
477 | * @param key identifies values to be removed | ||
478 | * @return number of values removed | ||
479 | */ | ||
480 | int GNUNET_CONTAINER_multihashmap_remove_all (struct | ||
481 | GNUNET_CONTAINER_MultiHashMap | ||
482 | *map, | ||
483 | const GNUNET_HashCode * key); | ||
484 | |||
485 | /** | ||
486 | * Check if the map contains any value under the given | ||
487 | * key (including values that are NULL). | ||
488 | * | ||
489 | * @param map the map | ||
490 | * @param key the key to test if a value exists for it | ||
491 | * @return GNUNET_YES if such a value exists, | ||
492 | * GNUNET_NO if not | ||
493 | */ | ||
494 | int GNUNET_CONTAINER_multihashmap_contains (const struct | ||
495 | GNUNET_CONTAINER_MultiHashMap | ||
496 | *map, | ||
497 | const GNUNET_HashCode * key); | ||
498 | |||
499 | /** | ||
500 | * Store a key-value pair in the map. | ||
501 | * | ||
502 | * @param map the map | ||
503 | * @param key key to use | ||
504 | * @param value value to use | ||
505 | * @param opt options for put | ||
506 | * @return GNUNET_OK on success, | ||
507 | * GNUNET_NO if a value was replaced (with REPLACE) | ||
508 | * GNUNET_SYSERR if UNIQUE_ONLY was the option and the | ||
509 | * value already exists | ||
510 | */ | ||
511 | int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap | ||
512 | *map, const GNUNET_HashCode * key, | ||
513 | void *value, | ||
514 | enum | ||
515 | GNUNET_CONTAINER_MultiHashMapOption | ||
516 | opt); | ||
517 | |||
518 | /** | ||
519 | * Get the number of key-value pairs in the map. | ||
520 | * | ||
521 | * @param map the map | ||
522 | * @return the number of key value pairs | ||
523 | */ | ||
524 | unsigned int GNUNET_CONTAINER_multihashmap_size (const struct | ||
525 | GNUNET_CONTAINER_MultiHashMap | ||
526 | *map); | ||
527 | |||
528 | |||
529 | /** | ||
530 | * Iterate over all entries in the map. | ||
531 | * | ||
532 | * @param map the map | ||
533 | * @param iterator function to call on each entry | ||
534 | * @param cls extra argument to it | ||
535 | * @return the number of key value pairs processed, | ||
536 | * GNUNET_SYSERR if it aborted iteration | ||
537 | */ | ||
538 | int GNUNET_CONTAINER_multihashmap_iterate (const struct | ||
539 | GNUNET_CONTAINER_MultiHashMap *map, | ||
540 | GNUNET_CONTAINER_HashMapIterator | ||
541 | iterator, void *cls); | ||
542 | |||
543 | /** | ||
544 | * Iterate over all entries in the map | ||
545 | * that match a particular key. | ||
546 | * | ||
547 | * @param map the map | ||
548 | * @param key key that the entries must correspond to | ||
549 | * @param iterator function to call on each entry | ||
550 | * @param cls extra argument to it | ||
551 | * @return the number of key value pairs processed, | ||
552 | * GNUNET_SYSERR if it aborted iteration | ||
553 | */ | ||
554 | int GNUNET_CONTAINER_multihashmap_get_multiple (const struct | ||
555 | GNUNET_CONTAINER_MultiHashMap | ||
556 | *map, | ||
557 | const GNUNET_HashCode * key, | ||
558 | GNUNET_CONTAINER_HashMapIterator | ||
559 | iterator, void *cls); | ||
560 | /** | ||
561 | * Returns the stored value of a random non-null entry | ||
562 | * in the hash table. Returns only the first value, does | ||
563 | * not go inside bucket linked list (yet). Runs with a | ||
564 | * worst case time of N, so it's not efficient in any way | ||
565 | * shape or form!!!!. | ||
566 | */ | ||
567 | void *GNUNET_CONTAINER_multihashmap_get_random (const struct | ||
568 | GNUNET_CONTAINER_MultiHashMap | ||
569 | *map); | ||
570 | |||
571 | |||
572 | |||
573 | |||
574 | /* ******************** doubly-linked list *************** */ | ||
575 | |||
576 | /** | ||
577 | * Insert an element into a DLL. Assumes | ||
578 | * that head, tail and element are structs | ||
579 | * with prev and next fields. | ||
580 | */ | ||
581 | #define GNUNET_CONTAINER_DLL_insert(head,tail,element) \ | ||
582 | (element)->next = (head); \ | ||
583 | (element)->prev = NULL; \ | ||
584 | if ((tail) == NULL) \ | ||
585 | (tail) = element; \ | ||
586 | else \ | ||
587 | (head)->prev = element; \ | ||
588 | (head) = (element); | ||
589 | |||
590 | /** | ||
591 | * Insert an element into a DLL after the given other | ||
592 | * element. Insert at the head if the other | ||
593 | * element is NULL. | ||
594 | */ | ||
595 | #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) \ | ||
596 | (element)->prev = (other); \ | ||
597 | if (NULL == other) \ | ||
598 | { \ | ||
599 | (element)->next = (head); \ | ||
600 | (head) = (element); \ | ||
601 | } \ | ||
602 | else \ | ||
603 | { \ | ||
604 | (element)->next = (other)->next; \ | ||
605 | (other)->next = (element); \ | ||
606 | } \ | ||
607 | if (NULL == (element)->next) \ | ||
608 | (tail) = (element); \ | ||
609 | else \ | ||
610 | (element)->next->prev = (element); | ||
611 | |||
612 | |||
613 | |||
614 | |||
615 | /** | ||
616 | * Remove an element from a DLL. Assumes | ||
617 | * that head, tail and element are structs | ||
618 | * with prev and next fields. | ||
619 | */ | ||
620 | #define GNUNET_CONTAINER_DLL_remove(head,tail,element) \ | ||
621 | if ((element)->prev == NULL) \ | ||
622 | (head) = (element)->next; \ | ||
623 | else \ | ||
624 | (element)->prev->next = (element)->next; \ | ||
625 | if ((element)->next == NULL) \ | ||
626 | (tail) = (element)->prev; \ | ||
627 | else \ | ||
628 | (element)->next->prev = (element)->prev; | ||
629 | |||
630 | |||
631 | |||
632 | /* ******************** Heap *************** */ | ||
633 | |||
634 | |||
635 | /** | ||
636 | * Cost by which elements in a heap can be ordered. | ||
637 | */ | ||
638 | typedef unsigned int GNUNET_CONTAINER_HeapCost; | ||
639 | |||
640 | /* | ||
641 | * Heap type, either max or min. Hopefully makes the | ||
642 | * implementation more useful. | ||
643 | */ | ||
644 | enum GNUNET_CONTAINER_HeapOrder | ||
645 | { | ||
646 | /** | ||
647 | * Heap with the maximum cost at the root. | ||
648 | */ | ||
649 | GNUNET_CONTAINER_HEAP_ORDER_MAX, | ||
650 | |||
651 | /** | ||
652 | * Heap with the minimum cost at the root. | ||
653 | */ | ||
654 | GNUNET_CONTAINER_HEAP_ORDER_MIN | ||
655 | }; | ||
656 | |||
657 | /** | ||
658 | * Handle to a Heap. | ||
659 | */ | ||
660 | struct GNUNET_CONTAINER_Heap; | ||
661 | |||
662 | /** | ||
663 | * Create a new heap. | ||
664 | * | ||
665 | * @param type should the minimum or the maximum element be the root | ||
666 | * @return NULL on error, otherwise a fresh heap | ||
667 | */ | ||
668 | struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum | ||
669 | GNUNET_CONTAINER_HeapOrder | ||
670 | type); | ||
671 | |||
672 | /** | ||
673 | * Free a heap | ||
674 | * | ||
675 | * @param h heap to free. | ||
676 | */ | ||
677 | void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h); | ||
678 | |||
679 | /** | ||
680 | * Function called on elements of a heap. | ||
681 | * | ||
682 | * @param cls closure | ||
683 | * @param element obj stored in heap | ||
684 | * @param cost cost of the element | ||
685 | * @return GNUNET_YES if we should continue to iterate, | ||
686 | * GNUNET_NO if not. | ||
687 | */ | ||
688 | typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls, | ||
689 | void *element, | ||
690 | GNUNET_CONTAINER_HeapCost cost); | ||
691 | /** | ||
692 | * Iterate over all entries in the map. | ||
693 | * | ||
694 | * @param heap the heap | ||
695 | * @param iterator function to call on each entry | ||
696 | * @param iterator_cls closure for iterator | ||
697 | * @return number of items handled | ||
698 | * GNUNET_SYSERR if iteration was aborted by iterator | ||
699 | */ | ||
700 | int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap, | ||
701 | GNUNET_CONTAINER_HeapIterator iterator, | ||
702 | void *iterator_cls); | ||
703 | |||
704 | |||
705 | /** | ||
706 | * Inserts a new item into the heap, item is always neighbor now. | ||
707 | * @param heap the heap | ||
708 | */ | ||
709 | int | ||
710 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, | ||
711 | void *element, GNUNET_CONTAINER_HeapCost cost); | ||
712 | |||
713 | /** | ||
714 | * Removes root of the tree, is remove max if a max heap and remove min | ||
715 | * if a min heap, returns the data stored at the node. | ||
716 | * | ||
717 | * @param heap the heap | ||
718 | * @return NULL if the heap is empty | ||
719 | */ | ||
720 | void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); | ||
721 | |||
722 | /** | ||
723 | * Returns element stored at root of tree, doesn't effect anything | ||
724 | * | ||
725 | * @param heap the heap | ||
726 | * @return NULL if the heap is empty | ||
727 | */ | ||
728 | void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap); | ||
729 | |||
730 | /** | ||
731 | * Removes any node from the tree based on the neighbor given, does | ||
732 | * not traverse the tree (backpointers) but may take more time due to | ||
733 | * percolation of nodes. | ||
734 | * @param heap the heap | ||
735 | */ | ||
736 | void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap, | ||
737 | void *element); | ||
738 | |||
739 | /** | ||
740 | * Updates the cost of any node in the tree | ||
741 | * | ||
742 | * @param heap the heap | ||
743 | * @param element the element for which the cost is updated | ||
744 | * @param new_cost new cost for the element | ||
745 | * @return WHAT? | ||
746 | */ | ||
747 | int | ||
748 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, | ||
749 | void *element, | ||
750 | GNUNET_CONTAINER_HeapCost new_cost); | ||
751 | |||
752 | /** | ||
753 | * Random walk of the tree, returns the data stored at the next random node | ||
754 | * in the walk. Calls callee with the data, or NULL if the tree is empty | ||
755 | * or some other problem crops up. | ||
756 | * | ||
757 | * @param heap the heap | ||
758 | * @return the next element from the random walk | ||
759 | */ | ||
760 | void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap | ||
761 | *heap); | ||
762 | |||
763 | /** | ||
764 | * Returns the current size of the heap | ||
765 | * | ||
766 | * @param heap the heap to get the size of | ||
767 | * @return number of elements in the heap | ||
768 | */ | ||
769 | unsigned int | ||
770 | GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap); | ||
771 | |||
772 | |||
773 | |||
774 | #if 0 /* keep Emacsens' auto-indent happy */ | ||
775 | { | ||
776 | #endif | ||
777 | #ifdef __cplusplus | ||
778 | } | ||
779 | #endif | ||
780 | |||
781 | |||
782 | /* ifndef GNUNET_CONTAINER_LIB_H */ | ||
783 | #endif | ||
784 | /* end of gnunet_container_lib.h */ | ||