X-Git-Url: http://git.indexdata.com/?a=blobdiff_plain;f=isamb%2Ftstisamb.c;h=4103211742341c54d93e550893b22907e5128ba7;hb=4eaf00a0af4c40bd166e2224964319a58efafeaa;hp=67e3336463ec8fd5fc6745aab39495fbe42c2f20;hpb=4eb3b54bb2ca9af74f39f000d3d40dba99ded887;p=idzebra-moved-to-github.git

diff --git a/isamb/tstisamb.c b/isamb/tstisamb.c
index 67e3336..4103211 100644
--- a/isamb/tstisamb.c
+++ b/isamb/tstisamb.c
@@ -1,6 +1,6 @@
-/* $Id: tstisamb.c,v 1.13 2004-12-13 20:51:31 adam Exp $
-   Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
-   Index Data Aps
+/* $Id: tstisamb.c,v 1.26 2006-12-07 21:13:56 adam Exp $
+   Copyright (C) 1995-2006
+   Index Data ApS
 
 This file is part of the Zebra server.
 
@@ -15,11 +15,19 @@ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.
 
 You should have received a copy of the GNU General Public License
-along with Zebra; see the file LICENSE.zebra.  If not, write to the
-Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA.
+along with this program; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
 */
 
+#if HAVE_SYS_TIMES_H
+#include <sys/times.h>
+#endif
+#if HAVE_SYS_TIME_H
+#include <sys/time.h>
+#endif
+
+#include <stdlib.h>
 #include <string.h>
 #include <yaz/log.h>
 #include <yaz/xmalloc.h>
@@ -44,10 +52,14 @@ int compare_item(const void *a, const void *b)
 
     memcpy(&ia, a, sizeof(int));
     memcpy(&ib, b, sizeof(int));
-    return ia - ib;
+    if (ia > ib)
+	return 1;
+    if (ia < ib)
+	return -1;
+   return 0;
 }
 
-void *code_start()
+void *code_start(void)
 {
     return 0;
 }
@@ -67,8 +79,10 @@ void code_stop(void *p)
 }
 
 struct read_info {
-    int no;
+    int val;
     int step;
+
+    int no;
     int max;
     int insertMode;
 };
@@ -80,36 +94,191 @@ int code_read(void *vp, char **dst, int *insertMode)
 
     if (ri->no >= ri->max)
 	return 0;
-    x = ri->no;
+    ri->no++;
+
+    x = ri->val;
     memcpy (*dst, &x, sizeof(int));
     (*dst)+=sizeof(int);
 
-    ri->no += ri->step;
+    ri->val = ri->val + ri->step;
     *insertMode = ri->insertMode;
+
+#if 0
+    yaz_log(YLOG_LOG, "%d %5d", ri->insertMode, x);
+#endif
     return 1;
 }
 
