git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 1/5] trailer: use singly-linked list, not doubly

From
JTJonathan Tan <jonathantanmy@google.com>
Date
Oct 12, 2016, 01:23 UTC
Message-ID
<8e12e0954f0a23d7c7905c58a3f7d8084d9338be.1476232683.git.jonathantanmy@google.com>
In-Reply-To
<cover.1476232683.git.jonathantanmy@google.com>

Use singly-linked lists (instead of doubly-linked lists) in trailer to keep track of arguments (whether implicit from configuration or explicit from the command line) and trailer items.

This change significantly reduces the code length and simplifies the code.
There are now fewer pointers to be manipulated, but most trailer
manipulations now require seeking from beginning to end, so there might
be a slight net decrease in performance; however the number of trailers
is usually small (10 to 15 at the most) so this should not cause a big
impact.
---
 trailer.c | 357 ++++++++++++++++++++++----------------------------------------
 1 file changed, 125 insertions(+), 232 deletions(-)
diff --git a/trailer.c b/trailer.c
index c6ea9ac..bf3d7d0 100644
--- a/trailer.c
+++ b/trailer.c
@@ -25,7 +25,6 @@ struct conf_info {
 static struct conf_info default_conf_info;
 
 struct trailer_item {
-	struct trailer_item *previous;
 	struct trailer_item *next;
 	const char *token;
 	const char *value;
@@ -56,7 +55,8 @@ static size_t token_len_without_separator(const char *token, size_t len)
 	return len;
 }
 
-static int same_token(struct trailer_item *a, struct trailer_item *b)
+static int same_token(const struct trailer_item *a,
+		      const struct trailer_item *b)
 {
 	size_t a_len = token_len_without_separator(a->token, strlen(a->token));
 	size_t b_len = token_len_without_separator(b->token, strlen(b->token));
@@ -65,12 +65,14 @@ static int same_token(struct trailer_item *a, struct trailer_item *b)
 	return !strncasecmp(a->token, b->token, min_len);
 }
 
-static int same_value(struct trailer_item *a, struct trailer_item *b)
+static int same_value(const struct trailer_item *a,
+		      const struct trailer_item *b)
 {
 	return !strcasecmp(a->value, b->value);
 }
 
-static int same_trailer(struct trailer_item *a, struct trailer_item *b)
+static int same_trailer(const struct trailer_item *a,
+			const struct trailer_item *b)
 {
 	return same_token(a, b) && same_value(a, b);
 }
@@ -129,92 +131,6 @@ static void print_all(FILE *outfile, struct trailer_item *first, int trim_empty)
 	}
 }
 
-static void update_last(struct trailer_item **last)
-{
-	if (*last)
-		while ((*last)->next != NULL)
-			*last = (*last)->next;
-}
-
-static void update_first(struct trailer_item **first)
-{
-	if (*first)
-		while ((*first)->previous != NULL)
-			*first = (*first)->previous;
-}
-
-static void add_arg_to_input_list(struct trailer_item *on_tok,
-				  struct trailer_item *arg_tok,
-				  struct trailer_item **first,
-				  struct trailer_item **last)
-{
-	if (after_or_end(arg_tok->conf.where)) {
-		arg_tok->next = on_tok->next;
-		on_tok->next = arg_tok;
-		arg_tok->previous = on_tok;
-		if (arg_tok->next)
-			arg_tok->next->previous = arg_tok;
-		update_last(last);
-	} else {
-		arg_tok->previous = on_tok->previous;
-		on_tok->previous = arg_tok;
-		arg_tok->next = on_tok;
-		if (arg_tok->previous)
-			arg_tok->previous->next = arg_tok;
-		update_first(first);
-	}
-}
-
-static int check_if_different(struct trailer_item *in_tok,
-			      struct trailer_item *arg_tok,
-			      int check_all)
-{
-	enum action_where where = arg_tok->conf.where;
-	do {
-		if (!in_tok)
-			return 1;
-		if (same_trailer(in_tok, arg_tok))
-			return 0;
-		/*
-		 * if we want to add a trailer after another one,
-		 * we have to check those before this one
-		 */
-		in_tok = after_or_end(where) ? in_tok->previous : in_tok->next;
-	} while (check_all);
-	return 1;
-}
-
-static void remove_from_list(struct trailer_item *item,
-			     struct trailer_item **first,
-			     struct trailer_item **last)
-{
-	struct trailer_item *next = item->next;
-	struct trailer_item *previous = item->previous;
-
-	if (next) {
-		item->next->previous = previous;
-		item->next = NULL;
-	} else if (last)
-		*last = previous;
-
-	if (previous) {
-		item->previous->next = next;
-		item->previous = NULL;
-	} else if (first)
-		*first = next;
-}
-
-static struct trailer_item *remove_first(struct trailer_item **first)
-{
-	struct trailer_item *item = *first;
-	*first = item->next;
-	if (item->next) {
-		item->next->previous = NULL;
-		item->next = NULL;
-	}
-	return item;
-}
-
 static const char *apply_command(const char *command, const char *arg)
 {
 	struct strbuf cmd = STRBUF_INIT;
@@ -263,122 +179,116 @@ static void apply_item_command(struct trailer_item *in_tok, struct trailer_item
 	}
 }
 
