simplemail-cvs — Changes in the CVS

[Simplemail-cvs] simplemail/tests index_external_unittest.c, 1.8, 1.9

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25379/tests

Modified Files:
	index_external_unittest.c 
Log Message:
Use function calls instead of direct peeks to get the document id.


Index: index_external_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_external_unittest.c,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- index_external_unittest.c	19 Jan 2014 18:53:49 -0000	1.8
+++ index_external_unittest.c	19 Jan 2014 18:54:09 -0000	1.9
@@ -114,7 +114,7 @@
 			printf("For \"%s\" iter is NULL!\n", buf);
 		} else
 		{
-			CU_ASSERT(iter->did == i);
+			CU_ASSERT(bnode_string_iter_data_get_did(iter) == i);
 
 			iter = bnode_find_string_iter(idx, buf, iter);
 			CU_ASSERT(iter != NULL);
@@ -124,7 +124,7 @@
 				printf("For \"%s\" 2nd iter is NULL!\n", buf);
 			} else
 			{
-				CU_ASSERT(iter->did == i);
+				CU_ASSERT(bnode_string_iter_data_get_did(iter) == i);
 			}
 		}
 	}

[Simplemail-cvs] simplemail/tests index_external_unittest.c, 1.7, 1.8

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25323/tests

Modified Files:
	index_external_unittest.c 
Log Message:
Added comment.


Index: index_external_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_external_unittest.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- index_external_unittest.c	19 Jan 2014 18:53:26 -0000	1.7
+++ index_external_unittest.c	19 Jan 2014 18:53:49 -0000	1.8
@@ -82,6 +82,7 @@
 
 	CU_ASSERT(count_index_leaves(idx, idx->root_node, 0) == 2 * number_of_distinct_strings);
 
+	/* Simple Lookups */
 	for (i=0;i<number_of_distinct_strings;i++)
 	{
 		char buf[16];

[Simplemail-cvs] simplemail index_external.c,1.46,1.47

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25276

Modified Files:
	index_external.c 
Log Message:
Added bnode_find_string_iter() that allows to scan the index using an iterator-like API.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.46
retrieving revision 1.47
diff -u -d -r1.46 -r1.47
--- index_external.c	19 Jan 2014 18:51:49 -0000	1.46
+++ index_external.c	19 Jan 2014 18:53:26 -0000	1.47
@@ -700,6 +700,94 @@
 	return nd;
 }
 
+/**
+ * The iterator data.
+ */
+struct bnode_string_iter_data
+{
+	/** Allocated bnode */
+	bnode *node;
+
+	/** The current index */
+	int index;
+
+	/** The document id */
+	int did;
+};
+
+/**
+ * The document did to which the iter points.
+ *
+ * @param iter
+ * @return
+ */
+int bnode_string_iter_data_get_did(struct bnode_string_iter_data *iter)
+{
+	return iter->did;
+}
+
+/**
+ * Sets up an iterator to find the given text.
+ *
+ * @param idx the index.
+ * @param text the text to look for.
+ * @param iter the previous iterator or NULL if this is the first iterator.
+ * @return the new iterator or NULL, if no more matches could have been found.
+ */
+static struct bnode_string_iter_data *bnode_find_string_iter(struct index_external *idx, const char *text, struct bnode_string_iter_data *iter)
+{
+	int cmp;
+	int index;
+	int text_len;
+	struct bnode_element *be;
+	char *str;
+
+	if (!iter)
+	{
+		struct bnode_path path;
+		int block;
+
+		if (!(iter = malloc(sizeof(*iter))))
+			return NULL;
+
+		if (!(iter->node = bnode_create(idx)))
+		{
+			free(iter);
+			return NULL;
+		}
+
+		if (!bnode_lookup(idx, text, &path))
+			return 0;
+
+		block = path.node[path.max_level].block;
+		index = path.node[path.max_level].key_index;
+
+		if (!bnode_read_block(idx, iter->node, block))
+			return 0;
+	} else
+	{
+		index = iter->index + 1;
+	}
+
+	text_len = strlen(text);
+
+	if (index == iter->node->num_elements)
+		goto done;
+	be = bnode_get_ith_element_of_node(idx, iter->node, index);
+	if (!(str = bnode_read_string(idx, be)))
+		goto done;
+
+	cmp = strncmp(text, str, text_len);
+	if (cmp) goto done;
+	iter->index = index;
+	iter->did = be->did;
+	return iter;
+done:
+	bnode_free(idx, iter->node);
+	free(iter);
+	return NULL;
+}
+
 static void index_external_dispose(struct index *index)
 {
 	struct document_node *d;

[Simplemail-cvs] simplemail/tests index_external_unittest.c, 1.5, 1.6

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25239/tests

Modified Files:
	index_external_unittest.c 
Log Message:
Some more logging in the unit test.


Index: index_external_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_external_unittest.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- index_external_unittest.c	19 Jan 2014 18:52:47 -0000	1.5
+++ index_external_unittest.c	19 Jan 2014 18:53:05 -0000	1.6
@@ -93,12 +93,14 @@
 		rc = bnode_lookup(idx, buf, &bp);
 		CU_ASSERT(rc != 0);
 		CU_ASSERT(bp.max_level == 1);
+
+		printf("buf: %s %d\n", buf, bp.node[1].key_index);
 	}
 
 	printf("%d %d %d %d\n", count_index_leaves(idx, idx->root_node, 0), count_index(idx, idx->root_node, 0), idx->max_elements_per_node, idx->number_of_blocks);
 
 
