Add source code documentation for bloom_insert().
authorAndre Noll <maan@systemlinux.org>
Thu, 25 Dec 2008 10:46:41 +0000 (11:46 +0100)
committerAndre Noll <maan@systemlinux.org>
Thu, 25 Dec 2008 10:46:41 +0000 (11:46 +0100)
adu.c
bloom.c

diff --git a/adu.c b/adu.c
index 82c876a..b227589 100644 (file)
--- 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 (file)
--- a/bloom.c
+++ b/bloom.c
@@ -1,3 +1,11 @@
+/*
+ * Copyright (C) 2008 Andre Noll <maan@systemlinux.org>
+ *
+ * Licensed under the GPL v2. For licencing details see COPYING.
+ */
+
+/** \file bloom.c Simple bloom filter implementation. */
+
 #include <stdio.h>
 #include <stdlib.h>
 #include <inttypes.h>
@@ -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;