Write a postlicyd(8) man page.

[apps/pfixtools.git] / common / tst-trie.c

diff --git a/common/tst-trie.c b/common/tst-trie.c
index 2b7bdee..53faf1c 100644 (file)
--- a/common/tst-trie.c
+++ b/common/tst-trie.c
@@ -16,17 +16,20 @@
 /*     products derived from this software without specific prior written     */
 /*     permission.                                                            */
 /*                                                                            */
-/*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
-/*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
-/*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
-/*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
-/*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
-/*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
-/*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
-/*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
-/*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
-/*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
-/*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
+/*  THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS ``AS IS'' AND ANY EXPRESS   */
+/*  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED         */
+/*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE    */
+/*  DISCLAIMED.  IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY         */
+/*  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL        */
+/*  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS   */
+/*  OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)     */
+/*  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,       */
+/*  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN  */
+/*  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE           */
+/*  POSSIBILITY OF SUCH DAMAGE.                                               */
+/*                                                                            */
+/*   Copyright (c) 2006-2008 the Authors                                      */
+/*   see AUTHORS and source files for details                                 */
 /******************************************************************************/
 
 /*
@@ -86,6 +89,7 @@ static trie_t *create_trie_from_file(const char *file)
     return db;
 }
 
+
 __attribute__((used))
 static void check_trie_with_file(const trie_t *db, const char *file)
 {
@@ -132,8 +136,106 @@ static void check_trie_with_file(const trie_t *db, const char *file)
 }
 
 
+static bool test_linear(const uint8_t *start, uint32_t len, uint8_t data) {
+    const uint8_t *end = start + len;
+    while (start < end) {
+        const uint8_t val = *start;
+        if (val == data) {
+            return true;
+        } else if (val > data) {
+            return false;
+        }
+        ++start;
+    }
+    return false;
+}
+
+static bool test_dicho(const uint8_t *start, uint32_t len, uint8_t data) {
+    const uint8_t *end = start + len;
+
+    while (start < end) {
+        const uint8_t *mid = start + ((end - start) >> 1);
+        const uint8_t val = *mid;
+
+        if (val == data) {
+            return true;
+        } else if (data < val) {
+            end = mid;
+        } else {
+            start = mid + 1;
+        }
+    }
+    return false;
+}
+
+__attribute__((used))
+static void test_lookup(void) {
+    bool set[64];
+    uint8_t data[64];
+
+    printf("size,dicho,linear\n");
+    for (int i = 1 ; i < 64 ; ++i) {
+        if (i > 32) {
+            int selected = 64;
+            memset(set, 1, 64 * sizeof(bool));
+            while (selected > i) {
+                int val = rand() % 64;
+                if (set[val]) {
+                    set[val] = false;
+                    --selected;
+                }
+            }
+        } else {
+            int selected = 0;
+            memset(set, 0, 64 * sizeof(bool));
+            while (selected < i) {
+                int val = rand() % 64;
+                if (!set[val]) {
+                    set[val] = true;
+                    ++selected;
+                }
+            }
+        }
+        int pos = 0;
+        for (int j = 0 ; j < 64 ; ++j) {
+            if (set[j]) {
+                data[pos] = j;
+                ++pos;
+            }
+        }
+
+        struct timeval start, end;
+        double diff_dicho, diff_linear;
+        const int iterations = 50000000;
+
+        gettimeofday(&start, NULL);
+        for (int k = 0 ; k < iterations ; ++k) {
+            for (int j = 0 ; j < 64 ; ++j) {
+                test_dicho(data, i, j);
+            }
+        }
+        gettimeofday(&end, NULL);
+        diff_dicho = ((end.tv_sec - start.tv_sec) * 10.0)
+             + (double)(end.tv_usec - start.tv_usec) / 10e5;
+
+        gettimeofday(&start, NULL);
+        for (int k = 0 ; k < iterations ; ++k) {
+            for (int j = 0 ; j < 64 ; ++j) {
+                test_linear(data, i, j);
+            }
+        }
+        gettimeofday(&end, NULL);
+        diff_linear = ((end.tv_sec - start.tv_sec) * 10.0)
+             + (double)(end.tv_usec - start.tv_usec) / 10e5;
+        printf("%d,%d,%d\n", i, (int)diff_dicho, (int)diff_linear);
+    }
+}
+
+
 int main(int argc, char *argv[])
 {
+    /* test_lookup(); */
+
     /* Trivial tests
      */
     trie_t *trie = trie_new();