-//	dump_index(idx, idx->root_node, 0);
+	dump_index(idx, idx->root_node, 0);
 
 	index_external_dispose(&idx->index);
 }

[Simplemail-cvs] simplemail/tests index_external_unittest.c, 1.4, 1.5

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25179/tests

Modified Files:
	index_external_unittest.c 
Log Message:
Now insert duplicates and test them.


Index: index_external_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_external_unittest.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- index_external_unittest.c	19 Jan 2014 18:52:28 -0000	1.4
+++ index_external_unittest.c	19 Jan 2014 18:52:47 -0000	1.5
@@ -66,6 +66,35 @@
 		CU_ASSERT(bp.max_level == 1);
 	}
 
+	/* Insert strings again */
+	for (i=0;i<number_of_distinct_strings;i++)
+	{
+		char buf[16];
+		long offset;
+		snprintf(buf, sizeof(buf), "%03dtest", i);
+
+		rc = index_external_append_string(idx, buf, &offset);
+		CU_ASSERT(rc != 0);
+
+		rc = bnode_insert_string(idx, i, offset, buf);
+		CU_ASSERT(rc != 0);
+	}
+
+	CU_ASSERT(count_index_leaves(idx, idx->root_node, 0) == 2 * number_of_distinct_strings);
+
+	for (i=0;i<number_of_distinct_strings;i++)
+	{
+		char buf[16];
+		struct bnode_path bp;
+
+		snprintf(buf, sizeof(buf), "%03dtest", i);
+
+		memset(&bp, 0, sizeof(bp));
+		rc = bnode_lookup(idx, buf, &bp);
+		CU_ASSERT(rc != 0);
+		CU_ASSERT(bp.max_level == 1);
+	}
+
 	printf("%d %d %d %d\n", count_index_leaves(idx, idx->root_node, 0), count_index(idx, idx->root_node, 0), idx->max_elements_per_node, idx->number_of_blocks);
 
 

[Simplemail-cvs] simplemail/tests index_external_unittest.c, 1.3, 1.4

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25142/tests

Modified Files:
	index_external_unittest.c 
Log Message:
Declare number_of_distinct_strings variable.


Index: index_external_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_external_unittest.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- index_external_unittest.c	19 Jan 2014 18:52:08 -0000	1.3
+++ index_external_unittest.c	19 Jan 2014 18:52:28 -0000	1.4
@@ -32,14 +32,16 @@
 	struct index_external *idx;
 	int rc;
 	int i;
-	long offset;
+	int number_of_distinct_strings;
 
 	idx = (struct index_external *)index_external_create_with_opts("/tmp/index_external_unittest_index.dat", 512);
 	CU_ASSERT(idx != NULL);
 
-	for (i=0;i<idx->max_elements_per_node+1;i++)
+	number_of_distinct_strings = idx->max_elements_per_node + 1;
+	for (i=0;i<number_of_distinct_strings;i++)
 	{
 		char buf[16];
+		long offset;
 		snprintf(buf, sizeof(buf), "%03dtest", i);
 
 		rc = index_external_append_string(idx, buf, &offset);
@@ -49,9 +51,9 @@
 		CU_ASSERT(rc != 0);
 	}
 
-	CU_ASSERT(count_index_leaves(idx, idx->root_node, 0) == idx->max_elements_per_node+1);
+	CU_ASSERT(count_index_leaves(idx, idx->root_node, 0) == number_of_distinct_strings);
 
