Get rid of crazy empty tag_list element at the start

Linus Torvalds torvalds at linux-foundation.org
Mon Mar 10 09:42:23 PDT 2014


So this is totally unrelated to the git repository format, except for
the fact that I noticed it while writing the git saving code.

The subsurface divetag list handling is being stupid, and has a
initial dummy entry at the head of the list for no good reason.

I say "no good reason", because there *is* a reason for it: it allows
code to avoid the special case of empty list and adding entries to
before the first entry etc etc.  But that reason is a really *bad*
reason, because it's valid only because people don't understand basic
list manipulation and pointers to pointers.

So get rid of the dummy element, and do things right instead - by
passing a *pointer* to the list, instead of the list. And then when
traversing the list and looking for a place to insert things, don't go
to the next entry - just update the "pointer to pointer" to point to
the address of the next entry. Each entry in a C linked list is no
different than the list itself, so you can use the pointer to the
pointer to the next entry as a pointer to the list.

This is a pet peeve of mine. The real beauty of pointers can never be
understood unless you understand the indirection they allow. People
who grew up with Pascal and were corrupted by that mindset are
mentally stunted. Niklaus Wirth has a lot to answer for!

But never fear. You too can overcome that mental limitation, it just
needs some brain exercise. Reading this patch may help. In particular,
contemplate the new "taglist_add_divetag()".

Signed-off-by: Linus Torvalds <torvalds at linux-foundation.org>
---

Ok, I'll admit that I didn't test this heavily, but I couldn't take
that dummy entry any more.
-------------- next part --------------
 dive.c            | 109 ++++++++++++++++++++----------------------------------
 dive.h            |   7 +---
 divelist.c        |   7 +---
 main.cpp          |   1 -
 parse-xml.c       |   6 +--
 qt-ui/maintab.cpp |   5 ++-
 save-git.c        |   4 --
 save-xml.c        |  32 ++++++----------
 8 files changed, 61 insertions(+), 110 deletions(-)

diff --git a/dive.c b/dive.c
index a402f9932b8a..6deee8b089bc 100644
--- a/dive.c
+++ b/dive.c
@@ -206,7 +206,6 @@ struct dive *alloc_dive(void)
 	if (!dive)
 		exit(1);
 	memset(dive, 0, sizeof(*dive));
-	taglist_init(&(dive->tag_list));
 	return dive;
 }
 