-static void apply_arg_if_exists(struct trailer_item *in_tok,
-				struct trailer_item *arg_tok,
-				struct trailer_item *on_tok,
-				struct trailer_item **in_tok_first,
-				struct trailer_item **in_tok_last)
+static void apply_existing_arg(struct trailer_item **found_next,
+			       struct trailer_item *arg_tok,
+			       struct trailer_item **position_to_add,
+			       const struct trailer_item *in_tok_head,
+			       const struct trailer_item *neighbor)
 {
-	switch (arg_tok->conf.if_exists) {
-	case EXISTS_DO_NOTHING:
+	if (arg_tok->conf.if_exists == EXISTS_DO_NOTHING) {
 		free_trailer_item(arg_tok);
-		break;
-	case EXISTS_REPLACE:
-		apply_item_command(in_tok, arg_tok);
-		add_arg_to_input_list(on_tok, arg_tok,
-				      in_tok_first, in_tok_last);
-		remove_from_list(in_tok, in_tok_first, in_tok_last);
-		free_trailer_item(in_tok);
-		break;
-	case EXISTS_ADD:
-		apply_item_command(in_tok, arg_tok);
-		add_arg_to_input_list(on_tok, arg_tok,
-				      in_tok_first, in_tok_last);
-		break;
-	case EXISTS_ADD_IF_DIFFERENT:
-		apply_item_command(in_tok, arg_tok);
-		if (check_if_different(in_tok, arg_tok, 1))
-			add_arg_to_input_list(on_tok, arg_tok,
-					      in_tok_first, in_tok_last);
-		else
-			free_trailer_item(arg_tok);
-		break;
-	case EXISTS_ADD_IF_DIFFERENT_NEIGHBOR:
-		apply_item_command(in_tok, arg_tok);
-		if (check_if_different(on_tok, arg_tok, 0))
-			add_arg_to_input_list(on_tok, arg_tok,
-					      in_tok_first, in_tok_last);
-		else
+		return;
+	}
+
+	apply_item_command(*found_next, arg_tok);
+
+	if (arg_tok->conf.if_exists == EXISTS_ADD_IF_DIFFERENT_NEIGHBOR) {
+		if (neighbor && same_trailer(neighbor, arg_tok)) {
 			free_trailer_item(arg_tok);
-		break;
+			return;
+		}
+	} else if (arg_tok->conf.if_exists == EXISTS_ADD_IF_DIFFERENT) {
+		const struct trailer_item *in_tok;
+		for (in_tok = in_tok_head; in_tok; in_tok = in_tok->next) {
+			if (same_trailer(in_tok, arg_tok)) {
+				free_trailer_item(arg_tok);
+				return;
+			}
+		}
+	}
+
+	arg_tok->next = *position_to_add;
+	*position_to_add = arg_tok;
+
+	if (arg_tok->conf.if_exists == EXISTS_REPLACE) {
+		struct trailer_item *new_next = (*found_next)->next;
+		free_trailer_item(*found_next);
+		*found_next = new_next;
 	}
 }
 
-static void apply_arg_if_missing(struct trailer_item **in_tok_first,
-				 struct trailer_item **in_tok_last,
-				 struct trailer_item *arg_tok)
+static void apply_missing_arg(struct trailer_item *arg_tok,
+			      struct trailer_item **position_to_add)
 {
-	struct trailer_item **in_tok;
-	enum action_where where;
-
-	switch (arg_tok->conf.if_missing) {
-	case MISSING_DO_NOTHING:
+	if (arg_tok->conf.if_missing == MISSING_DO_NOTHING) {
 		free_trailer_item(arg_tok);
-		break;
-	case MISSING_ADD:
-		where = arg_tok->conf.where;
-		in_tok = after_or_end(where) ? in_tok_last : in_tok_first;
-		apply_item_command(NULL, arg_tok);
-		if (*in_tok) {
-			add_arg_to_input_list(*in_tok, arg_tok,
-					      in_tok_first, in_tok_last);
-		} else {
-			*in_tok_first = arg_tok;
-			*in_tok_last = arg_tok;
-		}
-		break;
+		return;
 	}
+
+	apply_item_command(NULL, arg_tok);
+
+	arg_tok->next = *position_to_add;
+	*position_to_add = arg_tok;
 }
 
-static int find_same_and_apply_arg(struct trailer_item **in_tok_first,
-				   struct trailer_item **in_tok_last,
-				   struct trailer_item *arg_tok)
+static void apply_arg(struct trailer_item **in_tok_head,
+		      struct trailer_item *arg_tok)
 {
-	struct trailer_item *in_tok;
-	struct trailer_item *on_tok;
-	struct trailer_item *following_tok;
-
+	struct trailer_item **next, **found_next = NULL, *last = NULL;
 	enum action_where where = arg_tok->conf.where;
-	int middle = (where == WHERE_AFTER) || (where == WHERE_BEFORE);
 	int backwards = after_or_end(where);
-	struct trailer_item *start_tok = backwards ? *in_tok_last : *in_tok_first;
 
-	for (in_tok = start_tok; in_tok; in_tok = following_tok) {
-		following_tok = backwards ? in_tok->previous : in_tok->next;
-		if (!same_token(in_tok, arg_tok))
-			continue;
-		on_tok = middle ? in_tok : start_tok;
-		apply_arg_if_exists(in_tok, arg_tok, on_tok,
-				    in_tok_first, in_tok_last);
-		return 1;
+	for (next = in_tok_head; *next; next = &(*next)->next) {
+		last = *next;
+		if ((!found_next || backwards) &&
+		    same_token(*next, arg_tok))
+			found_next = next;
+	}
+
+	if (found_next) {
+		struct trailer_item **position_to_add, *neighbor;
+		switch (where) {
+		case WHERE_START:
+			position_to_add = in_tok_head;
+			neighbor = *in_tok_head;
+			break;
+		case WHERE_BEFORE:
+			position_to_add = found_next;
+			neighbor = *found_next;
+			break;
+		case WHERE_AFTER:
+			position_to_add = &(*found_next)->next;
+			neighbor = *found_next;
+			break;
+		default:
+			position_to_add = next;
+			neighbor = last;
+			break;
+		}
+		apply_existing_arg(found_next, arg_tok, position_to_add,
+				   *in_tok_head, neighbor);
+	} else {
+		struct trailer_item **position_to_add;
+		switch (where) {
+		case WHERE_START:
+		case WHERE_BEFORE:
+			position_to_add = in_tok_head;
+			break;
+		default:
+			position_to_add = next;
+			break;
+		}
+		apply_missing_arg(arg_tok, position_to_add);
 	}
-	return 0;
 }
 
-static void process_trailers_lists(struct trailer_item **in_tok_first,
-				   struct trailer_item **in_tok_last,
-				   struct trailer_item **arg_tok_first)
+static void process_trailers_lists(struct trailer_item **in_tok_head,
+				   struct trailer_item *arg_tok_head)
 {
-	struct trailer_item *arg_tok;
-	struct trailer_item *next_arg;
-
-	if (!*arg_tok_first)
-		return;
-
-	for (arg_tok = *arg_tok_first; arg_tok; arg_tok = next_arg) {
-		int applied = 0;
-
-		next_arg = arg_tok->next;
-		remove_from_list(arg_tok, arg_tok_first, NULL);
-
-		applied = find_same_and_apply_arg(in_tok_first,
-						  in_tok_last,
-						  arg_tok);
-
-		if (!applied)
-			apply_arg_if_missing(in_tok_first,
-					     in_tok_last,
-					     arg_tok);
+	struct trailer_item *arg_tok, *next;
+	for (arg_tok = arg_tok_head; arg_tok; arg_tok = next) {
+		next = arg_tok->next;
+		apply_arg(in_tok_head, arg_tok);
 	}
 }
 
@@ -438,29 +348,19 @@ static void duplicate_conf(struct conf_info *dst, struct conf_info *src)
 
 static struct trailer_item *get_conf_item(const char *name)
 {
+	struct trailer_item **next = &first_conf_item;
 	struct trailer_item *item;
-	struct trailer_item *previous;
 
 	/* Look up item with same name */
-	for (previous = NULL, item = first_conf_item;
-	     item;
-	     previous = item, item = item->next) {
-		if (!strcasecmp(item->conf.name, name))
-			return item;
-	}
+	for (next = &first_conf_item; *next; next = &(*next)->next)
+		if (!strcasecmp((*next)->conf.name, name))
+			return *next;
 
 	/* Item does not already exists, create it */
 	item = xcalloc(sizeof(struct trailer_item), 1);
 	duplicate_conf(&item->conf, &default_conf_info);
 	item->conf.name = xstrdup(name);
-
-	if (!previous)
-		first_conf_item = item;
-	else {
-		previous->next = item;
-		item->previous = previous;
-	}
-
+	*next = item;
 	return item;
 }
 
@@ -652,26 +552,19 @@ static struct trailer_item *create_trailer_item(const char *string)
 				strbuf_detach(&val, NULL));
 }
 
-static void add_trailer_item(struct trailer_item **first,
-			     struct trailer_item **last,
+static void add_trailer_item(struct trailer_item ***tail,
 			     struct trailer_item *new)
 {
 	if (!new)
 		return;
-	if (!*last) {
-		*first = new;
-		*last = new;
-	} else {
-		(*last)->next = new;
-		new->previous = *last;
-		*last = new;
-	}
+	**tail = new;
+	*tail = &new->next;
 }
 
 static struct trailer_item *process_command_line_args(struct string_list *trailers)
 {
-	struct trailer_item *arg_tok_first = NULL;
-	struct trailer_item *arg_tok_last = NULL;
+	struct trailer_item *arg_tok_head = NULL;
+	struct trailer_item **arg_tok_tail = &arg_tok_head;
 	struct string_list_item *tr;
 	struct trailer_item *item;
 
@@ -679,17 +572,17 @@ static struct trailer_item *process_command_line_args(struct string_list *traile
 	for (item = first_conf_item; item; item = item->next) {
 		if (item->conf.command) {
 			struct trailer_item *new = new_trailer_item(item, NULL, NULL);
-			add_trailer_item(&arg_tok_first, &arg_tok_last, new);
+			add_trailer_item(&arg_tok_tail, new);
 		}
 	}
 
 	/* Add a trailer item for each trailer on the command line */
 	for_each_string_list_item(tr, trailers) {
 		struct trailer_item *new = create_trailer_item(tr->string);
-		add_trailer_item(&arg_tok_first, &arg_tok_last, new);
+		add_trailer_item(&arg_tok_tail, new);
 	}
 
-	return arg_tok_first;
+	return arg_tok_head;
 }
 
 static struct strbuf **read_input_file(const char *file)
@@ -805,8 +698,7 @@ static void print_lines(FILE *outfile, struct strbuf **lines, int start, int end
 
 static int process_input_file(FILE *outfile,
 			      struct strbuf **lines,
-			      struct trailer_item **in_tok_first,
-			      struct trailer_item **in_tok_last)
+			      struct trailer_item ***in_tok_tail)
 {
 	int count = 0;
 	int patch_start, trailer_start, trailer_end, i;
@@ -829,18 +721,19 @@ static int process_input_file(FILE *outfile,
 	for (i = trailer_start; i < trailer_end; i++) {
 		if (lines[i]->buf[0] != comment_line_char) {
 			struct trailer_item *new = create_trailer_item(lines[i]->buf);
-			add_trailer_item(in_tok_first, in_tok_last, new);
+			add_trailer_item(in_tok_tail, new);
 		}
 	}
 
 	return trailer_end;
 }
 
-static void free_all(struct trailer_item **first)
+static void free_all(struct trailer_item *head)
 {
-	while (*first) {
-		struct trailer_item *item = remove_first(first);
-		free_trailer_item(item);
+	while (head) {
+		struct trailer_item *next = head->next;
+		free_trailer_item(head);
+		head = next;
 	}
 }
 
@@ -877,9 +770,9 @@ static FILE *create_in_place_tempfile(const char *file)
 
 void process_trailers(const char *file, int in_place, int trim_empty, struct string_list *trailers)
 {
-	struct trailer_item *in_tok_first = NULL;
-	struct trailer_item *in_tok_last = NULL;
-	struct trailer_item *arg_tok_first;
+	struct trailer_item *in_tok_head = NULL;
+	struct trailer_item **in_tok_tail = &in_tok_head;
+	struct trailer_item *arg_tok_head;
 	struct strbuf **lines;
 	int trailer_end;
 	FILE *outfile = stdout;
@@ -894,15 +787,15 @@ void process_trailers(const char *file, int in_place, int trim_empty, struct str
 		outfile = create_in_place_tempfile(file);
 
 	/* Print the lines before the trailers */
-	trailer_end = process_input_file(outfile, lines, &in_tok_first, &in_tok_last);
+	trailer_end = process_input_file(outfile, lines, &in_tok_tail);
 
-	arg_tok_first = process_command_line_args(trailers);
+	arg_tok_head = process_command_line_args(trailers);
 
-	process_trailers_lists(&in_tok_first, &in_tok_last, &arg_tok_first);
+	process_trailers_lists(&in_tok_head, arg_tok_head);
 
-	print_all(outfile, in_tok_first, trim_empty);
+	print_all(outfile, in_tok_head, trim_empty);
 
-	free_all(&in_tok_first);
+	free_all(in_tok_head);
 
 	/* Print the lines after the trailers as is */
 	print_lines(outfile, lines, trailer_end, INT_MAX);

-- 
2.8.0.rc3.226.g39d4020
Previous: Jonathan TanNext: Junio C Hamano
Message 2 of 48 in “allow non-trailers and multiple-line trailers”
  1. 0/5 allow non-trailers and multiple-line trailersJonathan Tan, Oct 12, 2016
  2. 1/5 trailer: use singly-linked list, not doublyJonathan Tan, Oct 12, 2016
  3. Junio C HamanoOct 12, 2016
  4. Christian CouderOct 12, 2016
  5. Jeff KingOct 12, 2016
  6. 5/5 trailer: support values folded to multiple linesJonathan Tan, Oct 12, 2016
  7. Junio C HamanoOct 12, 2016
  8. 2/5 trailer: streamline trailer item create and addJonathan Tan, Oct 12, 2016
  9. 4/5 trailer: allow non-trailers in trailer blockJonathan Tan, Oct 12, 2016
  10. 3/5 trailer: make args have their own structJonathan Tan, Oct 12, 2016
  11. 0/6 allow non-trailers and multiple-line trailersJonathan Tan, Oct 12, 2016
  12. 1/6 trailer: improve const correctnessJonathan Tan, Oct 12, 2016
  13. 2/6 trailer: use list.h for doubly-linked listJonathan Tan, Oct 12, 2016
  14. Junio C HamanoOct 14, 2016
  15. Jakub NarębskiOct 14, 2016
  16. 3/6 trailer: streamline trailer item create and addJonathan Tan, Oct 12, 2016
  17. 4/6 trailer: make args have their own structJonathan Tan, Oct 12, 2016
  18. 5/6 trailer: allow non-trailers in trailer blockJonathan Tan, Oct 12, 2016
  19. 6/6 trailer: support values folded to multiple linesJonathan Tan, Oct 12, 2016
  20. 0/6 allow non-trailers and multiple-line trailersJonathan Tan, Oct 14, 2016
  21. 1/6 trailer: improve const correctnessJonathan Tan, Oct 14, 2016
  22. Stefan BellerOct 17, 2016
  23. 2/6 trailer: use list.h for doubly-linked listJonathan Tan, Oct 14, 2016
  24. 3/6 trailer: streamline trailer item create and addJonathan Tan, Oct 14, 2016
  25. Stefan BellerOct 17, 2016
  26. 5/6 trailer: allow non-trailers in trailer blockJonathan Tan, Oct 14, 2016
  27. Stefan BellerOct 18, 2016
  28. Junio C HamanoOct 18, 2016
  29. Jonathan TanOct 18, 2016
  30. Junio C HamanoOct 18, 2016
  31. Jonathan TanOct 19, 2016
  32. Junio C HamanoOct 19, 2016
  33. 6/6 trailer: support values folded to multiple linesJonathan Tan, Oct 14, 2016
  34. Stefan BellerOct 18, 2016
  35. 4/6 trailer: make args have their own structJonathan Tan, Oct 14, 2016
  36. Stefan BellerOct 17, 2016
  37. Junio C HamanoOct 18, 2016
  38. 0/8 allow non-trailers and multiple-line trailersJonathan Tan, Oct 21, 2016
  39. 1/8 trailer: improve const correctnessJonathan Tan, Oct 21, 2016
  40. 5/8 trailer: clarify failure modes in parse_trailerJonathan Tan, Oct 21, 2016
  41. 4/8 trailer: make args have their own structJonathan Tan, Oct 21, 2016
  42. 7/8 trailer: forbid leading whitespace in trailersJonathan Tan, Oct 21, 2016
  43. 6/8 trailer: allow non-trailers in trailer blockJonathan Tan, Oct 21, 2016
  44. 8/8 trailer: support values folded to multiple linesJonathan Tan, Oct 21, 2016
  45. 3/8 trailer: streamline trailer item create and addJonathan Tan, Oct 21, 2016
  46. 2/8 trailer: use list.h for doubly-linked listJonathan Tan, Oct 21, 2016
  47. Junio C HamanoOct 21, 2016
  48. Stefan BellerOct 22, 2016

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.