-	for (i=0;i<idx->max_elements_per_node+1;i++)
+	for (i=0;i<number_of_distinct_strings;i++)
 	{
 		char buf[16];
 		struct bnode_path bp;

[Simplemail-cvs] simplemail/tests index_external_unittest.c, 1.2, 1.3

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25100/tests

Modified Files:
	index_external_unittest.c 
Log Message:
Check for proper level of inserted strings.


Index: index_external_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_external_unittest.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- index_external_unittest.c	19 Jan 2014 18:51:29 -0000	1.2
+++ index_external_unittest.c	19 Jan 2014 18:52:08 -0000	1.3
@@ -50,6 +50,20 @@
 	}
 
 	CU_ASSERT(count_index_leaves(idx, idx->root_node, 0) == idx->max_elements_per_node+1);
+
+	for (i=0;i<idx->max_elements_per_node+1;i++)
+	{
+		char buf[16];
+		struct bnode_path bp;
+
+		snprintf(buf, sizeof(buf), "%03dtest", i);
+
+		memset(&bp, 0, sizeof(bp));
+		rc = bnode_lookup(idx, buf, &bp);
+		CU_ASSERT(rc != 0);
+		CU_ASSERT(bp.max_level == 1);
+	}
+
 	printf("%d %d %d %d\n", count_index_leaves(idx, idx->root_node, 0), count_index(idx, idx->root_node, 0), idx->max_elements_per_node, idx->number_of_blocks);
 
 

[Simplemail-cvs] simplemail index_external.c,1.45,1.46

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv25044

Modified Files:
	index_external.c 
Log Message:
No longer leaves early, if there is a direct match.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.45
retrieving revision 1.46
diff -u -d -r1.45 -r1.46
--- index_external.c	19 Jan 2014 18:51:10 -0000	1.45
+++ index_external.c	19 Jan 2014 18:51:49 -0000	1.46
@@ -322,11 +322,6 @@
 		path->node[level].block = block;
 		path->node[level].key_index = i;
 
