From: Austin Clements <amdragon@MIT.EDU>
To: notmuch@notmuchmail.org
Subject: [PATCH 2/5] Implement an internal generic string list and use it.
Date: Thu,  9 Dec 2010 15:59:53 -0500
Message-Id: <1291928396-27937-3-git-send-email-amdragon@mit.edu>
In-Reply-To: <1291928396-27937-1-git-send-email-amdragon@mit.edu>
References: <1291928396-27937-1-git-send-email-amdragon@mit.edu>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Cc: Austin Clements <amdragon@mit.edu>
Precedence: list

This replaces the guts of the filename list and tag list, making those
interfaces simple iterators over the generic string list.  The
directory, message filename, and tags-related code now build generic
string lists and then wraps them in specific iterators.  The real wins
come in later patches, when we use these for even more generic
functionality.

As a nice side-effect, this also eliminates the annoying dependency on
GList in the tag list.
---
 lib/Makefile.local    |    1 +
 lib/database.cc       |   12 +++---
 lib/directory.cc      |    7 ++--
 lib/filenames.c       |   52 +++------------------------
 lib/message.cc        |   15 ++++----
 lib/messages.c        |   11 +++---
 lib/notmuch-private.h |   68 +++++++++++++++++++++--------------
 lib/strings.c         |   94 +++++++++++++++++++++++++++++++++++++++++++++++++
 lib/tags.c            |   63 ++++++--------------------------
 lib/thread.cc         |   10 +++---
 10 files changed, 179 insertions(+), 154 deletions(-)
 create mode 100644 lib/strings.c

diff --git a/lib/Makefile.local b/lib/Makefile.local
index 5233ea6..37d1c0d 100644
--- a/lib/Makefile.local
+++ b/lib/Makefile.local
@@ -50,6 +50,7 @@ extra_cflags += -I$(dir) -fPIC
 libnotmuch_c_srcs =		\
 	$(notmuch_compat_srcs)	\
 	$(dir)/filenames.c	\
+	$(dir)/strings.c	\
 	$(dir)/libsha1.c	\
 	$(dir)/message-file.c	\
 	$(dir)/messages.c	\
diff --git a/lib/database.cc b/lib/database.cc
index 7a00917..45613bd 100644
--- a/lib/database.cc
+++ b/lib/database.cc
@@ -1752,15 +1752,15 @@ _notmuch_convert_tags (void *ctx, Xapian::TermIterator &i,
 		       Xapian::TermIterator &end)
 {
     const char *prefix = _find_prefix ("tag");
-    notmuch_tags_t *tags;
+    notmuch_string_list_t *list;
     std::string tag;
 
     /* Currently this iteration is written with the assumption that
      * "tag" has a single-character prefix. */
     assert (strlen (prefix) == 1);
 
-    tags = _notmuch_tags_create (ctx);
-    if (unlikely (tags == NULL))
+    list = _notmuch_string_list_create (ctx);
+    if (unlikely (list == NULL))
 	return NULL;
 
     i.skip_to (prefix);
@@ -1771,14 +1771,14 @@ _notmuch_convert_tags (void *ctx, Xapian::TermIterator &i,
 	if (tag.empty () || tag[0] != *prefix)
 	    break;
 
-	_notmuch_tags_add_tag (tags, tag.c_str () + 1);
+	_notmuch_string_list_append (list, tag.c_str () + 1);
 
 	i++;
     }
 
-    _notmuch_tags_prepare_iterator (tags);
+    _notmuch_string_list_sort (list);
 
-    return tags;
+    return _notmuch_tags_create (ctx, list, TRUE);
 }
 
 notmuch_tags_t *