@@ -1954,7 +1953,7 @@ int taglist_get_tagstring(struct tag_entry *tag_list, char *buffer, int len)
 {
 	int i = 0;
 	struct tag_entry *tmp;
-	tmp = tag_list->next;
+	tmp = tag_list;
 	memset(buffer, 0, len);
 	while (tmp != NULL) {
 		int newlength = strlen(tmp->tag->name);
@@ -1976,21 +1975,6 @@ int taglist_get_tagstring(struct tag_entry *tag_list, char *buffer, int len)
 	return i;
 }
 
-struct divetag *taglist_get_tag(struct tag_entry *tag_list, const char *tag)
-{
-	struct tag_entry *tmp;
-	tmp = tag_list->next;
-	while (tmp != NULL) {
-		if (tmp->tag != NULL) {
-			if (strcmp(tmp->tag->name, tag) == 0)
-				return tmp->tag;
-			else
-				tmp = tmp->next;
-		}
-	}
-	return NULL;
-}
-
 static inline void taglist_free_divetag(struct divetag *tag)
 {
 	if (tag->name != NULL)
@@ -2001,29 +1985,32 @@ static inline void taglist_free_divetag(struct divetag *tag)
 }
 
 /* Add a tag to the tag_list, keep the list sorted */
-static struct divetag *taglist_add_divetag(struct tag_entry *tag_list, struct divetag *tag)
-{
-	struct tag_entry *tmp, *last;
-	last = tag_list;
-	tmp = tag_list->next;
-	while (1) {
-		if (tmp == NULL || strcmp(tmp->tag->name, tag->name) > 0) {
-			/* Insert in front of it */
-			last->next = malloc(sizeof(struct tag_entry));
-			last->next->next = tmp;
-			last->next->tag = tag;
-			return last->next->tag;
-		} else if (strcmp(tmp->tag->name, tag->name) == 0) {
-			/* Already in list */
-			return tmp->tag;
-		} else {
-			last = tmp;
-			tmp = tmp->next;
-		}
+static struct divetag *taglist_add_divetag(struct tag_entry **tag_list, struct divetag *tag)
+{
+	struct tag_entry *next, *entry;
+
+	while ((next = *tag_list) != NULL) {
+		int cmp = strcmp(next->tag->name, tag->name);
+
+		/* Already have it? */
+		if (!cmp)
+			return next->tag;
+		/* Is the entry larger? If so, insert here */
+		if (cmp > 0)
+			break;
+		/* Continue traversing the list */
+		tag_list = &next->next;
 	}
+
+	/* Insert in front of it */
+	entry = malloc(sizeof(struct tag_entry));
+	entry->next = next;
+	entry->tag = tag;
+	*tag_list = entry;
+	return tag;
 }
 
-struct divetag *taglist_add_tag(struct tag_entry *tag_list, const char *tag)
+struct divetag *taglist_add_tag(struct tag_entry **tag_list, const char *tag)
 {
 	int i = 0, is_default_tag = 0;
 	struct divetag *ret_tag, *new_tag;
@@ -2049,8 +2036,8 @@ struct divetag *taglist_add_tag(struct tag_entry *tag_list, const char *tag)
 		memcpy(new_tag->name, tag, strlen(tag) + 1);
 	}
 	/* Try to insert new_tag into g_tag_list if we are not operating on it */
-	if (tag_list != g_tag_list) {
-		ret_tag = taglist_add_divetag(g_tag_list, new_tag);
+	if (tag_list != &g_tag_list) {
+		ret_tag = taglist_add_divetag(&g_tag_list, new_tag);
 		/* g_tag_list already contains new_tag, free the duplicate */
 		if (ret_tag != new_tag)
 			taglist_free_divetag(new_tag);
@@ -2063,49 +2050,33 @@ struct divetag *taglist_add_tag(struct tag_entry *tag_list, const char *tag)
 	return ret_tag;
 }
 
-void taglist_init(struct tag_entry **tag_list)
-{
-	*tag_list = malloc(sizeof(struct tag_entry));
-	(*tag_list)->next = NULL;
-	(*tag_list)->tag = NULL;
-}
-
 /* Clear everything but the first element */
-void taglist_clear(struct tag_entry *tag_list)
+void taglist_free(struct tag_entry *entry)
 {
-	struct tag_entry *current_tag_entry, *next;
-	current_tag_entry = tag_list->next;
-	while (current_tag_entry != NULL) {
-		next = current_tag_entry->next;
-		free(current_tag_entry);
-		current_tag_entry = next;
+	while (entry) {
+		struct tag_entry *next = entry->next;
+		free(entry);
+		entry = next;
 	}
-	tag_list->next = NULL;
 }
 
 /* Merge src1 and src2, write to *dst */
-static void taglist_merge(struct tag_entry *dst, struct tag_entry *src1, struct tag_entry *src2)
+static void taglist_merge(struct tag_entry **dst, struct tag_entry *src1, struct tag_entry *src2)
 {
-	struct tag_entry *current_tag_entry;
-	current_tag_entry = src1->next;
-	while (current_tag_entry != NULL) {
-		taglist_add_divetag(dst, current_tag_entry->tag);
-		current_tag_entry = current_tag_entry->next;
-	}
-	current_tag_entry = src2->next;
-	while (current_tag_entry != NULL) {
-		taglist_add_divetag(dst, current_tag_entry->tag);
-		current_tag_entry = current_tag_entry->next;
-	}
+	struct tag_entry *entry;
+
+	for (entry = src1; entry; entry = entry->next)
+		taglist_add_divetag(dst, entry->tag);
+	for (entry = src2; entry; entry = entry->next)
+		taglist_add_divetag(dst, entry->tag);
 }
 
 void taglist_init_global()
 {
 	int i;
-	taglist_init(&g_tag_list);
 
 	for (i = 0; i < sizeof(default_tags) / sizeof(char *); i++)
-		taglist_add_tag(g_tag_list, default_tags[i]);
+		taglist_add_tag(&g_tag_list, default_tags[i]);
 }
 
 struct dive *merge_dives(struct dive *a, struct dive *b, int offset, bool prefer_downloaded)
@@ -2144,7 +2115,7 @@ struct dive *merge_dives(struct dive *a, struct dive *b, int offset, bool prefer
 	MERGE_MAX(res, a, b, number);
 	MERGE_NONZERO(res, a, b, cns);
 	MERGE_NONZERO(res, a, b, visibility);
-	taglist_merge(res->tag_list, a->tag_list, b->tag_list);
+	taglist_merge(&res->tag_list, a->tag_list, b->tag_list);
 	merge_equipment(res, a, b);
 	merge_airtemps(res, a, b);
 	if (dl) {
diff --git a/dive.h b/dive.h
index 6d6edaae9dbd..cba65f50f150 100644
--- a/dive.h
+++ b/dive.h
@@ -315,7 +315,7 @@ struct tag_entry {
 
 extern struct tag_entry *g_tag_list;
 
-struct divetag *taglist_add_tag(struct tag_entry *tag_list, const char *tag);
+struct divetag *taglist_add_tag(struct tag_entry **tag_list, const char *tag);
 
 /*
  * Writes all divetags in tag_list to buffer, limited by the buffer's (len)gth.
@@ -323,10 +323,7 @@ struct divetag *taglist_add_tag(struct tag_entry *tag_list, const char *tag);
  */
 int taglist_get_tagstring(struct tag_entry *tag_list, char *buffer, int len);
 
-void taglist_init(struct tag_entry **tag_list);
-void taglist_clear(struct tag_entry *tag_list);
-void taglist_init_global();
-
+void taglist_free(struct tag_entry *tag_list);
 
 /*
  * Events are currently pretty meaningless. This is
diff --git a/divelist.c b/divelist.c
index 8bad4828d653..17f24ef7e539 100644
--- a/divelist.c
+++ b/divelist.c
@@ -744,11 +744,8 @@ void delete_single_dive(int idx)
 		free((void *)dive->buddy);
 	if (dive->suit)
 		free((void *)dive->suit);
-	if (dive->tag_list) {
-		taglist_clear(dive->tag_list);
-		/* Remove head of list */
-		free((void *)dive->tag_list);
-	}
+	if (dive->tag_list)
+		taglist_free(dive->tag_list);
 	free(dive);
 }
 
diff --git a/main.cpp b/main.cpp
index 22969605564e..f7fe3c2d235f 100644
--- a/main.cpp
+++ b/main.cpp
@@ -24,7 +24,6 @@ int main(int argc, char **argv)
 	fill_profile_color();
 	init_ui(&argc, &argv);
 	parse_xml_init();
-	taglist_init_global();
 
 	QStringList files;
 	QStringList importedFiles;
diff --git a/parse-xml.c b/parse-xml.c
index a2c73d31c802..d3ff03d2c297 100644
--- a/parse-xml.c
+++ b/parse-xml.c
@@ -221,7 +221,7 @@ enum ParseState {
 };
 static void divetags(char *buffer, void *_tags)
 {
-	struct tag_entry *tags = _tags;
+	struct tag_entry **tags = _tags;
 	int i = 0, start = 0, end = 0;
 	enum ParseState state = FINDEND;
 	int len = buffer ? strlen(buffer) : 0;
@@ -1089,7 +1089,7 @@ static void try_to_fill_dive(struct dive *dive, const char *name, char *buf)
 
 	if (MATCH("number", get_index, &dive->number))
 		return;
-	if (MATCH("tags", divetags, dive->tag_list))
+	if (MATCH("tags", divetags, &dive->tag_list))
 		return;
 	if (MATCH("tripflag", get_tripflag, &dive->tripflag))
 		return;
@@ -1738,7 +1738,7 @@ extern int dm4_events(void *handle, int columns, char **data, char **column)
 extern int dm4_tags(void *handle, int columns, char **data, char **column)
 {
 	if (data[0])
-		taglist_add_tag(cur_dive->tag_list, data[0]);
+		taglist_add_tag(&cur_dive->tag_list, data[0]);
 
 	return 0;
 }
diff --git a/qt-ui/maintab.cpp b/qt-ui/maintab.cpp
index 847cf5ec70d8..068d703a3404 100644
--- a/qt-ui/maintab.cpp
+++ b/qt-ui/maintab.cpp
@@ -873,9 +873,10 @@ void MainTab::saveTags()
 {
 	EDIT_SELECTED_DIVES(
 	    QString tag;
-	    taglist_clear(mydive->tag_list);
+	    taglist_free(mydive->tag_list);
+	    mydive->tag_list = NULL;
 	    foreach(tag, ui.tagWidget->getBlockStringList())
-		    taglist_add_tag(mydive->tag_list, tag.toUtf8().data()););
+		    taglist_add_tag(&mydive->tag_list, tag.toUtf8().data()););
 }
 
 void MainTab::on_tagWidget_textChanged()
diff --git a/save-git.c b/save-git.c
index 990364eba108..3ec610b39d70 100644
--- a/save-git.c
+++ b/save-git.c
@@ -111,10 +111,6 @@ static void save_tags(struct membuffer *b, struct tag_entry *tags)
 
 	if (!tags)
 		return;
-	/* The first entry is a dummy, because people don't understand pointers to pointers */
-	tags = tags->next;
-	if (!tags)
-		return;
 	put_string(b, "tags");
 	while (tags) {
 		show_utf8(b, sep, tags->tag->source ? : tags->tag->name, "");
diff --git a/save-xml.c b/save-xml.c
index 7801080e9d84..f5d17c49cb6a 100644
--- a/save-xml.c
+++ b/save-xml.c
@@ -332,27 +332,18 @@ static void save_events(struct membuffer *b, struct event *ev)
 	}
 }
 
-static void save_tags(struct membuffer *b, struct tag_entry *tag_list)
+static void save_tags(struct membuffer *b, struct tag_entry *entry)
 {
-	int more = 0;
-	struct tag_entry *tmp = tag_list->next;
-
-	/* Only write tag attribute if the list contains at least one item  */
-	if (tmp != NULL) {
-		put_format(b, " tags='");
-
-		while (tmp != NULL) {
-			if (more)
-				put_format(b, ", ");
+	if (entry) {
+		const char *sep = " tags='";
+		do {
+			struct divetag *tag = entry->tag;
+			put_string(b, sep);
 			/* If the tag has been translated, write the source to the xml file */
-			if (tmp->tag->source != NULL)
-				quote(b, tmp->tag->source, 0);
-			else
-				quote(b, tmp->tag->name, 0);
-			tmp = tmp->next;
-			more = 1;
-		}
-		put_format(b, "'");
+			quote(b, tag->source ?: tag->name, 0);
+			sep = ", ";
+		} while ((entry = entry->next) != NULL);
+		put_string(b, "'");
 	}
 }
 
@@ -416,8 +407,7 @@ void save_one_dive(struct membuffer *b, struct dive *dive)
 		put_format(b, " rating='%d'", dive->rating);
 	if (dive->visibility)
 		put_format(b, " visibility='%d'", dive->visibility);
-	if (dive->tag_list != NULL)
-		save_tags(b, dive->tag_list);
+	save_tags(b, dive->tag_list);
 
 	show_date(b, dive->when);
 	put_format(b, " duration='%u:%02u min'>\n",


More information about the subsurface mailing list