-		/* Leave early if this was a direct match with a separation key.
-		 * In this case, we do not need to descend to the child */
-		if (direct_match)
-			goto out;
-
 		if (block == lchild && !tmp->leaf)
 		{
 			fprintf(stderr, "Endless loop detected!\n");
@@ -604,12 +599,12 @@
 
 		if (tmp->num_elements == idx->max_elements_per_node)
 		{
-			/* Now we split the node into two nodes. We keep the median out as we
+			/* Now we split the node into two nodes. We keep the median in but also
 			 * insert it as a separation value for the two nodes on the parent.
 			 */
 
 			int median = tmp->num_elements / 2;
-			int start_of_2nd_node = median + 1;
+			int start_of_2nd_node = median;
 			struct bnode_element *me = bnode_get_ith_element_of_node(idx, tmp, median);
 			struct bnode_element me_copy = *me;
 

[Simplemail-cvs] simplemail/tests index_external_unittest.c, 1.1, 1.2

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24999/tests

Modified Files:
	index_external_unittest.c 
Log Message:
Improved test.


Index: index_external_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_external_unittest.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- index_external_unittest.c	19 Jan 2014 18:48:29 -0000	1.1
+++ index_external_unittest.c	19 Jan 2014 18:51:29 -0000	1.2
@@ -27,14 +27,35 @@
 /*******************************************************/
 
 /* @Test */
-void test_me(void)
+void test_number_of_leaves_match_inserted_strings(void)
 {
-	struct index *idx;
+	struct index_external *idx;
+	int rc;
+	int i;
+	long offset;
 
-	idx = index_external_create("/tmp/index_external_unittest_index.dat");
+	idx = (struct index_external *)index_external_create_with_opts("/tmp/index_external_unittest_index.dat", 512);
 	CU_ASSERT(idx != NULL);
 
-	index_external_dispose(idx);
+	for (i=0;i<idx->max_elements_per_node+1;i++)
+	{
+		char buf[16];
+		snprintf(buf, sizeof(buf), "%03dtest", i);
+
+		rc = index_external_append_string(idx, buf, &offset);
+		CU_ASSERT(rc != 0);
+
+		rc = bnode_insert_string(idx, i, offset, buf);
+		CU_ASSERT(rc != 0);
+	}
+
+	CU_ASSERT(count_index_leaves(idx, idx->root_node, 0) == idx->max_elements_per_node+1);
+	printf("%d %d %d %d\n", count_index_leaves(idx, idx->root_node, 0), count_index(idx, idx->root_node, 0), idx->max_elements_per_node, idx->number_of_blocks);
+
+
+//	dump_index(idx, idx->root_node, 0);
+
+	index_external_dispose(&idx->index);
 }
 
 /*******************************************************/

[Simplemail-cvs] simplemail index_external.c,1.44,1.45

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24959

Modified Files:
	index_external.c 
Log Message:
Extracted median + 1 into an own variable.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.44
retrieving revision 1.45
diff -u -d -r1.44 -r1.45
--- index_external.c	19 Jan 2014 18:50:51 -0000	1.44
+++ index_external.c	19 Jan 2014 18:51:10 -0000	1.45
@@ -609,6 +609,7 @@
 			 */
 
 			int median = tmp->num_elements / 2;
+			int start_of_2nd_node = median + 1;
 			struct bnode_element *me = bnode_get_ith_element_of_node(idx, tmp, median);
 			struct bnode_element me_copy = *me;
 
@@ -616,10 +617,10 @@
 			tmp->num_elements = median;
 
 			/* Second node */
-			idx->tmp3->num_elements = idx->max_elements_per_node - (median + 1);
+			idx->tmp3->num_elements = idx->max_elements_per_node - start_of_2nd_node;
 			idx->tmp3->lchild = me->gchild;
 			idx->tmp3->leaf = tmp->leaf;
-			memcpy(bnode_get_ith_element_of_node(idx, idx->tmp3, 0), bnode_get_ith_element_of_node(idx, tmp, median + 1), idx->tmp3->num_elements * sizeof(struct bnode_element));
+			memcpy(bnode_get_ith_element_of_node(idx, idx->tmp3, 0), bnode_get_ith_element_of_node(idx, tmp, start_of_2nd_node), idx->tmp3->num_elements * sizeof(struct bnode_element));
 			bnode_clear_elements(idx, idx->tmp3, idx->tmp3->num_elements);
 			int tmp3block = bnode_add_block(idx, idx->tmp3);
 

[Simplemail-cvs] simplemail index_external.c,1.43,1.44

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24914

Modified Files:
	index_external.c 
Log Message:
Added a new function to create an index with some options.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.43
retrieving revision 1.44
diff -u -d -r1.43 -r1.44
--- index_external.c	19 Jan 2014 18:50:32 -0000	1.43
+++ index_external.c	19 Jan 2014 18:50:51 -0000	1.44
@@ -719,7 +719,7 @@
 	free(idx);
 }
 
-static struct index *index_external_create(const char *filename)
+static struct index *index_external_create_with_opts(const char *filename, int block_size)
 {
 	struct index_external *idx;
 	char buf[380];
@@ -729,7 +729,7 @@
 
 	memset(idx,0,sizeof(*idx));
 	list_init(&idx->document_list);
-	idx->block_size = 16384;
+	idx->block_size = block_size;
 	idx->max_elements_per_node = (idx->block_size - sizeof(struct bnode_header)) / sizeof(struct bnode_element);
 
 	if (!(idx->tmp = bnode_create(idx)))
@@ -759,6 +759,11 @@
 	return NULL;
 }
 
+static struct index *index_external_create(const char *filename)
+{
+	return index_external_create_with_opts(filename, 16384);
+}
+
 /**
  * Appends the given string to the string file. The string will be zero-byte terminated.
  *

[Simplemail-cvs] simplemail index_external.c,1.42,1.43

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24862

Modified Files:
	index_external.c 
Log Message:
Made some function static.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -d -r1.42 -r1.43
--- index_external.c	19 Jan 2014 18:50:08 -0000	1.42
+++ index_external.c	19 Jan 2014 18:50:32 -0000	1.43
@@ -704,7 +704,7 @@
 	return nd;
 }
 
-void index_external_dispose(struct index *index)
+static void index_external_dispose(struct index *index)
 {
 	struct document_node *d;
 	struct index_external *idx;
@@ -719,7 +719,7 @@
 	free(idx);
 }
 
-struct index *index_external_create(const char *filename)
+static struct index *index_external_create(const char *filename)
 {
 	struct index_external *idx;
 	char buf[380];

[Simplemail-cvs] simplemail index_external.c,1.41,1.42

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24821

Modified Files:
	index_external.c 
Log Message:
Added count_index_leaves() function.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.41
retrieving revision 1.42
diff -u -d -r1.41 -r1.42
--- index_external.c	19 Jan 2014 18:49:36 -0000	1.41
+++ index_external.c	19 Jan 2014 18:50:08 -0000	1.42
@@ -518,6 +518,40 @@
 }
 
 /**
+ * Count the number of strings, to which all the leaves refer.
+ *
+ * @param idx
+ * @param block
+ * @param level
+ */
+static int count_index_leaves(struct index_external *idx, int block, int level)
+{
+	int i, count = 0;
+	bnode *tmp = bnode_create(idx);
+
+	if (!bnode_read_block(idx, tmp, block))
+		return;
+
+	if (!tmp->leaf)
+		count += count_index(idx, tmp->lchild, level + 1);
+
+	for (i=0; i<tmp->num_elements; i++)
+	{
+		struct bnode_element *e;
+		int rc;
+
+		e = bnode_get_ith_element_of_node(idx, tmp, i);
+		if (!tmp->leaf)
+			count += count_index_leaves(idx, e->gchild, level + 1);
+		else
+			count++;
+	}
+
+	bnode_free(idx, tmp);
+	return count;
+}
+
+/**
  * Inserts the given string into the bnode tree.
  *
  * @param idx

[Simplemail-cvs] simplemail index_external.c,1.40,1.41

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24747

Modified Files:
	index_external.c 
Log Message:
Fixed doxygen docu.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.40
retrieving revision 1.41
diff -u -d -r1.40 -r1.41
--- index_external.c	19 Jan 2014 18:49:16 -0000	1.40
+++ index_external.c	19 Jan 2014 18:49:36 -0000	1.41
@@ -484,9 +484,10 @@
 
 
 /**
- * Verify whether the index is consitent, i.e., whether all strings are in increasing order.
+ * Count the total number of strings to which the index refers.
+ * This includes the strings of the internal nodes as well as the leaves.
  *
- * @param
+ * @param idx
  * @param block
  * @param level
  */

[Simplemail-cvs] simplemail index_external.c,1.39,1.40

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24686

Modified Files:
	index_external.c 
Log Message:
Extracted the appending of strings into an own function.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.39
retrieving revision 1.40
diff -u -d -r1.39 -r1.40
--- index_external.c	19 Jan 2014 18:47:57 -0000	1.39
+++ index_external.c	19 Jan 2014 18:49:16 -0000	1.40
@@ -724,20 +724,37 @@
 	return NULL;
 }
 