diff --git a/lib/directory.cc b/lib/directory.cc
index 946be4f..aeee9ca 100644
--- a/lib/directory.cc
+++ b/lib/directory.cc
@@ -33,11 +33,11 @@ _create_filenames_for_terms_with_prefix (void *ctx,
 					 notmuch_database_t *notmuch,
 					 const char *prefix)
 {
-    notmuch_filename_list_t *filename_list;
+    notmuch_string_list_t *filename_list;
     Xapian::TermIterator i, end;
     int prefix_len = strlen (prefix);
 
-    filename_list = _notmuch_filename_list_create (ctx);
+    filename_list = _notmuch_string_list_create (ctx);
     if (unlikely (filename_list == NULL))
 	return NULL;
 
@@ -47,8 +47,7 @@ _create_filenames_for_terms_with_prefix (void *ctx,
     {
 	std::string term = *i;
 
-	_notmuch_filename_list_add_filename (filename_list, term.c_str () +
-					     prefix_len);
+	_notmuch_string_list_append (filename_list, term.c_str () + prefix_len);
     }
 
     return _notmuch_filenames_create (ctx, filename_list);
diff --git a/lib/filenames.c b/lib/filenames.c
index f078c95..f1ea243 100644
--- a/lib/filenames.c
+++ b/lib/filenames.c
@@ -21,56 +21,14 @@
 #include "notmuch-private.h"
 
 struct _notmuch_filenames {
-    notmuch_filename_node_t *iterator;
+    notmuch_string_node_t *iterator;
 };
 
-/* Create a new notmuch_filename_list_t object, with 'ctx' as its
- * talloc owner.
- *
- * This function can return NULL in case of out-of-memory.
- */
-notmuch_filename_list_t *
-_notmuch_filename_list_create (const void *ctx)
-{
-    notmuch_filename_list_t *list;
-
-    list = talloc (ctx, notmuch_filename_list_t);
-    if (unlikely (list == NULL))
-	return NULL;
-
-    list->head = NULL;
-    list->tail = &list->head;
-
-    return list;
-}
-
-void
-_notmuch_filename_list_add_filename (notmuch_filename_list_t *list,
-				     const char *filename)
-{
-    /* Create and initialize new node. */
-    notmuch_filename_node_t *node = talloc (list,
-					    notmuch_filename_node_t);
-
-    node->filename = talloc_strdup (node, filename);
-    node->next = NULL;
-
-    /* Append the node to the list. */
-    *(list->tail) = node;
-    list->tail = &node->next;
-}
-
-void
-_notmuch_filename_list_destroy (notmuch_filename_list_t *list)
-{
-    talloc_free (list);
-}
-
-/* The notmuch_filenames_t is an iterator object for a
- * notmuch_filename_list_t */
+/* The notmuch_filenames_t iterates over a notmuch_string_list_t of
+ * file names */
 notmuch_filenames_t *
 _notmuch_filenames_create (const void *ctx,
-			   notmuch_filename_list_t *list)
+			   notmuch_string_list_t *list)
 {
     notmuch_filenames_t *filenames;
 
@@ -99,7 +57,7 @@ notmuch_filenames_get (notmuch_filenames_t *filenames)
     if (filenames->iterator == NULL)
 	return NULL;
 
-    return filenames->iterator->filename;
+    return filenames->iterator->string;
 }
 
 void
diff --git a/lib/message.cc b/lib/message.cc
index d6ab636..031eda5 100644
--- a/lib/message.cc
+++ b/lib/message.cc
@@ -32,7 +32,7 @@ struct _notmuch_message {
     char *message_id;
     char *thread_id;
     char *in_reply_to;
-    notmuch_filename_list_t *filename_list;
+    notmuch_string_list_t *filename_list;
     char *author;
     notmuch_message_file_t *message_file;
     notmuch_message_list_t *replies;
@@ -434,7 +434,7 @@ _notmuch_message_add_filename (notmuch_message_t *message,
     char *direntry;
 
     if (message->filename_list) {
-	_notmuch_filename_list_destroy (message->filename_list);
+	talloc_free (message->filename_list);
 	message->filename_list = NULL;
     }
 
@@ -511,7 +511,7 @@ _notmuch_message_ensure_filename_list (notmuch_message_t *message)
     if (message->filename_list)
 	return;
 
-    message->filename_list = _notmuch_filename_list_create (message);
+    message->filename_list = _notmuch_string_list_create (message);
 
     i = message->doc.termlist_begin ();
     i.skip_to (prefix);
@@ -532,7 +532,7 @@ _notmuch_message_ensure_filename_list (notmuch_message_t *message)
 	if (data == NULL)
 	    INTERNAL_ERROR ("message with no filename");
 
-	_notmuch_filename_list_add_filename (message->filename_list, data);
+	_notmuch_string_list_append (message->filename_list, data);
 
 	return;
     }
@@ -573,8 +573,7 @@ _notmuch_message_ensure_filename_list (notmuch_message_t *message)
 	    filename = talloc_asprintf (message, "%s/%s",
 					db_path, basename);
 
-	_notmuch_filename_list_add_filename (message->filename_list,
-					     filename);
+	_notmuch_string_list_append (message->filename_list, filename);
 
 	talloc_free (local);
     }
@@ -589,12 +588,12 @@ notmuch_message_get_filename (notmuch_message_t *message)
 	return NULL;
 
     if (message->filename_list->head == NULL ||
-	message->filename_list->head->filename == NULL)
+	message->filename_list->head->string == NULL)
     {
 	INTERNAL_ERROR ("message with no filename");
     }
 
