aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_bloomfilter.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_bloomfilter.c')
-rw-r--r--src/util/container_bloomfilter.c539
1 files changed, 270 insertions, 269 deletions
diff --git a/src/util/container_bloomfilter.c b/src/util/container_bloomfilter.c
index 1bc559ba3..cb7984c3f 100644
--- a/src/util/container_bloomfilter.c
+++ b/src/util/container_bloomfilter.c
@@ -43,18 +43,19 @@
43#include "gnunet_util_lib.h" 43#include "gnunet_util_lib.h"
44 44
45#define LOG(kind, ...) \ 45#define LOG(kind, ...) \
46 GNUNET_log_from(kind, "util-container-bloomfilter", __VA_ARGS__) 46 GNUNET_log_from (kind, "util-container-bloomfilter", __VA_ARGS__)
47 47
48#define LOG_STRERROR(kind, syscall) \ 48#define LOG_STRERROR(kind, syscall) \
49 GNUNET_log_from_strerror(kind, "util-container-bloomfilter", syscall) 49 GNUNET_log_from_strerror (kind, "util-container-bloomfilter", syscall)
50 50
51#define LOG_STRERROR_FILE(kind, syscall, filename) \ 51#define LOG_STRERROR_FILE(kind, syscall, filename) \
52 GNUNET_log_from_strerror_file(kind, \ 52 GNUNET_log_from_strerror_file (kind, \
53 "util-container-bloomfilter", \ 53 "util-container-bloomfilter", \
54 syscall, \ 54 syscall, \
55 filename) 55 filename)
56 56
57struct GNUNET_CONTAINER_BloomFilter { 57struct GNUNET_CONTAINER_BloomFilter
58{
58 /** 59 /**
59 * The actual bloomfilter bit array 60 * The actual bloomfilter bit array
60 */ 61 */
@@ -89,7 +90,7 @@ struct GNUNET_CONTAINER_BloomFilter {
89 * @return addresses set per element in the bf 90 * @return addresses set per element in the bf
90 */ 91 */
91size_t 92size_t
92GNUNET_CONTAINER_bloomfilter_get_element_addresses( 93GNUNET_CONTAINER_bloomfilter_get_element_addresses (
93 const struct GNUNET_CONTAINER_BloomFilter *bf) 94 const struct GNUNET_CONTAINER_BloomFilter *bf)
94{ 95{
95 if (bf == NULL) 96 if (bf == NULL)
@@ -105,7 +106,7 @@ GNUNET_CONTAINER_bloomfilter_get_element_addresses(
105 * @return number of bytes used for the data of the bloom filter 106 * @return number of bytes used for the data of the bloom filter
106 */ 107 */
107size_t 108size_t
108GNUNET_CONTAINER_bloomfilter_get_size( 109GNUNET_CONTAINER_bloomfilter_get_size (
109 const struct GNUNET_CONTAINER_BloomFilter *bf) 110 const struct GNUNET_CONTAINER_BloomFilter *bf)
110{ 111{
111 if (bf == NULL) 112 if (bf == NULL)
@@ -121,12 +122,12 @@ GNUNET_CONTAINER_bloomfilter_get_size(
121 * @return copy of the bf 122 * @return copy of the bf
122 */ 123 */
123struct GNUNET_CONTAINER_BloomFilter * 124struct GNUNET_CONTAINER_BloomFilter *
124GNUNET_CONTAINER_bloomfilter_copy( 125GNUNET_CONTAINER_bloomfilter_copy (
125 const struct GNUNET_CONTAINER_BloomFilter *bf) 126 const struct GNUNET_CONTAINER_BloomFilter *bf)
126{ 127{
127 return GNUNET_CONTAINER_bloomfilter_init(bf->bitArray, 128 return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray,
128 bf->bitArraySize, 129 bf->bitArraySize,
129 bf->addressesPerElement); 130 bf->addressesPerElement);
130} 131}
131 132
132 133
@@ -138,7 +139,7 @@ GNUNET_CONTAINER_bloomfilter_copy(
138 * @param bitIdx which bit to set 139 * @param bitIdx which bit to set
139 */ 140 */
140static void 141static void
141setBit(char *bitArray, unsigned int bitIdx) 142setBit (char *bitArray, unsigned int bitIdx)
142{ 143{
143 size_t arraySlot; 144 size_t arraySlot;
144 unsigned int targetBit; 145 unsigned int targetBit;
@@ -156,7 +157,7 @@ setBit(char *bitArray, unsigned int bitIdx)
156 * @param bitIdx which bit to unset 157 * @param bitIdx which bit to unset
157 */ 158 */
158static void 159static void
159clearBit(char *bitArray, unsigned int bitIdx) 160clearBit (char *bitArray, unsigned int bitIdx)
160{ 161{
161 size_t slot; 162 size_t slot;
162 unsigned int targetBit; 163 unsigned int targetBit;
@@ -174,7 +175,7 @@ clearBit(char *bitArray, unsigned int bitIdx)
174 * @return GNUNET_YES if the bit is set, GNUNET_NO if not. 175 * @return GNUNET_YES if the bit is set, GNUNET_NO if not.
175 */ 176 */
176static int 177static int
177testBit(char *bitArray, unsigned int bitIdx) 178testBit (char *bitArray, unsigned int bitIdx)
178{ 179{
179 size_t slot; 180 size_t slot;
180 unsigned int targetBit; 181 unsigned int targetBit;
@@ -197,9 +198,9 @@ testBit(char *bitArray, unsigned int bitIdx)
197 * @param fh A file to keep the 4 bit address usage counters in 198 * @param fh A file to keep the 4 bit address usage counters in
198 */ 199 */
199static void 200static void
200incrementBit(char *bitArray, 201incrementBit (char *bitArray,
201 unsigned int bitIdx, 202 unsigned int bitIdx,
202 const struct GNUNET_DISK_FileHandle *fh) 203 const struct GNUNET_DISK_FileHandle *fh)
203{ 204{
204 off_t fileSlot; 205 off_t fileSlot;
205 unsigned char value; 206 unsigned char value;
@@ -207,34 +208,34 @@ incrementBit(char *bitArray,
207 unsigned int low; 208 unsigned int low;
208 unsigned int targetLoc; 209 unsigned int targetLoc;
209 210
210 setBit(bitArray, bitIdx); 211 setBit (bitArray, bitIdx);
211 if (GNUNET_DISK_handle_invalid(fh)) 212 if (GNUNET_DISK_handle_invalid (fh))
212 return; 213 return;
213 /* Update the counter file on disk */ 214 /* Update the counter file on disk */
214 fileSlot = bitIdx / 2; 215 fileSlot = bitIdx / 2;
215 targetLoc = bitIdx % 2; 216 targetLoc = bitIdx % 2;
216 217
217 GNUNET_assert(fileSlot == 218 GNUNET_assert (fileSlot ==
218 GNUNET_DISK_file_seek(fh, fileSlot, GNUNET_DISK_SEEK_SET)); 219 GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
219 if (1 != GNUNET_DISK_file_read(fh, &value, 1)) 220 if (1 != GNUNET_DISK_file_read (fh, &value, 1))
220 value = 0; 221 value = 0;
221 low = value & 0xF; 222 low = value & 0xF;
222 high = (value & (~0xF)) >> 4; 223 high = (value & (~0xF)) >> 4;
223 224
224 if (targetLoc == 0) 225 if (targetLoc == 0)
225 { 226 {
226 if (low < 0xF) 227 if (low < 0xF)
227 low++; 228 low++;
228 } 229 }
229 else 230 else
230 { 231 {
231 if (high < 0xF) 232 if (high < 0xF)
232 high++; 233 high++;
233 } 234 }
234 value = ((high << 4) | low); 235 value = ((high << 4) | low);
235 GNUNET_assert(fileSlot == 236 GNUNET_assert (fileSlot ==
236 GNUNET_DISK_file_seek(fh, fileSlot, GNUNET_DISK_SEEK_SET)); 237 GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
237 GNUNET_assert(1 == GNUNET_DISK_file_write(fh, &value, 1)); 238 GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
238} 239}
239 240
240/** 241/**
@@ -246,9 +247,9 @@ incrementBit(char *bitArray,
246 * @param fh A file to keep the 4bit address usage counters in 247 * @param fh A file to keep the 4bit address usage counters in
247 */ 248 */
248static void 249static void
249decrementBit(char *bitArray, 250decrementBit (char *bitArray,
250 unsigned int bitIdx, 251 unsigned int bitIdx,
251 const struct GNUNET_DISK_FileHandle *fh) 252 const struct GNUNET_DISK_FileHandle *fh)
252{ 253{
253 off_t fileslot; 254 off_t fileslot;
254 unsigned char value; 255 unsigned char value;
@@ -256,49 +257,49 @@ decrementBit(char *bitArray,
256 unsigned int low; 257 unsigned int low;
257 unsigned int targetLoc; 258 unsigned int targetLoc;
258 259
259 if (GNUNET_DISK_handle_invalid(fh)) 260 if (GNUNET_DISK_handle_invalid (fh))
260 return; /* cannot decrement! */ 261 return; /* cannot decrement! */
261 /* Each char slot in the counter file holds two 4 bit counters */ 262 /* Each char slot in the counter file holds two 4 bit counters */
262 fileslot = bitIdx / 2; 263 fileslot = bitIdx / 2;
263 targetLoc = bitIdx % 2; 264 targetLoc = bitIdx % 2;
264 if (GNUNET_SYSERR == 265 if (GNUNET_SYSERR ==
265 GNUNET_DISK_file_seek(fh, fileslot, GNUNET_DISK_SEEK_SET)) 266 GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET))
266 { 267 {
267 GNUNET_log_strerror(GNUNET_ERROR_TYPE_ERROR, "seek"); 268 GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek");
268 return; 269 return;
269 } 270 }
270 if (1 != GNUNET_DISK_file_read(fh, &value, 1)) 271 if (1 != GNUNET_DISK_file_read (fh, &value, 1))
271 value = 0; 272 value = 0;
272 low = value & 0xF; 273 low = value & 0xF;
273 high = (value & 0xF0) >> 4; 274 high = (value & 0xF0) >> 4;
274 275
275 /* decrement, but once we have reached the max, never go back! */ 276 /* decrement, but once we have reached the max, never go back! */
276 if (targetLoc == 0) 277 if (targetLoc == 0)
278 {
279 if ((low > 0) && (low < 0xF))
280 low--;
281 if (low == 0)
277 { 282 {
278 if ((low > 0) && (low < 0xF)) 283 clearBit (bitArray, bitIdx);
279 low--;
280 if (low == 0)
281 {
282 clearBit(bitArray, bitIdx);
283 }
284 } 284 }
285 }
285 else 286 else
287 {
288 if ((high > 0) && (high < 0xF))
289 high--;
290 if (high == 0)
286 { 291 {
287 if ((high > 0) && (high < 0xF)) 292 clearBit (bitArray, bitIdx);
288 high--;
289 if (high == 0)
290 {
291 clearBit(bitArray, bitIdx);
292 }
293 } 293 }
294 }
294 value = ((high << 4) | low); 295 value = ((high << 4) | low);
295 if (GNUNET_SYSERR == 296 if (GNUNET_SYSERR ==
296 GNUNET_DISK_file_seek(fh, fileslot, GNUNET_DISK_SEEK_SET)) 297 GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET))
297 { 298 {
298 GNUNET_log_strerror(GNUNET_ERROR_TYPE_ERROR, "seek"); 299 GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek");
299 return; 300 return;
300 } 301 }
301 GNUNET_assert(1 == GNUNET_DISK_file_write(fh, &value, 1)); 302 GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
302} 303}
303 304
304#define BUFFSIZE 65536 305#define BUFFSIZE 65536
@@ -311,33 +312,33 @@ decrementBit(char *bitArray,
311 * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise 312 * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise
312 */ 313 */
313static int 314static int
314make_empty_file(const struct GNUNET_DISK_FileHandle *fh, size_t size) 315make_empty_file (const struct GNUNET_DISK_FileHandle *fh, size_t size)
315{ 316{
316 char buffer[BUFFSIZE]; 317 char buffer[BUFFSIZE];
317 size_t bytesleft = size; 318 size_t bytesleft = size;
318 int res = 0; 319 int res = 0;
319 320
320 if (GNUNET_DISK_handle_invalid(fh)) 321 if (GNUNET_DISK_handle_invalid (fh))
321 return GNUNET_SYSERR; 322 return GNUNET_SYSERR;
322 memset(buffer, 0, sizeof(buffer)); 323 memset (buffer, 0, sizeof(buffer));
323 GNUNET_DISK_file_seek(fh, 0, GNUNET_DISK_SEEK_SET); 324 GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET);
324 while (bytesleft > 0) 325 while (bytesleft > 0)
326 {
327 if (bytesleft > sizeof(buffer))
325 { 328 {
326 if (bytesleft > sizeof(buffer)) 329 res = GNUNET_DISK_file_write (fh, buffer, sizeof(buffer));
327 { 330 if (res >= 0)
328 res = GNUNET_DISK_file_write(fh, buffer, sizeof(buffer)); 331 bytesleft -= res;
329 if (res >= 0)
330 bytesleft -= res;
331 }
332 else
333 {
334 res = GNUNET_DISK_file_write(fh, buffer, bytesleft);
335 if (res >= 0)
336 bytesleft -= res;
337 }
338 if (GNUNET_SYSERR == res)
339 return GNUNET_SYSERR;
340 } 332 }
333 else
334 {
335 res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
336 if (res >= 0)
337 bytesleft -= res;
338 }
339 if (GNUNET_SYSERR == res)
340 return GNUNET_SYSERR;
341 }
341 return GNUNET_OK; 342 return GNUNET_OK;
342} 343}
343 344
@@ -368,10 +369,10 @@ typedef int (*BitIterator) (void *cls,
368 * @param key the key for which we iterate over the BF bits 369 * @param key the key for which we iterate over the BF bits
369 */ 370 */
370static void 371static void
371iterateBits(const struct GNUNET_CONTAINER_BloomFilter *bf, 372iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
372 BitIterator callback, 373 BitIterator callback,
373 void *arg, 374 void *arg,
374 const struct GNUNET_HashCode *key) 375 const struct GNUNET_HashCode *key)
375{ 376{
376 struct GNUNET_HashCode tmp[2]; 377 struct GNUNET_HashCode tmp[2];
377 int bitCount; 378 int bitCount;
@@ -381,32 +382,32 @@ iterateBits(const struct GNUNET_CONTAINER_BloomFilter *bf,
381 bitCount = bf->addressesPerElement; 382 bitCount = bf->addressesPerElement;
382 tmp[0] = *key; 383 tmp[0] = *key;
383 round = 0; 384 round = 0;
384 GNUNET_assert(bf->bitArraySize > 0); 385 GNUNET_assert (bf->bitArraySize > 0);
385 GNUNET_assert(bf->bitArraySize * 8LL > bf->bitArraySize); 386 GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize);
386 while (bitCount > 0) 387 while (bitCount > 0)
388 {
389 while (slot < (sizeof(struct GNUNET_HashCode) / sizeof(uint32_t)))
390 {
391 if (GNUNET_YES !=
392 callback (arg,
393 bf,
394 ntohl ((((uint32_t *) &tmp[round & 1])[slot]))
395 % ((bf->bitArraySize * 8LL))))
396 return;
397 slot++;
398 bitCount--;
399 if (bitCount == 0)
400 break;
401 }
402 if (bitCount > 0)
387 { 403 {
388 while (slot < (sizeof(struct GNUNET_HashCode) / sizeof(uint32_t))) 404 GNUNET_CRYPTO_hash (&tmp[round & 1],
389 { 405 sizeof(struct GNUNET_HashCode),
390 if (GNUNET_YES != 406 &tmp[(round + 1) & 1]);
391 callback(arg, 407 round++;
392 bf, 408 slot = 0;
393 ntohl((((uint32_t *)&tmp[round & 1])[slot])) %
394 ((bf->bitArraySize * 8LL))))
395 return;
396 slot++;
397 bitCount--;
398 if (bitCount == 0)
399 break;
400 }
401 if (bitCount > 0)
402 {
403 GNUNET_CRYPTO_hash(&tmp[round & 1],
404 sizeof(struct GNUNET_HashCode),
405 &tmp[(round + 1) & 1]);
406 round++;
407 slot = 0;
408 }
409 } 409 }
410 }
410} 411}
411 412
412 413
@@ -419,13 +420,13 @@ iterateBits(const struct GNUNET_CONTAINER_BloomFilter *bf,
419 * @return GNUNET_YES 420 * @return GNUNET_YES
420 */ 421 */
421static int 422static int
422incrementBitCallback(void *cls, 423incrementBitCallback (void *cls,
423 const struct GNUNET_CONTAINER_BloomFilter *bf, 424 const struct GNUNET_CONTAINER_BloomFilter *bf,
424 unsigned int bit) 425 unsigned int bit)
425{ 426{
426 struct GNUNET_CONTAINER_BloomFilter *b = cls; 427 struct GNUNET_CONTAINER_BloomFilter *b = cls;
427 428
428 incrementBit(b->bitArray, bit, bf->fh); 429 incrementBit (b->bitArray, bit, bf->fh);
429 return GNUNET_YES; 430 return GNUNET_YES;
430} 431}
431 432
@@ -439,13 +440,13 @@ incrementBitCallback(void *cls,
439 * @return GNUNET_YES 440 * @return GNUNET_YES
440 */ 441 */
441static int 442static int
442decrementBitCallback(void *cls, 443decrementBitCallback (void *cls,
443 const struct GNUNET_CONTAINER_BloomFilter *bf, 444 const struct GNUNET_CONTAINER_BloomFilter *bf,
444 unsigned int bit) 445 unsigned int bit)
445{ 446{
446 struct GNUNET_CONTAINER_BloomFilter *b = cls; 447 struct GNUNET_CONTAINER_BloomFilter *b = cls;
447 448
448 decrementBit(b->bitArray, bit, bf->fh); 449 decrementBit (b->bitArray, bit, bf->fh);
449 return GNUNET_YES; 450 return GNUNET_YES;
450} 451}
451 452
@@ -459,17 +460,17 @@ decrementBitCallback(void *cls,
459 * @return YES if the bit is set, NO if not 460 * @return YES if the bit is set, NO if not
460 */ 461 */
461static int 462static int
462testBitCallback(void *cls, 463testBitCallback (void *cls,
463 const struct GNUNET_CONTAINER_BloomFilter *bf, 464 const struct GNUNET_CONTAINER_BloomFilter *bf,
464 unsigned int bit) 465 unsigned int bit)
465{ 466{
466 int *arg = cls; 467 int *arg = cls;
467 468
468 if (GNUNET_NO == testBit(bf->bitArray, bit)) 469 if (GNUNET_NO == testBit (bf->bitArray, bit))
469 { 470 {
470 *arg = GNUNET_NO; 471 *arg = GNUNET_NO;
471 return GNUNET_NO; 472 return GNUNET_NO;
472 } 473 }
473 return GNUNET_YES; 474 return GNUNET_YES;
474} 475}
475 476
@@ -487,9 +488,9 @@ testBitCallback(void *cls,
487 * @return the bloomfilter 488 * @return the bloomfilter
488 */ 489 */
489struct GNUNET_CONTAINER_BloomFilter * 490struct GNUNET_CONTAINER_BloomFilter *
490GNUNET_CONTAINER_bloomfilter_load(const char *filename, 491GNUNET_CONTAINER_bloomfilter_load (const char *filename,
491 size_t size, 492 size_t size,
492 unsigned int k) 493 unsigned int k)
493{ 494{
494 struct GNUNET_CONTAINER_BloomFilter *bf; 495 struct GNUNET_CONTAINER_BloomFilter *bf;
495 char *rbuff; 496 char *rbuff;
@@ -499,7 +500,7 @@ GNUNET_CONTAINER_bloomfilter_load(const char *filename,
499 off_t fsize; 500 off_t fsize;
500 int must_read; 501 int must_read;
501 502
502 GNUNET_assert(NULL != filename); 503 GNUNET_assert (NULL != filename);
503 if ((k == 0) || (size == 0)) 504 if ((k == 0) || (size == 0))
504 return NULL; 505 return NULL;
505 if (size < BUFFSIZE) 506 if (size < BUFFSIZE)
@@ -509,115 +510,115 @@ GNUNET_CONTAINER_bloomfilter_load(const char *filename,
509 ui *= 2; 510 ui *= 2;
510 size = ui; /* make sure it's a power of 2 */ 511 size = ui; /* make sure it's a power of 2 */
511 512
512 bf = GNUNET_new(struct GNUNET_CONTAINER_BloomFilter); 513 bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
513 /* Try to open a bloomfilter file */ 514 /* Try to open a bloomfilter file */
514 if (GNUNET_YES == GNUNET_DISK_file_test(filename)) 515 if (GNUNET_YES == GNUNET_DISK_file_test (filename))
515 bf->fh = GNUNET_DISK_file_open(filename, 516 bf->fh = GNUNET_DISK_file_open (filename,
516 GNUNET_DISK_OPEN_READWRITE, 517 GNUNET_DISK_OPEN_READWRITE,
517 GNUNET_DISK_PERM_USER_READ | 518 GNUNET_DISK_PERM_USER_READ
518 GNUNET_DISK_PERM_USER_WRITE); 519 | GNUNET_DISK_PERM_USER_WRITE);
519 if (NULL != bf->fh) 520 if (NULL != bf->fh)
521 {
522 /* file existed, try to read it! */
523 must_read = GNUNET_YES;
524 if (GNUNET_OK != GNUNET_DISK_file_handle_size (bf->fh, &fsize))
525 {
526 GNUNET_DISK_file_close (bf->fh);
527 GNUNET_free (bf);
528 return NULL;
529 }
530 if (0 == fsize)
520 { 531 {
521 /* file existed, try to read it! */ 532 /* found existing empty file, just overwrite */
522 must_read = GNUNET_YES; 533 if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
523 if (GNUNET_OK != GNUNET_DISK_file_handle_size(bf->fh, &fsize)) 534 {
524 { 535 GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, "write");
525 GNUNET_DISK_file_close(bf->fh); 536 GNUNET_DISK_file_close (bf->fh);
526 GNUNET_free(bf); 537 GNUNET_free (bf);
527 return NULL; 538 return NULL;
528 } 539 }
529 if (0 == fsize)
530 {
531 /* found existing empty file, just overwrite */
532 if (GNUNET_OK != make_empty_file(bf->fh, size * 4LL))
533 {
534 GNUNET_log_strerror(GNUNET_ERROR_TYPE_WARNING, "write");
535 GNUNET_DISK_file_close(bf->fh);
536 GNUNET_free(bf);
537 return NULL;
538 }
539 }
540 else if (fsize != ((off_t)size) * 4LL)
541 {
542 GNUNET_log(
543 GNUNET_ERROR_TYPE_ERROR,
544 _(
545 "Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
546 (unsigned long long)(size * 4LL),
547 (unsigned long long)fsize);
548 GNUNET_DISK_file_close(bf->fh);
549 GNUNET_free(bf);
550 return NULL;
551 }
552 } 540 }
541 else if (fsize != ((off_t) size) * 4LL)
542 {
543 GNUNET_log (
544 GNUNET_ERROR_TYPE_ERROR,
545 _ (
546 "Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
547 (unsigned long long) (size * 4LL),
548 (unsigned long long) fsize);
549 GNUNET_DISK_file_close (bf->fh);
550 GNUNET_free (bf);
551 return NULL;
552 }
553 }
553 else 554 else
555 {
556 /* file did not exist, don't read, just create */
557 must_read = GNUNET_NO;
558 bf->fh = GNUNET_DISK_file_open (filename,
559 GNUNET_DISK_OPEN_CREATE
560 | GNUNET_DISK_OPEN_READWRITE,
561 GNUNET_DISK_PERM_USER_READ
562 | GNUNET_DISK_PERM_USER_WRITE);
563 if (NULL == bf->fh)
554 { 564 {
555 /* file did not exist, don't read, just create */ 565 GNUNET_free (bf);
556 must_read = GNUNET_NO; 566 return NULL;
557 bf->fh = GNUNET_DISK_file_open(filename,
558 GNUNET_DISK_OPEN_CREATE |
559 GNUNET_DISK_OPEN_READWRITE,
560 GNUNET_DISK_PERM_USER_READ |
561 GNUNET_DISK_PERM_USER_WRITE);
562 if (NULL == bf->fh)
563 {
564 GNUNET_free(bf);
565 return NULL;
566 }
567 if (GNUNET_OK != make_empty_file(bf->fh, size * 4LL))
568 {
569 GNUNET_log_strerror(GNUNET_ERROR_TYPE_WARNING, "write");
570 GNUNET_DISK_file_close(bf->fh);
571 GNUNET_free(bf);
572 return NULL;
573 }
574 } 567 }
575 bf->filename = GNUNET_strdup(filename); 568 if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
576 /* Alloc block */
577 bf->bitArray = GNUNET_malloc_large(size);
578 if (NULL == bf->bitArray)
579 { 569 {
580 if (NULL != bf->fh) 570 GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, "write");
581 GNUNET_DISK_file_close(bf->fh); 571 GNUNET_DISK_file_close (bf->fh);
582 GNUNET_free(bf->filename); 572 GNUNET_free (bf);
583 GNUNET_free(bf);
584 return NULL; 573 return NULL;
585 } 574 }
575 }
576 bf->filename = GNUNET_strdup (filename);
577 /* Alloc block */
578 bf->bitArray = GNUNET_malloc_large (size);
579 if (NULL == bf->bitArray)
580 {
581 if (NULL != bf->fh)
582 GNUNET_DISK_file_close (bf->fh);
583 GNUNET_free (bf->filename);
584 GNUNET_free (bf);
585 return NULL;
586 }
586 bf->bitArraySize = size; 587 bf->bitArraySize = size;
587 bf->addressesPerElement = k; 588 bf->addressesPerElement = k;
588 if (GNUNET_YES != must_read) 589 if (GNUNET_YES != must_read)
589 return bf; /* already done! */ 590 return bf; /* already done! */
590 /* Read from the file what bits we can */ 591 /* Read from the file what bits we can */
591 rbuff = GNUNET_malloc(BUFFSIZE); 592 rbuff = GNUNET_malloc (BUFFSIZE);
592 pos = 0; 593 pos = 0;
593 while (pos < ((off_t)size) * 8LL) 594 while (pos < ((off_t) size) * 8LL)
595 {
596 int res;
597
598 res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE);
599 if (res == -1)
594 { 600 {
595 int res; 601 LOG_STRERROR_FILE (GNUNET_ERROR_TYPE_WARNING, "read", bf->filename);
596 602 GNUNET_free (rbuff);
597 res = GNUNET_DISK_file_read(bf->fh, rbuff, BUFFSIZE); 603 GNUNET_free (bf->filename);
598 if (res == -1) 604 GNUNET_DISK_file_close (bf->fh);
599 { 605 GNUNET_free (bf);
600 LOG_STRERROR_FILE(GNUNET_ERROR_TYPE_WARNING, "read", bf->filename); 606 return NULL;
601 GNUNET_free(rbuff); 607 }
602 GNUNET_free(bf->filename); 608 if (res == 0)
603 GNUNET_DISK_file_close(bf->fh); 609 break; /* is ok! we just did not use that many bits yet */
604 GNUNET_free(bf); 610 for (i = 0; i < res; i++)
605 return NULL; 611 {
606 } 612 if ((rbuff[i] & 0x0F) != 0)
607 if (res == 0) 613 setBit (bf->bitArray, pos + i * 2);
608 break; /* is ok! we just did not use that many bits yet */ 614 if ((rbuff[i] & 0xF0) != 0)
609 for (i = 0; i < res; i++) 615 setBit (bf->bitArray, pos + i * 2 + 1);
610 {
611 if ((rbuff[i] & 0x0F) != 0)
612 setBit(bf->bitArray, pos + i * 2);
613 if ((rbuff[i] & 0xF0) != 0)
614 setBit(bf->bitArray, pos + i * 2 + 1);
615 }
616 if (res < BUFFSIZE)
617 break;
618 pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
619 } 616 }
620 GNUNET_free(rbuff); 617 if (res < BUFFSIZE)
618 break;
619 pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
620 }
621 GNUNET_free (rbuff);
621 return bf; 622 return bf;
622} 623}
623 624
@@ -636,27 +637,27 @@ GNUNET_CONTAINER_bloomfilter_load(const char *filename,
636 * @return the bloomfilter 637 * @return the bloomfilter
637 */ 638 */
638struct GNUNET_CONTAINER_BloomFilter * 639struct GNUNET_CONTAINER_BloomFilter *
639GNUNET_CONTAINER_bloomfilter_init(const char *data, 640GNUNET_CONTAINER_bloomfilter_init (const char *data,
640 size_t size, 641 size_t size,
641 unsigned int k) 642 unsigned int k)
642{ 643{
643 struct GNUNET_CONTAINER_BloomFilter *bf; 644 struct GNUNET_CONTAINER_BloomFilter *bf;
644 645
645 if ((0 == k) || (0 == size)) 646 if ((0 == k) || (0 == size))
646 return NULL; 647 return NULL;
647 bf = GNUNET_new(struct GNUNET_CONTAINER_BloomFilter); 648 bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
648 bf->filename = NULL; 649 bf->filename = NULL;
649 bf->fh = NULL; 650 bf->fh = NULL;
650 bf->bitArray = GNUNET_malloc_large(size); 651 bf->bitArray = GNUNET_malloc_large (size);
651 if (NULL == bf->bitArray) 652 if (NULL == bf->bitArray)
652 { 653 {
653 GNUNET_free(bf); 654 GNUNET_free (bf);
654 return NULL; 655 return NULL;
655 } 656 }
656 bf->bitArraySize = size; 657 bf->bitArraySize = size;
657 bf->addressesPerElement = k; 658 bf->addressesPerElement = k;
658 if (NULL != data) 659 if (NULL != data)
659 GNUNET_memcpy(bf->bitArray, data, size); 660 GNUNET_memcpy (bf->bitArray, data, size);
660 return bf; 661 return bf;
661} 662}
662 663
@@ -671,7 +672,7 @@ GNUNET_CONTAINER_bloomfilter_init(const char *data,
671 * @return #GNUNET_SYSERR if the data array is not big enough 672 * @return #GNUNET_SYSERR if the data array is not big enough
672 */ 673 */
673int 674int
674GNUNET_CONTAINER_bloomfilter_get_raw_data( 675GNUNET_CONTAINER_bloomfilter_get_raw_data (
675 const struct GNUNET_CONTAINER_BloomFilter *bf, 676 const struct GNUNET_CONTAINER_BloomFilter *bf,
676 char *data, 677 char *data,
677 size_t size) 678 size_t size)
@@ -680,7 +681,7 @@ GNUNET_CONTAINER_bloomfilter_get_raw_data(
680 return GNUNET_SYSERR; 681 return GNUNET_SYSERR;
681 if (bf->bitArraySize != size) 682 if (bf->bitArraySize != size)
682 return GNUNET_SYSERR; 683 return GNUNET_SYSERR;
683 GNUNET_memcpy(data, bf->bitArray, size); 684 GNUNET_memcpy (data, bf->bitArray, size);
684 return GNUNET_OK; 685 return GNUNET_OK;
685} 686}
686 687
@@ -693,15 +694,15 @@ GNUNET_CONTAINER_bloomfilter_get_raw_data(
693 * @param bf the filter 694 * @param bf the filter
694 */ 695 */
695void 696void
696GNUNET_CONTAINER_bloomfilter_free(struct GNUNET_CONTAINER_BloomFilter *bf) 697GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
697{ 698{
698 if (NULL == bf) 699 if (NULL == bf)
699 return; 700 return;
700 if (bf->fh != NULL) 701 if (bf->fh != NULL)
701 GNUNET_DISK_file_close(bf->fh); 702 GNUNET_DISK_file_close (bf->fh);
702 GNUNET_free_non_null(bf->filename); 703 GNUNET_free_non_null (bf->filename);
703 GNUNET_free(bf->bitArray); 704 GNUNET_free (bf->bitArray);
704 GNUNET_free(bf); 705 GNUNET_free (bf);
705} 706}
706 707
707 708
@@ -711,14 +712,14 @@ GNUNET_CONTAINER_bloomfilter_free(struct GNUNET_CONTAINER_BloomFilter *bf)
711 * @param bf the filter 712 * @param bf the filter
712 */ 713 */
713void 714void
714GNUNET_CONTAINER_bloomfilter_clear(struct GNUNET_CONTAINER_BloomFilter *bf) 715GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
715{ 716{
716 if (NULL == bf) 717 if (NULL == bf)
717 return; 718 return;
718 719
719 memset(bf->bitArray, 0, bf->bitArraySize); 720 memset (bf->bitArray, 0, bf->bitArraySize);
720 if (bf->filename != NULL) 721 if (bf->filename != NULL)
721 make_empty_file(bf->fh, bf->bitArraySize * 4LL); 722 make_empty_file (bf->fh, bf->bitArraySize * 4LL);
722} 723}
723 724
724 725
@@ -730,7 +731,7 @@ GNUNET_CONTAINER_bloomfilter_clear(struct GNUNET_CONTAINER_BloomFilter *bf)
730 * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not 731 * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
731 */ 732 */
732int 733int
733GNUNET_CONTAINER_bloomfilter_test( 734GNUNET_CONTAINER_bloomfilter_test (
734 const struct GNUNET_CONTAINER_BloomFilter *bf, 735 const struct GNUNET_CONTAINER_BloomFilter *bf,
735 const struct GNUNET_HashCode *e) 736 const struct GNUNET_HashCode *e)
736{ 737{
@@ -739,7 +740,7 @@ GNUNET_CONTAINER_bloomfilter_test(
739 if (NULL == bf) 740 if (NULL == bf)
740 return GNUNET_YES; 741 return GNUNET_YES;
741 res = GNUNET_YES; 742 res = GNUNET_YES;
742 iterateBits(bf, &testBitCallback, &res, e); 743 iterateBits (bf, &testBitCallback, &res, e);
743 return res; 744 return res;
744} 745}
745 746
@@ -751,12 +752,12 @@ GNUNET_CONTAINER_bloomfilter_test(
751 * @param e the element 752 * @param e the element
752 */ 753 */
753void 754void
754GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, 755GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
755 const struct GNUNET_HashCode *e) 756 const struct GNUNET_HashCode *e)
756{ 757{
757 if (NULL == bf) 758 if (NULL == bf)
758 return; 759 return;
759 iterateBits(bf, &incrementBitCallback, bf, e); 760 iterateBits (bf, &incrementBitCallback, bf, e);
760} 761}
761 762
762 763
@@ -771,9 +772,9 @@ GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf,
771 * @param size number of bytes in data 772 * @param size number of bytes in data
772 */ 773 */
773int 774int
774GNUNET_CONTAINER_bloomfilter_or(struct GNUNET_CONTAINER_BloomFilter *bf, 775GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
775 const char *data, 776 const char *data,
776 size_t size) 777 size_t size)
777{ 778{
778 unsigned int i; 779 unsigned int i;
779 unsigned int n; 780 unsigned int n;
@@ -784,8 +785,8 @@ GNUNET_CONTAINER_bloomfilter_or(struct GNUNET_CONTAINER_BloomFilter *bf,
784 return GNUNET_YES; 785 return GNUNET_YES;
785 if (bf->bitArraySize != size) 786 if (bf->bitArraySize != size)
786 return GNUNET_SYSERR; 787 return GNUNET_SYSERR;
787 fc = (unsigned long long *)bf->bitArray; 788 fc = (unsigned long long *) bf->bitArray;
788 dc = (const unsigned long long *)data; 789 dc = (const unsigned long long *) data;
789 n = size / sizeof(unsigned long long); 790 n = size / sizeof(unsigned long long);
790 791
791 for (i = 0; i < n; i++) 792 for (i = 0; i < n; i++)
@@ -806,7 +807,7 @@ GNUNET_CONTAINER_bloomfilter_or(struct GNUNET_CONTAINER_BloomFilter *bf,
806 * @return #GNUNET_OK on success 807 * @return #GNUNET_OK on success
807 */ 808 */
808int 809int
809GNUNET_CONTAINER_bloomfilter_or2( 810GNUNET_CONTAINER_bloomfilter_or2 (
810 struct GNUNET_CONTAINER_BloomFilter *bf, 811 struct GNUNET_CONTAINER_BloomFilter *bf,
811 const struct GNUNET_CONTAINER_BloomFilter *to_or) 812 const struct GNUNET_CONTAINER_BloomFilter *to_or)
812{ 813{
@@ -819,13 +820,13 @@ GNUNET_CONTAINER_bloomfilter_or2(
819 if (NULL == bf) 820 if (NULL == bf)
820 return GNUNET_OK; 821 return GNUNET_OK;
821 if (bf->bitArraySize != to_or->bitArraySize) 822 if (bf->bitArraySize != to_or->bitArraySize)
822 { 823 {
823 GNUNET_break(0); 824 GNUNET_break (0);
824 return GNUNET_SYSERR; 825 return GNUNET_SYSERR;
825 } 826 }
826 size = bf->bitArraySize; 827 size = bf->bitArraySize;
827 fc = (unsigned long long *)bf->bitArray; 828 fc = (unsigned long long *) bf->bitArray;
828 dc = (const unsigned long long *)to_or->bitArray; 829 dc = (const unsigned long long *) to_or->bitArray;
829 n = size / sizeof(unsigned long long); 830 n = size / sizeof(unsigned long long);
830 831
831 for (i = 0; i < n; i++) 832 for (i = 0; i < n; i++)
@@ -843,14 +844,14 @@ GNUNET_CONTAINER_bloomfilter_or2(
843 * @param e the element to remove 844 * @param e the element to remove
844 */ 845 */
845void 846void
846GNUNET_CONTAINER_bloomfilter_remove(struct GNUNET_CONTAINER_BloomFilter *bf, 847GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
847 const struct GNUNET_HashCode *e) 848 const struct GNUNET_HashCode *e)
848{ 849{
849 if (NULL == bf) 850 if (NULL == bf)
850 return; 851 return;
851 if (NULL == bf->filename) 852 if (NULL == bf->filename)
852 return; 853 return;
853 iterateBits(bf, &decrementBitCallback, bf, e); 854 iterateBits (bf, &decrementBitCallback, bf, e);
854} 855}
855 856
856/** 857/**
@@ -865,27 +866,27 @@ GNUNET_CONTAINER_bloomfilter_remove(struct GNUNET_CONTAINER_BloomFilter *bf,
865 * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element 866 * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
866 */ 867 */
867void 868void
868GNUNET_CONTAINER_bloomfilter_resize(struct GNUNET_CONTAINER_BloomFilter *bf, 869GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
869 GNUNET_CONTAINER_HashCodeIterator iterator, 870 GNUNET_CONTAINER_HashCodeIterator iterator,
870 void *iterator_cls, 871 void *iterator_cls,
871 size_t size, 872 size_t size,
872 unsigned int k) 873 unsigned int k)
873{ 874{
874 struct GNUNET_HashCode hc; 875 struct GNUNET_HashCode hc;
875 unsigned int i; 876 unsigned int i;
876 877
877 GNUNET_free(bf->bitArray); 878 GNUNET_free (bf->bitArray);
878 i = 1; 879 i = 1;
879 while (i < size) 880 while (i < size)
880 i *= 2; 881 i *= 2;
881 size = i; /* make sure it's a power of 2 */ 882 size = i; /* make sure it's a power of 2 */
882 bf->addressesPerElement = k; 883 bf->addressesPerElement = k;
883 bf->bitArraySize = size; 884 bf->bitArraySize = size;
884 bf->bitArray = GNUNET_malloc(size); 885 bf->bitArray = GNUNET_malloc (size);
885 if (NULL != bf->filename) 886 if (NULL != bf->filename)
886 make_empty_file(bf->fh, bf->bitArraySize * 4LL); 887 make_empty_file (bf->fh, bf->bitArraySize * 4LL);
887 while (GNUNET_YES == iterator(iterator_cls, &hc)) 888 while (GNUNET_YES == iterator (iterator_cls, &hc))
888 GNUNET_CONTAINER_bloomfilter_add(bf, &hc); 889 GNUNET_CONTAINER_bloomfilter_add (bf, &hc);
889} 890}
890 891
891/* end of container_bloomfilter.c */ 892/* end of container_bloomfilter.c */