+/**
+ * Appends the given string to the string file. The string will be zero-byte terminated.
+ *
+ * @param idx the index.
+ * @param text the text to be inserted.
+ * @param offset returns the starting offset of the string that has been inserted.
+ * @return 0 on failure, else something different.
+ */
+static int index_external_append_string(struct index_external *idx, const char *text, long *offset)
+{
+	/* Determine position and write text */
+	if (fseek(idx->string_file, 0, SEEK_END) != 0)
+		return 0;
+	*offset = ftell(idx->string_file);
+	fputs(text, idx->string_file);
+	fputc(0, idx->string_file);
+
+	return 1;
+}
+
 int index_external_put_document(struct index *index, int did, const char *text)
 {
 	struct index_external *idx;
 	int i;
 	int l = strlen(text);
+	long offset;
 
 	idx = (struct index_external*)index;
 
-	/* Determine position and write text */
-	if (fseek(idx->string_file, 0, SEEK_END) != 0)
+	if (!index_external_append_string(idx, text, &offset))
 		return 0;
-	long offset = ftell(idx->string_file);
-	fputs(text, idx->string_file);
-	fputc(0, idx->string_file);
 
 	for (i=0; i < l; i++)
 	{

[Simplemail-cvs] simplemail/tests .cvsignore,1.10,1.11

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24625/tests

Modified Files:
	.cvsignore 
Log Message:
Ignore more.


Index: .cvsignore
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/.cvsignore,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- .cvsignore	24 Dec 2013 09:10:45 -0000	1.10
+++ .cvsignore	19 Jan 2014 18:48:55 -0000	1.11
@@ -13,3 +13,4 @@
 test-profile
 imap-profile
 dovecot-2.2.9*
+of-human-bondage.txt

[Simplemail-cvs] simplemail/tests index_external_unittest.c, NONE, 1.1 makefile, 1.42, 1.43

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24584/tests

Modified Files:
	makefile 
Added Files:
	index_external_unittest.c 
Log Message:
Added new unit test file index_external_unittest.c.

Here, we like to test functions that are private to index_external.c.


Index: makefile
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/makefile,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -d -r1.42 -r1.43
--- makefile	19 Jan 2014 18:35:24 -0000	1.42
+++ makefile	19 Jan 2014 18:48:29 -0000	1.43
@@ -26,6 +26,7 @@
 	filter_unittest \
 	folder_unittest \
 	index_unittest \
+	index_external_unittest \
 	imap2_unittest \
 	mail_unittest \
 	support_indep_unittest \

--- NEW FILE: index_external_unittest.c ---
/**
 * index_external_unittest.c - unit tests for SimpleMail's external string index implementation
 * Copyright (C) 2013  Sebastian Bauer
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * @file index_external_unittest.c
 */

#include <CUnit/Basic.h>

#include "index_external.c"

/*******************************************************/

/* @Test */
void test_me(void)
{
	struct index *idx;

	idx = index_external_create("/tmp/index_external_unittest_index.dat");
	CU_ASSERT(idx != NULL);

	index_external_dispose(idx);
}

/*******************************************************/

[Simplemail-cvs] simplemail index_external.c,1.38,1.39

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24484

Modified Files:
	index_external.c 
Log Message:
Ensure 0 byte for each string.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -d -r1.38 -r1.39
--- index_external.c	19 Jan 2014 18:46:41 -0000	1.38
+++ index_external.c	19 Jan 2014 18:47:57 -0000	1.39
@@ -737,6 +737,7 @@
 		return 0;
 	long offset = ftell(idx->string_file);
 	fputs(text, idx->string_file);
+	fputc(0, idx->string_file);
 
 	for (i=0; i < l; i++)
 	{

[Simplemail-cvs] simplemail/tests index_unittest.c,1.13,1.14

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24444/tests

Modified Files:
	index_unittest.c 
Log Message:
Test if suffixes some more strings are contained.


Index: index_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_unittest.c,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- index_unittest.c	19 Jan 2014 18:47:03 -0000	1.13
+++ index_unittest.c	19 Jan 2014 18:47:34 -0000	1.14
@@ -237,6 +237,7 @@
 	ok = index_put_document(index,20,zauberlehrling);
 	CU_ASSERT(ok != 0);
 
+	test_index_contains_all_suffixes(index, "This is a very long text.", 4);
 	test_index_contains_all_suffixes(index, zauberlehrling, 20);
 
 	ok = index_remove_document(index,4);
@@ -251,6 +252,9 @@
 	ok = index_put_document(index,32,text);
 	CU_ASSERT(ok != 0);
 
+	test_index_contains_all_suffixes(index, zauberlehrling, 20);
+	test_index_contains_all_suffixes(index, text, 32);
+
 	index_dispose(index);
 	free(text);
 }

[Simplemail-cvs] simplemail/tests index_unittest.c,1.12,1.13

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24372/tests

Modified Files:
	index_unittest.c 
Log Message:
Now longer reads more than 200000 bytes.


Index: index_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_unittest.c,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -d -r1.12 -r1.13
--- index_unittest.c	19 Jan 2014 18:46:18 -0000	1.12
+++ index_unittest.c	19 Jan 2014 18:47:03 -0000	1.13
@@ -130,7 +130,8 @@
 
 
 /**
- * Read the content of the file given by the filename.
+ * Read the content of the file given by the filename but not
+ * more than 200000 bytes.
  *
  * @param filename the name of the file which should be read.
  *
@@ -153,6 +154,9 @@
 		goto out;
 	fseek(fh,0,SEEK_SET);
 
+	if (size > 200000)
+		size = 200000;
+
 	if (!(contents = malloc(size+1)))
 		goto out;
 	if ((fread(contents, 1, size, fh) != size))

[Simplemail-cvs] simplemail index_external.c,1.37,1.38

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24328

Modified Files:
	index_external.c 
Log Message:
Now respects the max_substring_len attribute.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.37
retrieving revision 1.38
diff -u -d -r1.37 -r1.38
--- index_external.c	19 Jan 2014 18:45:54 -0000	1.37
+++ index_external.c	19 Jan 2014 18:46:41 -0000	1.38
@@ -192,13 +192,16 @@
 static char *bnode_read_string(struct index_external *idx, struct bnode_element *element)
 {
 	char *str;
+	int str_len = element->str_len;
+	if (str_len > idx->max_substring_len)
+		str_len = idx->max_substring_len;
 
 	fseek(idx->string_file, element->str_offset, SEEK_SET);
-	if (!(str = malloc(element->str_len + 1)))
+	if (!(str = malloc(str_len + 1)))
 		return 0;
-	if (fread(str, 1, element->str_len, idx->string_file) != element->str_len)
+	if (fread(str, 1, str_len, idx->string_file) != str_len)
 		return 0;
-	str[element->str_len] = 0;
+	str[str_len] = 0;
 	return str;
 }
 
@@ -216,8 +219,8 @@
 {
 	char *str = bnode_read_string(idx, e);
 	if (!str) return 0;
+	*out_cmp = strncmp(str, text, idx->max_substring_len);
 
-	*out_cmp = strcmp(str, text);
 	free(str);
 	return 1;
 }
@@ -644,13 +647,16 @@
 	if (!bnode_read_block(idx, tmp, block))
 		return 0;
 
+	if (text_len > idx->max_substring_len)
+		text_len = idx->max_substring_len;
+
 	for (;i<tmp->num_elements;i++)
 	{
 		int cmp;
 		be = bnode_get_ith_element_of_node(idx, tmp, i);
 		str = bnode_read_string(idx, be);
 		if (!str) return 0;
-		cmp = strncmp(text, str, strlen(text));
+		cmp = strncmp(text, str, text_len);
 		free(str);
 		if (!cmp)
 		{

[Simplemail-cvs] simplemail/tests index_unittest.c,1.11,1.12

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail/tests
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24284/tests

Modified Files:
	index_unittest.c 
Log Message:
Rearranged where some texts are inserted/removed.


Index: index_unittest.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/tests/index_unittest.c,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -d -r1.11 -r1.12
--- index_unittest.c	19 Jan 2014 18:42:44 -0000	1.11
+++ index_unittest.c	19 Jan 2014 18:46:18 -0000	1.12
@@ -226,27 +226,27 @@
 	ok = index_put_document(index,12,"This is a short text.");
 	CU_ASSERT(ok != 0);
 
+	nd = index_find_documents(index,test_index_naive_callback,NULL,1,"very");
+	CU_ASSERT(test_index_naive_callback_called == 1);
+	CU_ASSERT(nd == 1);
+
 	ok = index_put_document(index,20,zauberlehrling);
 	CU_ASSERT(ok != 0);
 
 	test_index_contains_all_suffixes(index, zauberlehrling, 20);
 
-	text = read_file_contents("of-human-bondage.txt");
-	CU_ASSERT(text != NULL);
-
-	ok = index_put_document(index,32,text);
-	CU_ASSERT(ok != 0);
-
-	nd = index_find_documents(index,test_index_naive_callback,NULL,1,"very");
-	CU_ASSERT(test_index_naive_callback_called == 1);
-	CU_ASSERT(nd == 1);
-
 	ok = index_remove_document(index,4);
 	CU_ASSERT(ok != 0);
 
 	nd = index_find_documents(index,test_index_naive_callback2,NULL,1,"very");
 	CU_ASSERT(nd == 0);
 
+	text = read_file_contents("of-human-bondage.txt");
+	CU_ASSERT(text != NULL);
+
+	ok = index_put_document(index,32,text);
+	CU_ASSERT(ok != 0);
+
 	index_dispose(index);
 	free(text);
 }

[Simplemail-cvs] simplemail index_external.c,1.36,1.37

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24216

Modified Files:
	index_external.c 
Log Message:
Added a new field for restricting the length of searched strings.

It is not used yet.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.36
retrieving revision 1.37
diff -u -d -r1.36 -r1.37
--- index_external.c	19 Jan 2014 18:45:31 -0000	1.36
+++ index_external.c	19 Jan 2014 18:45:54 -0000	1.37
@@ -79,6 +79,12 @@
 	/** Identifies the block for the root node. TODO: Make this persistent */
 	int root_node;
 
+	/**
+	 * Defines the maximum length for which a substring search is accurate.
+	 * Searches with longer substring will shorten the substring to this length.
+	 */
+	int max_substring_len;
+
 	bnode *tmp;
 	bnode *tmp2;
 	bnode *tmp3;
@@ -704,6 +710,7 @@
 
 	idx->tmp->leaf = 1;
 	idx->root_node = bnode_add_block(idx, idx->tmp);
+	idx->max_substring_len = 32;
 
 	return &idx->index;
 bailout:

[Simplemail-cvs] simplemail index_external.c,1.35,1.36

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24178

Modified Files:
	index_external.c 
Log Message:
Replaced simple linear search with a more efficient binary search.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.35
retrieving revision 1.36
diff -u -d -r1.35 -r1.36
--- index_external.c	19 Jan 2014 18:45:06 -0000	1.35
+++ index_external.c	19 Jan 2014 18:45:31 -0000	1.36
@@ -248,25 +248,35 @@
  */
 static int bnode_find_separation_slot(struct index_external *idx, bnode *tmp, const char *text, int *out_slot, int *out_directmatch)
 {
-	int i;
+	int l, h, hcmp;
 
-	*out_directmatch = 0;
+	/* Variable l is inclusive, h is exclusive */
+	l = 0;
+	h = tmp->num_elements;
+	hcmp = 1;
 
-	/* Find the appropriate slot. TODO: Use binary search */
-	for (i=0; i < tmp->num_elements; i++)
+	while (l < h)
 	{
 		int cmp;
-		struct bnode_element *e = bnode_get_ith_element_of_node(idx, tmp, i);
+		int m = (l + h)/2;
+
+		struct bnode_element *e = bnode_get_ith_element_of_node(idx, tmp, m);
 		if (!bnode_compare_string(idx, e, text, &cmp))
 			return 0;
 
-		if (cmp >= 0)
+		/* < results in getting the first element. We could also use <= to get the last element */
+		if (cmp < 0)
 		{
-			*out_directmatch = cmp == 0;
-			break;
+			l = m + 1;
+		} else
+		{
+			h = m;
+			hcmp = cmp;
 		}
 	}
-	*out_slot = i;
+
+	*out_slot = h;
+	*out_directmatch = hcmp == 0;
 	return 1;
 }
 

[Simplemail-cvs] simplemail index_external.c,1.34,1.35

[Sebastian B. <sb...@us...>]

Update of /cvsroot/simplemail/simplemail
In directory sfp-cvs-1.v30.ch3.sourceforge.com:/tmp/cvs-serv24142

Modified Files:
	index_external.c 
Log Message:
Refactored the finding of the separation slot into an own function.


Index: index_external.c
===================================================================
RCS file: /cvsroot/simplemail/simplemail/index_external.c,v
retrieving revision 1.34
retrieving revision 1.35
diff -u -d -r1.34 -r1.35
--- index_external.c	19 Jan 2014 18:44:43 -0000	1.34
+++ index_external.c	19 Jan 2014 18:45:06 -0000	1.35
@@ -231,6 +231,45 @@
 	} node[BNODE_PATH_MAX_NODES];
 };
 