-    return message->filename_list->head->filename;
+    return message->filename_list->head->string;
 }
 
 notmuch_filenames_t *
diff --git a/lib/messages.c b/lib/messages.c
index 120a48a..404e8b3 100644
--- a/lib/messages.c
+++ b/lib/messages.c
@@ -146,13 +146,14 @@ notmuch_messages_destroy (notmuch_messages_t *messages)
 notmuch_tags_t *
 notmuch_messages_collect_tags (notmuch_messages_t *messages)
 {
-    notmuch_tags_t *tags, *msg_tags;
+    notmuch_string_list_t *tags;
+    notmuch_tags_t *msg_tags;
     notmuch_message_t *msg;
     GHashTable *htable;
     GList *keys, *l;
     const char *tag;
 
-    tags = _notmuch_tags_create (messages);
+    tags = _notmuch_string_list_create (messages);
     if (tags == NULL) return NULL;
 
     htable = g_hash_table_new_full (g_str_hash, g_str_equal, free, NULL);
@@ -170,12 +171,12 @@ notmuch_messages_collect_tags (notmuch_messages_t *messages)
 
     keys = g_hash_table_get_keys (htable);
     for (l = keys; l; l = l->next) {
-	_notmuch_tags_add_tag (tags, (char *)l->data);
+	_notmuch_string_list_append (tags, (char *)l->data);
     }
 
     g_list_free (keys);
     g_hash_table_destroy (htable);
 
-    _notmuch_tags_prepare_iterator (tags);
-    return tags;
+    _notmuch_string_list_sort (tags);
+    return _notmuch_tags_create (messages, tags, TRUE);
 }
diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h
index 303aeb3..b6f1095 100644
--- a/lib/notmuch-private.h
+++ b/lib/notmuch-private.h
@@ -453,48 +453,60 @@ notmuch_sha1_of_string (const char *str);
 char *
 notmuch_sha1_of_file (const char *filename);
 
-/* tags.c */
+/* strings.c */
 
-notmuch_tags_t *
-_notmuch_tags_create (void *ctx);
+typedef struct _notmuch_string_node {
+    char *string;
+    struct _notmuch_string_node *next;
+} notmuch_string_node_t;
+
+typedef struct _notmuch_string_list {
+    int length;
+    notmuch_string_node_t *head;
+    notmuch_string_node_t **tail;
+} notmuch_string_list_t;
 
+notmuch_string_list_t *
+_notmuch_string_list_create (const void *ctx);
+
+/* Add 'string' to 'list'.
+ *
+ * The list will create its own talloced copy of 'string'.
+ */
 void
-_notmuch_tags_add_tag (notmuch_tags_t *tags, const char *tag);
+_notmuch_string_list_append (notmuch_string_list_t *list,
+			     const char *string);
 
 void
-_notmuch_tags_prepare_iterator (notmuch_tags_t *tags);
+_notmuch_string_list_sort (notmuch_string_list_t *list);
 
-/* filenames.c */
+/* tags.c */
+
+notmuch_tags_t *
+_notmuch_tags_create (const void *ctx, notmuch_string_list_t *list,
+		      notmuch_bool_t steal);
 
-typedef struct _notmuch_filename_node {
-    char *filename;
-    struct _notmuch_filename_node *next;
-} notmuch_filename_node_t;
+/* filenames.c */
 