+void bench_insert(ISAMB isb, int number_of_trees,
+                int number_of_rounds, int number_of_elements)
+{
+    ISAMC_I isamc_i;
+    ISAM_P *isamc_p = xmalloc(sizeof(ISAM_P) * number_of_trees);
+    struct read_info ri;
+    int round, i;
+
+    for (i = 0; i<number_of_trees; i++)
+        isamc_p[i] = 0; /* initially, is empty */
+
+    ri.val = 0;
+    ri.step = 1;
+    ri.insertMode = 1;
+    
+    for (round = 0; round < number_of_rounds; round++)
+    {
+#if HAVE_SYS_TIMES_H
+#if HAVE_SYS_TIME_H
+        struct tms tms1, tms2;
+        struct timeval start_time, end_time;
+        double usec;
+        times(&tms1);
+        gettimeofday(&start_time, 0);
+#endif
+#endif
+        for (i = 0; i<number_of_trees; i++)
+        {
+
+            /* insert a number of entries */
+            ri.no = 0;
+            
+            ri.val = (rand());
+            ri.max = number_of_elements;
+            
+            isamc_i.clientData = &ri;
+            isamc_i.read_item = code_read;
+            
+            
+            isamb_merge (isb, &isamc_p[i] , &isamc_i);
+        }
+#if HAVE_SYS_TIMES_H
+#if HAVE_SYS_TIME_H      
+        gettimeofday(&end_time, 0);
+        times(&tms2);
+        
+        usec = (end_time.tv_sec - start_time.tv_sec) * 1000000.0 +
+            end_time.tv_usec - start_time.tv_usec;
+        
+        yaz_log (YLOG_LOG, "round=%d times: %5.4f %5.2f %5.2f",
+                 round,
+                 usec / 1000000,
+                 (double) (tms2.tms_utime - tms1.tms_utime)/100,
+                 (double) (tms2.tms_stime - tms1.tms_stime)/100);
+#endif
+#endif
+    }
+}
+
+void tst_insert(ISAMB isb, int n)
+{
+    ISAMC_I isamc_i;
+    ISAM_P isamc_p;
+    struct read_info ri;
+    ISAMB_PP pp;
+    char key_buf[20];
+    int nerrs = 0;
+
+    /* insert a number of entries */
+    ri.no = 0;
+    ri.max = n;
+
+    ri.val = 0;
+    ri.step = 1;
+    ri.insertMode = 1;
+
+    isamc_i.clientData = &ri;
+    isamc_i.read_item = code_read;
+    
+    isamc_p = 0; /* new list */
+    isamb_merge (isb, &isamc_p , &isamc_i);
+
+    /* read the entries */
+    pp = isamb_pp_open (isb, isamc_p, 1);
+
+    ri.val = 0;
+    while(isamb_pp_read (pp, key_buf))
+    {
+	int x;
+	memcpy (&x, key_buf, sizeof(int));
+	if (x != ri.val)
+	{
+	    yaz_log(YLOG_WARN, "isamb_pp_read. n=%d Got %d (expected %d)",
+		    n, x, ri.val);
+	    nerrs++;
+	}
+	else if (nerrs)
+	    yaz_log(YLOG_LOG, "isamb_pp_read. n=%d Got %d",
+		    n, x);
+
+	ri.val++;
+    }
+    if (ri.val != ri.max)
+    {
+	yaz_log(YLOG_WARN, "ri.max != ri.max (%d != %d)", ri.val, ri.max);
+	nerrs++;
+    }
+    isamb_dump(isb, isamc_p, log_pr);
+    isamb_pp_close(pp);
+
+    if (nerrs)
+        exit(3);
+    /* delete a number of entries (even ones) */
+    ri.no = 0;
+    ri.max = n - n/2;
+
+    ri.val = 0;
+    ri.step = 2;
+    ri.insertMode = 0;
+
+    isamc_i.clientData = &ri;
+    isamc_i.read_item = code_read;
+    
+    isamb_merge (isb, &isamc_p , &isamc_i);
+
+    /* delete a number of entries (odd ones) */
+    ri.no = 0;
+    ri.max = n/2;
+
+    ri.val = 1;
+    ri.step = 2;
+    ri.insertMode = 0;
+
+    isamc_i.clientData = &ri;
+    isamc_i.read_item = code_read;
+    
+    isamb_merge (isb, &isamc_p, &isamc_i);
+
+    if (isamc_p)
+    {
+	yaz_log(YLOG_WARN, "isamb_merge did not return empty list n=%d",
+		n);
+	exit(3);
+    }
+}
+
 void tst_forward(ISAMB isb, int n)
 {
     ISAMC_I isamc_i;
-    ISAMC_P isamc_p;
+    ISAM_P isamc_p;
     struct read_info ri;
     int i;
     ISAMB_PP pp;
 
     /* insert a number of entries */
+    ri.val = 0;
+    ri.max = n;
+
     ri.no = 0;
     ri.step = 1;
-    ri.max = n;
     ri.insertMode = 1;
 
     isamc_i.clientData = &ri;
     isamc_i.read_item = code_read;
     
-    isamc_p = isamb_merge (isb, 0 /* new list */ , &isamc_i);
+    isamc_p = 0;
+    isamb_merge (isb, &isamc_p, &isamc_i);
 
     /* read the entries */
-    pp = isamb_pp_open (isb, isamc_p, 2);
+    pp = isamb_pp_open (isb, isamc_p, 1);
     
     for (i = 0; i<ri.max; i +=2 )
     {
@@ -126,7 +295,7 @@ void tst_forward(ISAMB isb, int n)
     }
     isamb_pp_close(pp);
     
-    pp = isamb_pp_open (isb, isamc_p, 2);
+    pp = isamb_pp_open (isb, isamc_p, 1);
     for (i = 0; i<ri.max; i += 100)
     {
 	int x = -1;
@@ -145,79 +314,279 @@ void tst_forward(ISAMB isb, int n)
     isamb_unlink(isb, isamc_p);
 }
 
-void tst_insert(ISAMB isb, int n)
+void tst_x(ISAMB isb)
 {
     ISAMC_I isamc_i;
-    ISAMC_P isamc_p;
+    ISAM_P isamb_p = 0;
     struct read_info ri;
-    ISAMB_PP pp;
-    char key_buf[10];
 
-    /* insert a number of entries */
+    isamc_i.clientData = &ri;
+    isamc_i.read_item = code_read;
     ri.no = 0;
+    ri.max = 500;
+
+    ri.val = 1000;
     ri.step = 1;
-    ri.max = n;
     ri.insertMode = 1;
 
-    isamc_i.clientData = &ri;
-    isamc_i.read_item = code_read;
+    isamb_merge (isb, &isamb_p , &isamc_i);
+
+    ri.no = 0;
+    ri.max = 500;
+
+    ri.val = 1;
+    ri.step = 1;
+    ri.insertMode = 1;
+
+    isamb_merge (isb, &isamb_p , &isamc_i);
+}
+
+void tst_append(ISAMB isb, int n)
+{
+    ISAMC_I isamc_i;
+    ISAM_P isamb_p = 0;
+    struct read_info ri;
+    int i;
+    int chunk = 10;
+
+    for (i = 0; i < n; i += chunk)
+    {
+	/* insert a number of entries */
+	ri.no = 0;
+	ri.max = i + chunk;
+
+	ri.val = 0;
+	ri.step = 1;
+	ri.insertMode = 1;
+	
+	isamc_i.clientData = &ri;
+	isamc_i.read_item = code_read;
+	
+	isamb_merge (isb, &isamb_p , &isamc_i);
+    }
+}
+
+
+struct random_read_info {
+    int max;
+    int idx;
+    int level;
+    int *delta;
+};
+
+int tst_random_read(void *vp, char **dst, int *insertMode)
+{
+    struct random_read_info *ri = (struct random_read_info *)vp;
+    int x;
+
+    while(ri->idx < ri->max && ri->delta[ri->idx] == ri->level)
+    {
+	ri->idx++;
+	ri->level = 0;
+    }
+    if (ri->idx >= ri->max)
+	return 0;
     
-    isamc_p = isamb_merge (isb, 0 /* new list */ , &isamc_i);
+    if (ri->delta[ri->idx] > 0)
+    {
+	ri->level++;
+	*insertMode = 1;
+    }
+    else
+    {
+	ri->level--;
+	*insertMode = 0;
+    }
+    x = ri->idx;
+    memcpy (*dst, &x, sizeof(int));
+    (*dst)+=sizeof(int);
 
-    /* read the entries */
-    pp = isamb_pp_open (isb, isamc_p, 2);
+    yaz_log(YLOG_DEBUG, "%d %5d", *insertMode, x);
+    return 1;
+}
+
+void tst_random(ISAMB isb, int n, int rounds, int max_dups)
+{
+    ISAM_P isamb_p = 0;
+
+    int *freq = malloc(sizeof(int) * n);
+    int *delta = malloc(sizeof(int) * n);
+    int i, j;
+    for (i = 0; i<n; i++)
+	freq[i] = 0;
     
-    ri.no = 0;
-    while(isamb_pp_read (pp, key_buf))
+    for (j = 0; j<rounds; j++)
     {
-	int x;
-	memcpy (&x, key_buf, sizeof(int));
-	if (x != ri.no)
+	yaz_log(YLOG_DEBUG, "round %d", j);
+	for (i = 0; i<n; i++)
 	{
-	    yaz_log(YLOG_WARN, "isamb_pp_read. Got %d (expected %d)",
-		    x, ri.no);
-	    exit(3);
+	    if (rand() & 1)
+		delta[i] = (rand() % (1+max_dups)) - freq[i];
+	    else
+		delta[i] = 0;
+	}
+	if (n)
+	{
+	    ISAMC_I isamc_i;
+	    struct random_read_info ri;
+	    
+	    ri.delta = delta;
+	    ri.idx = 0;
+	    ri.max = n;
+	    ri.level = 0;
+	    
+	    isamc_i.clientData = &ri;
+	    isamc_i.read_item = tst_random_read;
+
+	    isamb_merge (isb, &isamb_p , &isamc_i);
+	}
+	
+	yaz_log(YLOG_DEBUG, "dump %d", j);
+	isamb_dump(isb, isamb_p, log_pr);
+
+	yaz_log(YLOG_DEBUG, "----------------------------");
+	for (i = 0; i<n; i++)
+	    freq[i] += delta[i];
+
+	if (!isamb_p)
+	{
+	    for (i = 0; i<n; i++)
+		if (freq[i])
+		{
+		    yaz_log(YLOG_WARN, "isamb_merge returned 0, but "
+			    "freq is non-empty");
+		    exit(1);
+		}
+	}
+	else
+	{
+	    int level = 0;
+	    int idx = 0;
+	    char key_buf[20];
+	    ISAMB_PP pp = isamb_pp_open (isb, isamb_p, 1);
+
+	    yaz_log(YLOG_DEBUG, "test %d", j);
+
+	    while(isamb_pp_read (pp, key_buf))
+	    {
+		int x;
+		memcpy (&x, key_buf, sizeof(int));
+		yaz_log(YLOG_DEBUG, "Got %d", x);
+		while (idx < n && freq[idx] == level)
+		{
+		    idx++;
+		    level = 0;
+		}
+		if (idx == n)
+		{
+		    yaz_log(YLOG_WARN, "tst_random: Extra item: %d", x);
+		    exit(1);
+		}
+		if (idx != x)
+		{
+		    yaz_log(YLOG_WARN, "tst_random: Mismatch %d != %d",
+			    x, idx);
+		    exit(1);
+		}
+		level++;
+	    }
+	    while (idx < n && freq[idx] == level)
+	    {
+		idx++;
+		level = 0;
+	    }
+	    if (idx != n)
+	    {
+		yaz_log(YLOG_WARN, "tst_random: Missing item: %d", idx);
+		exit(1);
+	    }
+	    isamb_pp_close(pp);
 	}
-	ri.no++;
-    }
-    if (ri.no != ri.max)
-    {
-	yaz_log(YLOG_WARN, "ri.max != ri.max (%d != %d)", ri.no, ri.max);
-	exit(3);
     }
-    isamb_pp_close(pp);
+    free(freq);
+    free(delta);
+}
 
-    isamb_dump(isb, isamc_p, log_pr);
+/* \fn void tst_minsert(ISAMB isb, int n)
+   \brief insert inserts n identical keys, removes n/2, then n-n/2 ..
+   \param isb ISAMB handle
+   \param n number of keys
+*/
+void tst_minsert(ISAMB isb, int n)
+{
+    ISAMC_I isamc_i;
+    ISAM_P isamb_p = 0;
+    struct read_info ri;
+
+    isamc_i.clientData = &ri;
+
+    /* all have same value = 1 */
+    ri.val = 1;  
+    ri.step = 0;
+
+    isamc_i.read_item = code_read;
 
-    /* delete a number of entries (even ones) */
     ri.no = 0;
-    ri.step = 2;
     ri.max = n;
-    ri.insertMode = 0;
 
-    isamc_i.clientData = &ri;
-    isamc_i.read_item = code_read;
+    ri.insertMode = 1;
+
+    isamb_merge (isb, &isamb_p , &isamc_i);
+
+    isamb_dump(isb, isamb_p, log_pr);
     
-    isamc_p = isamb_merge (isb, isamc_p , &isamc_i);
+    ri.no = 0;
+    ri.max = n - n/2;
 
-    /* delete a number of entries (odd ones) */
-    ri.no = 1;
-    ri.step = 2;
-    ri.max = n;
     ri.insertMode = 0;
 
-    isamc_i.clientData = &ri;
-    isamc_i.read_item = code_read;
-    
-    isamc_p = isamb_merge (isb, isamc_p , &isamc_i);
+    isamb_merge (isb, &isamb_p , &isamc_i);
 
-    if (isamc_p)
+    ri.no = 0;
+    ri.max = n/2;
+
+    ri.insertMode = 0;
+
+    isamb_merge (isb, &isamb_p , &isamc_i);
+    if (isamb_p)
     {
-	yaz_log(YLOG_WARN, "isamb_merge did not return empty list");
-	exit(3);
+	yaz_log(YLOG_WARN, "tst_minsert: isamb_merge should be empty n=%d",
+		n);
+	exit(1);
     }
 }
 
+/* tests for identical keys.. ISAMB does not handle that, so some of the
+   tests below fails
+*/
+static void identical_keys_tests(ISAMB isb)
+{
+#if 1
+    tst_minsert(isb, 10);
+#endif
+#if 0
+    tst_minsert(isb, 600);  /* still fails */
+#endif
+#if 1
+    tst_random(isb, 20, 200, 1);
+#endif
+#if 1
+    tst_random(isb, 5, 200, 2);
+#endif
+
+#if 1
+    tst_random(isb, 250, 10, 4);
+#endif
+#if 1
+    /* fails if both are executed */
+    tst_random(isb, 20000, 10, 4);
+    tst_random(isb, 20000, 10, 10);
+#endif
+#if 1
+    tst_random(isb, 250, 100, 10);
+#endif
+}
+
 int main(int argc, char **argv)
 {
     BFiles bfs;
@@ -253,14 +622,26 @@ int main(int argc, char **argv)
 	yaz_log(YLOG_WARN, "isamb_open failed");
 	exit(2);
     }
+#if 0
+    bench_insert(isb, 1000, 100, 10000);
+#else
     tst_insert(isb, 1);
     tst_insert(isb, 2);
     tst_insert(isb, 20);
     tst_insert(isb, 100);
     tst_insert(isb, 500);
     tst_insert(isb, 10000);
+
     tst_forward(isb, 10000);
-    /* close isam handle */
+
+    tst_x(isb);
+
+    tst_append(isb, 1000);
+#endif
+
+    if (0)
+	identical_keys_tests(isb);
+    
     isamb_close(isb);
 
     /* exit block system */
@@ -268,3 +649,11 @@ int main(int argc, char **argv)
     exit(0);
     return 0;
 }
+/*
+ * Local variables:
+ * c-basic-offset: 4
+ * indent-tabs-mode: nil
+ * End:
+ * vim: shiftwidth=4 tabstop=8 expandtab
+ */
+