+
+
+/**
+ * Find the slot with the separation key for the given text. The slot with
+ * the separation key for a given text is the slot whose value is not
+ * lexicographically smaller than the text but whose left neighbor slot value
+ * is lexicographically smaller than the text.
+ *
+ * @param idx
+ * @param tmp
+ * @param text
+ * @param out_slot
+ * @param out_directmatch
+ * @return
+ */
+static int bnode_find_separation_slot(struct index_external *idx, bnode *tmp, const char *text, int *out_slot, int *out_directmatch)
+{
+	int i;
+
+	*out_directmatch = 0;
+
+	/* Find the appropriate slot. TODO: Use binary search */
+	for (i=0; i < tmp->num_elements; i++)
+	{
+		int cmp;
+		struct bnode_element *e = bnode_get_ith_element_of_node(idx, tmp, i);
+		if (!bnode_compare_string(idx, e, text, &cmp))
+			return 0;
+
+		if (cmp >= 0)
+		{
+			*out_directmatch = cmp == 0;
+			break;
+		}
+	}
+	*out_slot = i;
+	return 1;
+}
+
 /**
  * Lookup the given text.
  *
@@ -254,27 +293,8 @@
 
 		bnode_read_block(idx, tmp, block);
 
-		/* Find the slot with the separation key for the given text. The slot with
-		 * the separation key for a given text is the slot whose value is not
-		 * lexicographically smaller than the text but whose left neighbor slot value
-		 * is lexicographically smaller than the text.
-		 *
-		 * TODO: Use binary search
-		 */
-		for (i=0; i < tmp->num_elements; i++)
-		{
-			int cmp;
-			struct bnode_element *e = bnode_get_ith_element_of_node(idx, tmp, i);
-			if (!bnode_compare_string(idx, e, text, &cmp))
-				return 0;
-
-			/* if str > text then we ascend to lchild (except if we are at a leaf, of course) */
-			if (cmp >= 0)
-			{
-				direct_match = cmp == 0;
-				break;
-			}
-		}
+		if (!bnode_find_separation_slot(idx, tmp, text, &i, &direct_match))
+			return 0;
 
 		if (i == 0) lchild = tmp->lchild;
 		else lchild = bnode_get_ith_element_of_node(idx, tmp, i - 1)->gchild;