-typedef struct _notmuch_filename_list {
-    notmuch_filename_node_t *head;
-    notmuch_filename_node_t **tail;
-} notmuch_filename_list_t;
+/* The notmuch_filenames_t iterates over a notmuch_string_list_t of
+ * file names */
+notmuch_filenames_t *
+_notmuch_filenames_create (const void *ctx,
+			   notmuch_string_list_t *list);
 
-notmuch_filename_list_t *
-_notmuch_filename_list_create (const void *ctx);
+/* tags.c */
 
-/* Add 'filename' to 'list'.
- *
- * The list will create its own talloced copy of 'filename'.
- */
-void
-_notmuch_filename_list_add_filename (notmuch_filename_list_t *list,
-				     const char *filename);
+notmuch_tags_t *
+_notmuch_tags_create (const void *ctx, notmuch_string_list_t *list,
+		      notmuch_bool_t steal);
 
-void
-_notmuch_filename_list_destroy (notmuch_filename_list_t *list);
+/* filenames.c */
 
-/* The notmuch_filenames_t is an iterator object for a
- * notmuch_filename_list_t */
+/* The notmuch_filenames_t iterates over a notmuch_string_list_t of
+ * file names */
 notmuch_filenames_t *
 _notmuch_filenames_create (const void *ctx,
-			   notmuch_filename_list_t *list);
+			   notmuch_string_list_t *list);
 
 #pragma GCC visibility pop
 
diff --git a/lib/strings.c b/lib/strings.c
new file mode 100644
index 0000000..d92a0ba
--- /dev/null
+++ b/lib/strings.c
@@ -0,0 +1,94 @@
+/* strings.c - Iterator for a list of strings
+ *
+ * Copyright © 2010 Intel Corporation
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see http://www.gnu.org/licenses/ .
+ *
+ * Author: Carl Worth <cworth@cworth.org>
+ */
+
+#include "notmuch-private.h"
+
+/* Create a new notmuch_string_list_t object, with 'ctx' as its
+ * talloc owner.
+ *
+ * This function can return NULL in case of out-of-memory.
+ */
+notmuch_string_list_t *
+_notmuch_string_list_create (const void *ctx)
+{
+    notmuch_string_list_t *list;
+
+    list = talloc (ctx, notmuch_string_list_t);
+    if (unlikely (list == NULL))
+	return NULL;
+
+    list->length = 0;
+    list->head = NULL;
+    list->tail = &list->head;
+
+    return list;
+}
+
+void
+_notmuch_string_list_append (notmuch_string_list_t *list,
+			     const char *string)
+{
+    /* Create and initialize new node. */
+    notmuch_string_node_t *node = talloc (list, notmuch_string_node_t);
+
+    node->string = talloc_strdup (node, string);
+    node->next = NULL;
+
+    /* Append the node to the list. */
+    *(list->tail) = node;
+    list->tail = &node->next;
+    list->length++;
+}
+
+static int
+cmpnode (const void *pa, const void *pb)
+{
+    notmuch_string_node_t *a = *(notmuch_string_node_t * const *)pa;
+    notmuch_string_node_t *b = *(notmuch_string_node_t * const *)pb;
+
+    return strcmp (a->string, b->string);
+}
+
+void
+_notmuch_string_list_sort (notmuch_string_list_t *list)
+{
+    notmuch_string_node_t **nodes, *node;
+    int i;
+
+    if (list->length == 0)
+	return;
+
+    nodes = talloc_array (list, notmuch_string_node_t *, list->length);
+    if (unlikely (nodes == NULL))
+	INTERNAL_ERROR ("Could not allocate memory for list sort");
+
+    for (i = 0, node = list->head; node; i++, node = node->next)
+	nodes[i] = node;
+
+    qsort (nodes, list->length, sizeof (*nodes), cmpnode);
+
+    for (i = 0; i < list->length - 1; ++i)
+	nodes[i]->next = nodes[i+1];
+    nodes[i]->next = NULL;
+    list->head = nodes[0];
+    list->tail = &nodes[i]->next;
+
+    talloc_free (nodes);
+}
diff --git a/lib/tags.c b/lib/tags.c
index 8fe4a3f..8392ef6 100644
--- a/lib/tags.c
+++ b/lib/tags.c
@@ -20,30 +20,20 @@
 
 #include "notmuch-private.h"
 
