From f9338eb031ef2bd9ec9d18d80140e7b539e47db0 Mon Sep 17 00:00:00 2001 From: Andre Noll Date: Thu, 25 Dec 2008 11:46:41 +0100 Subject: [PATCH] Add source code documentation for bloom_insert(). --- adu.c | 2 +- bloom.c | 32 +++++++++++++++++++++++++++++++- 2 files changed, 32 insertions(+), 2 deletions(-) diff --git a/adu.c b/adu.c index 82c876a..b227589 100644 --- a/adu.c +++ b/adu.c @@ -12,7 +12,7 @@ * - Modes of operation: \ref select.c, \ref create.c, \ref interactive.c * - User handling: \ref user.c * - Error handling: \ref error.h - * - Library-type functions: \ref fd.c, \ref format.c, \ref string.c, \ref portable_io.h + * - Library-type functions: \ref fd.c, \ref format.c, \ref string.c, \ref portable_io.h, \ref bloom.c */ #include "adu.h" diff --git a/bloom.c b/bloom.c index b072ad1..b9de98b 100644 --- a/bloom.c +++ b/bloom.c @@ -1,3 +1,11 @@ +/* + * Copyright (C) 2008 Andre Noll + * + * Licensed under the GPL v2. For licencing details see COPYING. + */ + +/** \file bloom.c Simple bloom filter implementation. */ + #include #include #include @@ -32,13 +40,14 @@ static inline uint64_t filter_bits(struct bloom *b) * http://www.azillionmonkeys.com/qed/hash.html */ +/** \cond */ #if (defined(__GNUC__) && defined(__i386__)) #define get16bits(d) (*((const uint16_t *) (d))) #else #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ +(uint32_t)(((const uint8_t *)(d))[0]) ) #endif - +/** \endcond */ static uint32_t super_fast_hash(const uint8_t *data, uint32_t len, uint32_t hash) { @@ -96,6 +105,27 @@ static int test_and_set_bit(uint64_t bitnum, struct bloom *b) return ret; } +/** + * Insert data to the given bloom filter. + * + * This function computes \a k hashes from the given data where \a k is the + * number of hash functions of the filter \a b. Each hash value corresponds to + * a position in the bit array of the filter and each of these bits are being + * tested and set. If not all \a k bits were already set, the given data was + * not yet contained in the filter and the function returns non-zero. + * + * Otherwise either (a) the same data has already been inserted previously or + * (b) a hash collision occurred or (c) the \a k bits are set due to previous + * insertion of other data (i.e. a false positive occurred). It is impossible + * to distinguish these cases. + * + * \param data The data to insert. + * \param len Number of bytes of \a data. + * \param b The filter to insert to. + * + * \return Zero if the entry was already contained in the filter (or in case of + * false positives), non-zero otherwise. + */ int bloom_insert(const uint8_t *data, size_t len, struct bloom *b) { int i, ret = 0; -- 2.39.5