-#include <glib.h> /* GList */
-
 struct _notmuch_tags {
-    int sorted;
-    GList *tags;
-    GList *iterator;
+    notmuch_string_node_t *iterator;
 };
 
-/* XXX: Should write some talloc-friendly list to avoid the need for
- * this. */
-static int
-_notmuch_tags_destructor (notmuch_tags_t *tags)
-{
-    g_list_free (tags->tags);
-
-    return 0;
-}
-
 /* Create a new notmuch_tags_t object, with 'ctx' as its talloc owner.
+ * If steal is true, then the iterator will steal the reference to the
+ * list (useful for one-shot iterators); otherwise it will add a
+ * reference.
  *
  * This function can return NULL in case of out-of-memory.
  */
 notmuch_tags_t *
-_notmuch_tags_create (void *ctx)
+_notmuch_tags_create (const void *ctx, notmuch_string_list_t *list,
+		      notmuch_bool_t steal)
 {
     notmuch_tags_t *tags;
 
@@ -51,44 +41,15 @@ _notmuch_tags_create (void *ctx)
     if (unlikely (tags == NULL))
 	return NULL;
 
-    talloc_set_destructor (tags, _notmuch_tags_destructor);
-
-    tags->sorted = 1;
-    tags->tags = NULL;
-    tags->iterator = NULL;
+    tags->iterator = list->head;
+    if (steal)
+	talloc_steal (tags, list);
+    else
+	(void) talloc_reference (tags, list);
 
     return tags;
 }
 
-/* Add a new tag to 'tags'. The tags object will create its own copy
- * of the string.
- *
- * Note: The tags object will not do anything to prevent duplicate
- * tags being stored, so the caller really shouldn't pass
- * duplicates. */
-void
-_notmuch_tags_add_tag (notmuch_tags_t *tags, const char *tag)
-{
-    tags->tags = g_list_prepend (tags->tags, talloc_strdup (tags, tag));
-    tags->sorted = 0;
-}
-
-/* Prepare 'tag' for iteration.
- *
- * The internal creator of 'tags' should call this function before
- * returning 'tags' to the user to call the public functions such as
- * notmuch_tags_valid, notmuch_tags_get, and
- * notmuch_tags_move_to_next. */
-void
-_notmuch_tags_prepare_iterator (notmuch_tags_t *tags)
-{
-    if (! tags->sorted)
-	tags->tags = g_list_sort (tags->tags, (GCompareFunc) strcmp);
-    tags->sorted = 1;
-
-    tags->iterator = tags->tags;
-}
-
 notmuch_bool_t
 notmuch_tags_valid (notmuch_tags_t *tags)
 {
@@ -101,7 +62,7 @@ notmuch_tags_get (notmuch_tags_t *tags)
     if (tags->iterator == NULL)
 	return NULL;
 
-    return (char *) tags->iterator->data;
+    return (char *) tags->iterator->string;
 }
 
 void
diff --git a/lib/thread.cc b/lib/thread.cc
index b29f2c9..5b024fd 100644
--- a/lib/thread.cc
+++ b/lib/thread.cc
@@ -535,23 +535,23 @@ notmuch_thread_get_newest_date (notmuch_thread_t *thread)
 notmuch_tags_t *
 notmuch_thread_get_tags (notmuch_thread_t *thread)
 {
-    notmuch_tags_t *tags;
+    notmuch_string_list_t *tags;
     GList *keys, *l;
 
-    tags = _notmuch_tags_create (thread);
+    tags = _notmuch_string_list_create (thread);
     if (unlikely (tags == NULL))
 	return NULL;
 
     keys = g_hash_table_get_keys (thread->tags);
 
     for (l = keys; l; l = l->next)
-	_notmuch_tags_add_tag (tags, (char *) l->data);
+	_notmuch_string_list_append (tags, (char *) l->data);
 
     g_list_free (keys);
 
-    _notmuch_tags_prepare_iterator (tags);
+    _notmuch_string_list_sort (tags);
 
-    return tags;
+    return _notmuch_tags_create (thread, tags, true);
 }
 
 void
-- 
1.7.2.3