{"thread":{"id":"33430","subject":"[PATCH 2/2] decorate: add \"clear_decoration()\"","startedAt":"2013-04-08T06:14:17Z","lastAt":"2013-04-09T20:06:21Z","messageCount":15,"participants":["Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"213496","messageId":"7v1ual35xi.fsf@alter.siamese.dyndns.org","threadId":"33430","inReplyTo":null,"subject":"[PATCH 2/2] decorate: add \"clear_decoration()\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-08T06:14:17Z","receivedAt":"2013-04-08T06:14:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"So far, all the users of the decoration API used decoration that\nonly grows and discarded at the end of the program execution.\n\nIntroduce for_each_decoration() that lets the caller iterate over\nall defined decorations and use it to implement clear_decoration()\nfunction.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n Documentation/technical/api-decorate.txt | 22 ++++++++++++++++++++++\n decorate.c                               | 19 +++++++++++++++++++\n decorate.h                               |  4 ++++\n 3 files changed, 45 insertions(+)\n\ndiff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt\nindex 0cc2b64..600366d 100644\n--- a/Documentation/technical/api-decorate.txt\n+++ b/Documentation/technical/api-decorate.txt\n@@ -35,3 +35,25 @@ the `obj`.  You cannot tell if `obj` does not appear in the hashtable\n at all, or if `obj` has decoration whose value is NULL, so if you want\n to use the decoration API for \"Did I see this object?\" hashtable,\n use decoration value that is _not_ NULL.\n+\n+Iterating\n+---------\n+\n+`for_each_decoration(struct decoration *deco, for_each_decoration_fn fn)`\n+iterates over all the entries in the hashtable, and calls `fn` on each\n+entry.  The `fn` callback function takes a single `struct object_decoration`\n+as its parameter, that has `base` field that points at the `obj`\n+given to an earlier call to `add_decoration` and `decoration` field\n+that remembers the `decoration`.\n+\n+Clearing\n+--------\n+\n+`clear_decoration(struct decoration *deco, for_each_decoration_fn fn)`,\n+when `fn` is not NULL, iterates over all the entries and calls the\n+callback function `fn` using `for_each_decoration`, and then frees\n+the memory used for the hashtable but not the `struct decoration` itself.\n+\n+The callback function can be used to release the resource used by\n+the `decoration` the earlier `add_decoration` registered to the\n+hashtable.\ndiff --git a/decorate.c b/decorate.c\nindex 2f8a63e..3e15358 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -86,3 +86,22 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)\n \t\t\tj = 0;\n \t}\n }\n+\n+void for_each_decoration(struct decoration *n, for_each_decoration_fn fn)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < n->size; i++) {\n+\t\tstruct object_decoration *entry = &n->hash[i];\n+\t\tif (!entry->base)\n+\t\t\tcontinue;\n+\t\tfn(entry);\n+\t}\n+}\n+\n+void clear_decoration(struct decoration *n, for_each_decoration_fn fn)\n+{\n+\tif (fn)\n+\t\tfor_each_decoration(n, fn);\n+\tfree(n->hash);\n+}\ndiff --git a/decorate.h b/decorate.h\nindex e732804..4a0d37e 100644\n--- a/decorate.h\n+++ b/decorate.h\n@@ -15,4 +15,8 @@ struct decoration {\n extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);\n extern void *lookup_decoration(struct decoration *n, const struct object *obj);\n \n+typedef void (*for_each_decoration_fn)(struct object_decoration *);\n+extern void for_each_decoration(struct decoration *, for_each_decoration_fn);\n+extern void clear_decoration(struct decoration *, for_each_decoration_fn);\n+\n #endif\n-- \n1.8.2.1-450-gd047976\n"},{"id":"213608","messageId":"20130408210903.GC9649@sigill.intra.peff.net","threadId":"33430","inReplyTo":"7v1ual35xi.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] decorate: add \"clear_decoration()\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-04-08T21:09:03Z","receivedAt":"2013-04-08T21:09:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 07, 2013 at 11:14:17PM -0700, Junio C Hamano wrote:\n\n> So far, all the users of the decoration API used decoration that\n> only grows and discarded at the end of the program execution.\n> \n> Introduce for_each_decoration() that lets the caller iterate over\n> all defined decorations and use it to implement clear_decoration()\n> function.\n> \n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n\nBoth this and the first patch look good to me. I had documented\napi-decorate long ago as part of the cache-metadata-on-disk series (it\nwas built on generic maps, which I also refactored decorate on top of).\nBut I didn't see anything in my version that was missing from yours (in\nfact, it was much sparser, because it just referred to the generic map\napi, which we never merged).\n\nOut of curiosity: where is the patch 3 that presumably led you to\nwanting these?\n\n-Peff\n"},{"id":"213611","messageId":"7vppy4vhsp.fsf@alter.siamese.dyndns.org","threadId":"33430","inReplyTo":"20130408210903.GC9649@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] decorate: add \"clear_decoration()\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-08T21:22:46Z","receivedAt":"2013-04-08T21:22:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Sun, Apr 07, 2013 at 11:14:17PM -0700, Junio C Hamano wrote:\n>\n>> So far, all the users of the decoration API used decoration that\n>> only grows and discarded at the end of the program execution.\n>> \n>> Introduce for_each_decoration() that lets the caller iterate over\n>> all defined decorations and use it to implement clear_decoration()\n>> function.\n>> \n>> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n>\n> Both this and the first patch look good to me. I had documented\n> api-decorate long ago as part of the cache-metadata-on-disk series (it\n> was built on generic maps, which I also refactored decorate on top of).\n> But I didn't see anything in my version that was missing from yours (in\n> fact, it was much sparser, because it just referred to the generic map\n> api, which we never merged).\n>\n> Out of curiosity: where is the patch 3 that presumably led you to\n> wanting these?\n\nIt is nowhere near ready to be published, as I am not finding any\ntime for coding today X-<.\n"},{"id":"213630","messageId":"1365462114-8630-1-git-send-email-gitster@pobox.com","threadId":"33430","inReplyTo":"20130408210903.GC9649@sigill.intra.peff.net","subject":"[PATCH 0/3] Using a bit more decoration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-08T23:01:51Z","receivedAt":"2013-04-08T23:01:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This comes on top of the two \"decorate\" patches that introduced the\nclear_decoration() function.\n\nI am not sure if pre-parsing and sharing the encoding values in-core\nwould affect performance very much, but now we have 2 bytes (or 6\nbytes, if you are on 64-bit archs) free to use in \"struct commit\"\nfor later use (e.g. extra object flags that are relevant only for\ncommit objects, without having to widen \"struct object\").\n\nJunio C Hamano (3):\n  commit: shrink \"indegree\" field\n  commit: rename parse_commit_date()\n  commit: add get_commit_encoding()\n\n commit.c    | 138 ++++++++++++++++++++++++++++++++++++++++++++++++++----------\n commit.h    |   5 ++-\n pretty.c    |  33 +--------------\n sequencer.c |  23 +---------\n 4 files changed, 122 insertions(+), 77 deletions(-)\n\n-- \n1.8.2.1-450-gd047976\n"},{"id":"213629","messageId":"1365462114-8630-2-git-send-email-gitster@pobox.com","threadId":"33430","inReplyTo":"1365462114-8630-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/3] commit: shrink \"indegree\" field","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-08T23:01:52Z","receivedAt":"2013-04-08T23:01:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The \"indegree\" field in the commit object is used only while a\ncommit list is sorted using the topo_order sorting.  The idea is to\ninitially store the number of direct parents and the commit itself\nthere, and start emitting the commits with indegree 1 (i.e. leaves\nthat do not have any commit as the parent), and every time a commit\nis emitted, decrement its own count (to drop it to 0 to clear the\nfield) and the count in its parents (so eventually a commit whose\nchildren are all emitted will see its count dropped to 1, becoming\neligible to be emitted) by one.\n\nWe used to allocate a full integer for this, but in real life, a\ncommit with thousands of direct children are rare. Shrink it to an\nunsigned char to represent a commit with 254 children or less\nwithout any extra overhead, and spilling the overflow to a separate\ndecoration hash.\n\nThis does not save any bytes from the commit object structure due to\nalignment, but would give us 3 or 7 bytes to store other information.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n commit.c | 46 +++++++++++++++++++++++++++++++++++++++-------\n commit.h |  2 +-\n 2 files changed, 40 insertions(+), 8 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 516a4ff..9d7e81b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -506,6 +506,30 @@ struct commit *pop_commit(struct commit_list **stack)\n \treturn item;\n }\n \n+#define QUICK_INDEGREE_LIMIT 255\n+\n+static inline void set_indegree(struct decoration *indegree,\n+\t\t\t\tstruct commit *commit, intptr_t value)\n+{\n+\tif (QUICK_INDEGREE_LIMIT <= value) {\n+\t\tcommit->indegree = QUICK_INDEGREE_LIMIT;\n+\t\tadd_decoration(indegree, &commit->object, (void *)value);\n+\t} else {\n+\t\tcommit->indegree = value;\n+\t}\n+}\n+\n+static inline intptr_t get_indegree(struct decoration *indegree,\n+\t\t\t\t    struct commit *commit)\n+{\n+\tif (commit->indegree < QUICK_INDEGREE_LIMIT)\n+\t\treturn commit->indegree;\n+\telse {\n+\t\tvoid *count = lookup_decoration(indegree, &commit->object);\n+\t\treturn (int) count;\n+\t}\n+}\n+\n /*\n  * Performs an in-place topological sort on the list supplied.\n  */\n@@ -514,15 +538,18 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n \tstruct commit_list **pptr;\n+\tstruct decoration id_overflow;\n+\tintptr_t count;\n \n \tif (!orig)\n \t\treturn;\n \t*list = NULL;\n \n \t/* Mark them and clear the indegree */\n+\tmemset(&id_overflow, 0, sizeof(id_overflow));\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n-\t\tcommit->indegree = 1;\n+\t\tset_indegree(&id_overflow, commit, 1);\n \t}\n \n \t/* update the indegree */\n@@ -531,8 +558,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\twhile (parents) {\n \t\t\tstruct commit *parent = parents->item;\n \n-\t\t\tif (parent->indegree)\n-\t\t\t\tparent->indegree++;\n+\t\t\tcount = get_indegree(&id_overflow, parent);\n+\t\t\tif (count)\n+\t\t\t\tset_indegree(&id_overflow, parent, count + 1);\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n@@ -549,7 +577,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \n-\t\tif (commit->indegree == 1)\n+\t\tif (get_indegree(&id_overflow, commit) == 1)\n \t\t\tinsert = &commit_list_insert(commit, insert)->next;\n \t}\n \n@@ -571,7 +599,8 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\tfor (parents = commit->parents; parents ; parents = parents->next) {\n \t\t\tstruct commit *parent = parents->item;\n \n-\t\t\tif (!parent->indegree)\n+\t\t\tcount = get_indegree(&id_overflow, parent);\n+\t\t\tif (!count)\n \t\t\t\tcontinue;\n \n \t\t\t/*\n@@ -579,7 +608,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t\t * when all their children have been emitted thereby\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n-\t\t\tif (--parent->indegree == 1) {\n+\t\t\tcount--;\n+\t\t\tset_indegree(&id_overflow, parent, count);\n+\t\t\tif (count == 1) {\n \t\t\t\tif (!lifo)\n \t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n \t\t\t\telse\n@@ -590,10 +621,11 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t * work_item is a commit all of whose children\n \t\t * have already been emitted. we can emit it now.\n \t\t */\n-\t\tcommit->indegree = 0;\n+\t\tset_indegree(&id_overflow, commit, 0);\n \t\t*pptr = work_item;\n \t\tpptr = &work_item->next;\n \t}\n+\tclear_decoration(&id_overflow, NULL);\n }\n \n /* merge-base stuff */\ndiff --git a/commit.h b/commit.h\nindex 87b4b6c..771eeae 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -15,7 +15,7 @@ struct commit_list {\n struct commit {\n \tstruct object object;\n \tvoid *util;\n-\tunsigned int indegree;\n+\tunsigned int indegree:8; /* see QUICK_INDEGREE_LIMIT in commit.c */\n \tunsigned long date;\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n-- \n1.8.2.1-450-gd047976\n"},{"id":"213632","messageId":"1365462114-8630-3-git-send-email-gitster@pobox.com","threadId":"33430","inReplyTo":"1365462114-8630-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/3] commit: rename parse_commit_date()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-08T23:01:53Z","receivedAt":"2013-04-08T23:01:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This function does a lot more than parsing the committer date out of\na commit object buffer.  After its sole caller parses one \"tree\",\nand 0 or more \"parent\", it makes sure the next one is \"author\" (and\nskips it), makes sure \"committer\" follows (and skips the committer\nidentity), and parses the date field.  Each of these fields must be\non its own line (no header folding is allowed).\n\nRename it to parse_commit_standard_header(), and change the function\nsignature to accept \"struct commit *\" to be updated as a parameter.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n commit.c | 32 +++++++++++++++++++-------------\n 1 file changed, 19 insertions(+), 13 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 9d7e81b..50a9827 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -78,31 +78,33 @@ struct commit *lookup_commit_reference_by_name(const char *name)\n \treturn commit;\n }\n \n-static unsigned long parse_commit_date(const char *buf, const char *tail)\n+static void parse_commit_standard_headers(const char *buf, const char *tail,\n+\t\t\t\t\t  struct commit *item)\n {\n \tconst char *dateptr;\n \n+\titem->date = 0;\n \tif (buf + 6 >= tail)\n-\t\treturn 0;\n+\t\treturn;\n \tif (memcmp(buf, \"author\", 6))\n-\t\treturn 0;\n+\t\treturn;\n \twhile (buf < tail && *buf++ != '\\n')\n-\t\t/* nada */;\n+\t\t; /* skip to the end of the line */\n \tif (buf + 9 >= tail)\n-\t\treturn 0;\n+\t\treturn;\n \tif (memcmp(buf, \"committer\", 9))\n-\t\treturn 0;\n+\t\treturn;\n \twhile (buf < tail && *buf++ != '>')\n-\t\t/* nada */;\n+\t\t; /* skip to the end of the e-mail */\n \tif (buf >= tail)\n-\t\treturn 0;\n+\t\treturn;\n \tdateptr = buf;\n \twhile (buf < tail && *buf++ != '\\n')\n-\t\t/* nada */;\n+\t\t; /* skip to the end of the line */\n \tif (buf >= tail)\n-\t\treturn 0;\n+\t\treturn;\n \t/* dateptr < buf && buf[-1] == '\\n', so strtoul will stop at buf-1 */\n-\treturn strtoul(dateptr, NULL, 10);\n+\titem->date = strtoul(dateptr, NULL, 10);\n }\n \n static struct commit_graft **commit_graft;\n@@ -262,6 +264,11 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \tif (item->object.parsed)\n \t\treturn 0;\n \titem->object.parsed = 1;\n+\n+\t/*\n+\t * tree, 0-or-more parents, author and committer are required\n+\t * and must appear in this order; no line folding is allowed.\n+\t */\n \ttail += size;\n \tif (tail <= bufptr + 46 || memcmp(bufptr, \"tree \", 5) || bufptr[45] != '\\n')\n \t\treturn error(\"bogus commit object %s\", sha1_to_hex(item->object.sha1));\n@@ -301,8 +308,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n \t\t}\n \t}\n-\titem->date = parse_commit_date(bufptr, tail);\n-\n+\tparse_commit_standard_headers(bufptr, tail, item);\n \treturn 0;\n }\n \n-- \n1.8.2.1-450-gd047976\n"},{"id":"213631","messageId":"1365462114-8630-4-git-send-email-gitster@pobox.com","threadId":"33430","inReplyTo":"1365462114-8630-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/3] commit: add get_commit_encoding()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-08T23:01:54Z","receivedAt":"2013-04-08T23:01:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This replaces two duplicated and slightly different helper functions\nin pretty.c and sequencer.c that parses the commit object to find\nthe encoding header, by having the header parsed when other standard\ncommit header fields are parsed.  A commit object now has a small\ninteger that is used to index into a static table that holds the\nfirst 200+ values for encoding headers, and in a weird project that\nuses more than that many encoding, the encoding values are parsed\ninto a separate decoration hash (that is not expected to be used in\nreal life).\n\nIncidentally, this fixes a small leak in sequencer(); the memory\nallocated in its get_encoding() helper was never freed in the\ncaller.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n commit.c    | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----\n commit.h    |  3 +++\n pretty.c    | 33 ++------------------------------\n sequencer.c | 23 +----------------------\n 4 files changed, 64 insertions(+), 57 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 50a9827..89c8d7c 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -78,10 +78,53 @@ struct commit *lookup_commit_reference_by_name(const char *name)\n \treturn commit;\n }\n \n+#define QUICK_ENCODING_LIMIT 254 /* offset 1, as 0 is for \"no encoding\" */\n+\n+static int quick_encoding_used;\n+static struct {\n+\tconst char *encoding;\n+\tsize_t sz;\n+} quick_encoding[QUICK_ENCODING_LIMIT];\n+static struct decoration slow_encoding;\n+\n+static void set_commit_encoding(struct commit *item, const char *encoding, size_t sz)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < quick_encoding_used; i++) {\n+\t\tif (sz == quick_encoding[i].sz &&\n+\t\t    !memcmp(encoding, quick_encoding[i].encoding, sz)) {\n+\t\t\titem->encoding = i + 1;\n+\t\t\treturn;\n+\t\t}\n+\t}\n+\tif (i < QUICK_ENCODING_LIMIT) {\n+\t\tquick_encoding[i].sz = sz;\n+\t\tquick_encoding[i].encoding = xmemdupz(encoding, sz);\n+\t\titem->encoding = i + 1;\n+\t\tquick_encoding_used++;\n+\t\treturn;\n+\t}\n+\titem->encoding = QUICK_ENCODING_LIMIT;\n+\tadd_decoration(&slow_encoding, &item->object, xmemdupz(encoding, sz));\n+}\n+\n+const char *get_commit_encoding(const struct commit *item)\n+{\n+\tint i;\n+\n+\tif (!item->encoding)\n+\t\treturn NULL;\n+\ti = item->encoding - 1; /* offset 1 */\n+\tif (i < QUICK_ENCODING_LIMIT)\n+\t\treturn quick_encoding[i].encoding;\n+\treturn lookup_decoration(&slow_encoding, &item->object);\n+}\n+\n static void parse_commit_standard_headers(const char *buf, const char *tail,\n \t\t\t\t\t  struct commit *item)\n {\n-\tconst char *dateptr;\n+\tconst char *ptr;\n \n \titem->date = 0;\n \tif (buf + 6 >= tail)\n@@ -98,13 +141,24 @@ static void parse_commit_standard_headers(const char *buf, const char *tail,\n \t\t; /* skip to the end of the e-mail */\n \tif (buf >= tail)\n \t\treturn;\n-\tdateptr = buf;\n+\tptr = buf;\n+\twhile (buf < tail && *buf++ != '\\n')\n+\t\t; /* skip to the end of the line */\n+\tif (buf >= tail)\n+\t\treturn;\n+\t/* ptr < buf && buf[-1] == '\\n', so strtoul will stop at buf-1 */\n+\titem->date = strtoul(ptr, NULL, 10);\n+\n+\titem->encoding = 0; /* no encoding header */\n+\tif (memcmp(buf, \"encoding \", 9))\n+\t\treturn;\n+\tptr = buf + 9;\n \twhile (buf < tail && *buf++ != '\\n')\n \t\t; /* skip to the end of the line */\n \tif (buf >= tail)\n \t\treturn;\n-\t/* dateptr < buf && buf[-1] == '\\n', so strtoul will stop at buf-1 */\n-\titem->date = strtoul(dateptr, NULL, 10);\n+\t/* buf[-1] == '\\n' that is the end of encoding */\n+\tset_commit_encoding(item, ptr, buf - ptr);\n }\n \n static struct commit_graft **commit_graft;\ndiff --git a/commit.h b/commit.h\nindex 771eeae..e7a70d3 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -16,12 +16,15 @@ struct commit {\n \tstruct object object;\n \tvoid *util;\n \tunsigned int indegree:8; /* see QUICK_INDEGREE_LIMIT in commit.c */\n+\tunsigned int encoding:8; /* see QUICK_ENCODING_LIMIT in commit.c */\n \tunsigned long date;\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n \tchar *buffer;\n };\n \n+extern const char *get_commit_encoding(const struct commit *);\n+\n extern int save_commit_buffer;\n extern const char *commit_type;\n \ndiff --git a/pretty.c b/pretty.c\nindex d3a82d2..08c6ffc 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -534,34 +534,6 @@ static void add_merge_info(const struct pretty_print_context *pp,\n \tstrbuf_addch(sb, '\\n');\n }\n \n-static char *get_header(const struct commit *commit, const char *msg,\n-\t\t\tconst char *key)\n-{\n-\tint key_len = strlen(key);\n-\tconst char *line = msg;\n-\n-\twhile (line) {\n-\t\tconst char *eol = strchr(line, '\\n'), *next;\n-\n-\t\tif (line == eol)\n-\t\t\treturn NULL;\n-\t\tif (!eol) {\n-\t\t\twarning(\"malformed commit (header is missing newline): %s\",\n-\t\t\t\tsha1_to_hex(commit->object.sha1));\n-\t\t\teol = line + strlen(line);\n-\t\t\tnext = NULL;\n-\t\t} else\n-\t\t\tnext = eol + 1;\n-\t\tif (eol - line > key_len &&\n-\t\t    !strncmp(line, key, key_len) &&\n-\t\t    line[key_len] == ' ') {\n-\t\t\treturn xmemdupz(line + key_len + 1, eol - line - key_len - 1);\n-\t\t}\n-\t\tline = next;\n-\t}\n-\treturn NULL;\n-}\n-\n static char *replace_encoding_header(char *buf, const char *encoding)\n {\n \tstruct strbuf tmp = STRBUF_INIT;\n@@ -598,7 +570,7 @@ char *logmsg_reencode(const struct commit *commit,\n {\n \tstatic const char *utf8 = \"UTF-8\";\n \tconst char *use_encoding;\n-\tchar *encoding;\n+\tconst char *encoding;\n \tchar *msg = commit->buffer;\n \tchar *out;\n \n@@ -617,7 +589,7 @@ char *logmsg_reencode(const struct commit *commit,\n \n \tif (!output_encoding || !*output_encoding)\n \t\treturn msg;\n-\tencoding = get_header(commit, msg, \"encoding\");\n+\tencoding = get_commit_encoding(commit);\n \tuse_encoding = encoding ? encoding : utf8;\n \tif (same_encoding(use_encoding, output_encoding)) {\n \t\t/*\n@@ -658,7 +630,6 @@ char *logmsg_reencode(const struct commit *commit,\n \tif (out)\n \t\tout = replace_encoding_header(out, output_encoding);\n \n-\tfree(encoding);\n \t/*\n \t * If the re-encoding failed, out might be NULL here; in that\n \t * case we just return the commit message verbatim.\ndiff --git a/sequencer.c b/sequencer.c\nindex baa0310..5d97519 100644\n--- a/sequencer.c\n+++ b/sequencer.c\n@@ -116,8 +116,6 @@ static const char *action_name(const struct replay_opts *opts)\n \treturn opts->action == REPLAY_REVERT ? \"revert\" : \"cherry-pick\";\n }\n \n-static char *get_encoding(const char *message);\n-\n struct commit_message {\n \tchar *parent_label;\n \tconst char *label;\n@@ -135,7 +133,7 @@ static int get_message(struct commit *commit, struct commit_message *out)\n \n \tif (!commit->buffer)\n \t\treturn -1;\n-\tencoding = get_encoding(commit->buffer);\n+\tencoding = get_commit_encoding(commit);\n \tif (!encoding)\n \t\tencoding = \"UTF-8\";\n \tif (!git_commit_encoding)\n@@ -173,25 +171,6 @@ static void free_message(struct commit_message *msg)\n \tfree(msg->reencoded_message);\n }\n \n-static char *get_encoding(const char *message)\n-{\n-\tconst char *p = message, *eol;\n-\n-\twhile (*p && *p != '\\n') {\n-\t\tfor (eol = p + 1; *eol && *eol != '\\n'; eol++)\n-\t\t\t; /* do nothing */\n-\t\tif (!prefixcmp(p, \"encoding \")) {\n-\t\t\tchar *result = xmalloc(eol - 8 - p);\n-\t\t\tstrlcpy(result, p + 9, eol - 8 - p);\n-\t\t\treturn result;\n-\t\t}\n-\t\tp = eol;\n-\t\tif (*p == '\\n')\n-\t\t\tp++;\n-\t}\n-\treturn NULL;\n-}\n-\n static void write_cherry_pick_head(struct commit *commit, const char *pseudoref)\n {\n \tconst char *filename;\n-- \n1.8.2.1-450-gd047976\n"},{"id":"213635","messageId":"20130409035126.GA17319@sigill.intra.peff.net","threadId":"33430","inReplyTo":"1365462114-8630-1-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 0/3] Using a bit more decoration","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-04-09T03:51:26Z","receivedAt":"2013-04-09T03:51:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 08, 2013 at 04:01:51PM -0700, Junio C Hamano wrote:\n\n> This comes on top of the two \"decorate\" patches that introduced the\n> clear_decoration() function.\n> [...]\n> Junio C Hamano (3):\n>   commit: shrink \"indegree\" field\n>   commit: rename parse_commit_date()\n>   commit: add get_commit_encoding()\n\nNeat. Reading through, I didn't notice anything obviously wrong with any\nof the patches (though there is one gcc warning, which I'll respond to\nseparately).\n\nIt does make me a little nervous to have code that almost never gets\nexercised (i.e., when indegree is really high, or a large number of\nencodings). It seems like a bug waiting to happen when somebody does hit\nthat condition. But the decoration lookups do look fairly simple and\neasy to get right.\n\n> I am not sure if pre-parsing and sharing the encoding values in-core\n> would affect performance very much, but now we have 2 bytes (or 6\n> bytes, if you are on 64-bit archs) free to use in \"struct commit\"\n> for later use (e.g. extra object flags that are relevant only for\n> commit objects, without having to widen \"struct object\").\n\nI wasn't able to measure any speedup, but I'm not surprised; something\nlike \"git log\" already spends way more effort extracting and\npretty-printing the commit objects.\n\nI was actually thinking of something related to this recently. It would\nbe nice to be able to allocate a slab of very efficient fixed-size\nper-commit or per-object storage. That would eliminate the need to pay\nthe cost for \"indegree\" all the time; the topo-sort could allocate a\nslab of indegree integers, then throw it away when the sort was done.\nSimilarly, a traversal would not have to worry about pollution of the\nobject flags, nor about using an arbitrarily large number of flags[1],\nif it could allocate a separate flag structure.\n\nUsing a separate hash would be too slow. I'm thinking more like giving\neach commit an integer \"id\" as it is parsed, and then using that id to\nindex into a temporary slab (you'd grow the slab as you see more commits\nbut that's OK, since we're always indexing it, not using a pointer). The\nslab management would get amortized, so the main cost would be the extra\nindirect memory access (i.e., hitting \"flags[commit->id]\" instead of\n\"commit->id\"), and the extra memory used by the id field.\n\nI dunno. Maybe those costs would make it too slow. I haven't actually\ncoded or measured anything yet.\n\n-Peff\n\n[1] The thing that made me think about this was making a version of\n    paint_down_to_common that could keep a separate color for each\n    source, rather than only PARENT1 and PARENT2. That would let us do\n    the \"--contains\" traversal in a breadth-first way, but calculate the\n    answer simultaneously for all sources (i.e., avoid the depth-first\n    \"go to roots\" problem that the current \"tag --contains\" has if you\n    do not use timestamp cutoffs).\n"},{"id":"213636","messageId":"20130409035250.GB17319@sigill.intra.peff.net","threadId":"33430","inReplyTo":"1365462114-8630-2-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 1/3] commit: shrink \"indegree\" field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-04-09T03:52:50Z","receivedAt":"2013-04-09T03:52:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 08, 2013 at 04:01:52PM -0700, Junio C Hamano wrote:\n\n> +static inline intptr_t get_indegree(struct decoration *indegree,\n> +\t\t\t\t    struct commit *commit)\n> +{\n> +\tif (commit->indegree < QUICK_INDEGREE_LIMIT)\n> +\t\treturn commit->indegree;\n> +\telse {\n> +\t\tvoid *count = lookup_decoration(indegree, &commit->object);\n> +\t\treturn (int) count;\n> +\t}\n> +}\n\nShould that cast be to intptr_t?\n\n-Peff\n"},{"id":"213637","messageId":"7vsj30tk0p.fsf@alter.siamese.dyndns.org","threadId":"33430","inReplyTo":"20130409035126.GA17319@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] Using a bit more decoration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-09T04:17:42Z","receivedAt":"2013-04-09T04:17:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> [1] The thing that made me think about this was making a version of\n>     paint_down_to_common that could keep a separate color for each\n>     source, rather than only PARENT1 and PARENT2. That would let us do\n>     the \"--contains\" traversal in a breadth-first way, but calculate the\n>     answer simultaneously for all sources (i.e., avoid the depth-first\n>     \"go to roots\" problem that the current \"tag --contains\" has if you\n>     do not use timestamp cutoffs).\n\nYes, show-branch operates independently of rev-list machinery, hence\ncan use full set of bits, but the full set of bits in a word is not\nalways sufficient and it can be helped greatly with such an unbound\nset of bits machinery.\n"},{"id":"213638","messageId":"7vobdotj41.fsf@alter.siamese.dyndns.org","threadId":"33430","inReplyTo":"20130409035126.GA17319@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] Using a bit more decoration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-09T04:37:18Z","receivedAt":"2013-04-09T04:37:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Neat. Reading through, I didn't notice anything obviously wrong with any\n> of the patches (though there is one gcc warning, which I'll respond to\n> separately).\n>\n> It does make me a little nervous to have code that almost never gets\n> exercised (i.e., when indegree is really high, or a large number of\n> encodings). It seems like a bug waiting to happen when somebody does hit\n> that condition.\n\nOne round of work-in-progress code I had when you asked what I was\nup to did have that off-by-one bug ;-)  set_indegree() had to spill\ninto the hash when storing 255 (i.e. exactly the value of LIMIT) but\nI was spilling strting from 256, so an entry with 255 children looked\ninto the hash, finding nothing and said \"I am done\" X-<.\n\nI haven't bothered to try the \"more than 256 encodings\", but with\nthe likely off-by-one in mind, I think I was being careful enough.\n"},{"id":"213639","messageId":"20130409043938.GA31447@sigill.intra.peff.net","threadId":"33430","inReplyTo":"7vsj30tk0p.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 0/3] Using a bit more decoration","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-04-09T04:39:39Z","receivedAt":"2013-04-09T04:39:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 08, 2013 at 09:17:42PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > [1] The thing that made me think about this was making a version of\n> >     paint_down_to_common that could keep a separate color for each\n> >     source, rather than only PARENT1 and PARENT2. That would let us do\n> >     the \"--contains\" traversal in a breadth-first way, but calculate the\n> >     answer simultaneously for all sources (i.e., avoid the depth-first\n> >     \"go to roots\" problem that the current \"tag --contains\" has if you\n> >     do not use timestamp cutoffs).\n> \n> Yes, show-branch operates independently of rev-list machinery, hence\n> can use full set of bits, but the full set of bits in a word is not\n> always sufficient and it can be helped greatly with such an unbound\n> set of bits machinery.\n\nThe tricky part is how to store the index for each commit (or object). I\ndon't see a way around adding a new field to \"struct commit\" to do so.\nIt _might_ be worth it, because that index would be reusable for many\ndifferent operations.\n\nI had hoped to do something clever and implicit with the commit pointer,\nsince we allocate from a pool. For example, if you have pointer X and\nknow that the pool starts at Y, you can get an index with simple\nsubtraction. But of course we don't know what the pool is for any given\nallocator without searching the pools, which grow linearly with the\nnumber of objects. So it ends up with the same algorithmic complexity as\njust searching for the commit in a data structure (albeit with a smaller\nconstant, since we allocate big chunks of objects).\n\n-Peff\n"},{"id":"213640","messageId":"7vk3octiat.fsf@alter.siamese.dyndns.org","threadId":"33430","inReplyTo":"20130409043938.GA31447@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] Using a bit more decoration","fromName":"Junio C Hamano","fromEmail":"junio@pobox.com","sentAt":"2013-04-09T04:54:50Z","receivedAt":"2013-04-09T04:54:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The tricky part is how to store the index for each commit (or object). I\n> don't see a way around adding a new field to \"struct commit\" to do so.\n\nWe could reuse the space \"indegree\" used to live at; that is a\none-word space already, and I really do not need \"encoding\".  It was\nno more than \"while we are at it, we could add different things\nhere\" demonstration.\n"},{"id":"213643","messageId":"20130409065256.GA20115@sigill.intra.peff.net","threadId":"33430","inReplyTo":"7vk3octiat.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 0/3] Using a bit more decoration","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-04-09T06:52:56Z","receivedAt":"2013-04-09T06:52:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 08, 2013 at 09:54:50PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > The tricky part is how to store the index for each commit (or object). I\n> > don't see a way around adding a new field to \"struct commit\" to do so.\n> \n> We could reuse the space \"indegree\" used to live at; that is a\n> one-word space already, and I really do not need \"encoding\".  It was\n> no more than \"while we are at it, we could add different things\n> here\" demonstration.\n\nHere is what my proposal would look like, replacing indegree with the\n\"index\" field. In my timings of \"git rev-list --topo-order --all\", I\ncouldn't measure any difference.\n\nNow the next tricky step will actually be writing a paint_down_to_common\nthat uses it. :)  The auto-growing slab implementation below assumes a\nfixed width of one int per commit. I think we'd want something similar\nthat stores a set of N bits per commit, where N is fixed at the start of\nthe algorithm.\n\n---\n commit.c | 59 +++++++++++++++++++++++++++++------\n commit.h |  2 +-\n 2 files changed, 51 insertions(+), 10 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 516a4ff..95f041a 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -14,6 +14,7 @@ const char *commit_type = \"commit\";\n int save_commit_buffer = 1;\n \n const char *commit_type = \"commit\";\n+static int commit_count;\n \n static struct commit *check_commit(struct object *obj,\n \t\t\t\t   const unsigned char *sha1,\n@@ -58,8 +59,11 @@ struct commit *lookup_commit(const unsigned char *sha1)\n struct commit *lookup_commit(const unsigned char *sha1)\n {\n \tstruct object *obj = lookup_object(sha1);\n-\tif (!obj)\n-\t\treturn create_object(sha1, OBJ_COMMIT, alloc_commit_node());\n+\tif (!obj) {\n+\t\tstruct commit *c = alloc_commit_node();\n+\t\tc->index = commit_count++;\n+\t\treturn create_object(sha1, OBJ_COMMIT, c);\n+\t}\n \tif (!obj->type)\n \t\tobj->type = OBJ_COMMIT;\n \treturn check_commit(obj, sha1, 0);\n@@ -506,6 +510,36 @@ struct commit *pop_commit(struct commit_list **stack)\n \treturn item;\n }\n \n+struct commit_slab {\n+\tint *buf;\n+\tint alloc;\n+};\n+\n+static void slab_init(struct commit_slab *s)\n+{\n+\tmemset(s, 0, sizeof(*s));\n+}\n+\n+static void slab_clear(struct commit_slab *s)\n+{\n+\tfree(s->buf);\n+\tslab_init(s);\n+}\n+\n+static inline int *slab_at(struct commit_slab *s, const struct commit *c)\n+{\n+\tif (s->alloc <= c->index) {\n+\t\tint new_alloc = alloc_nr(s->alloc);\n+\t\tif (new_alloc <= c->index)\n+\t\t\tnew_alloc = c->index + 1;\n+\n+\t\ts->buf = xrealloc(s->buf, new_alloc * sizeof(*s->buf));\n+\t\tmemset(s->buf + s->alloc, 0, new_alloc - s->alloc);\n+\t\ts->alloc = new_alloc;\n+\t}\n+\treturn s->buf + c->index;\n+}\n+\n /*\n  * Performs an in-place topological sort on the list supplied.\n  */\n@@ -514,15 +548,18 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n \tstruct commit_list **pptr;\n+\tstruct commit_slab indegree;\n \n \tif (!orig)\n \t\treturn;\n \t*list = NULL;\n \n+\tslab_init(&indegree);\n+\n \t/* Mark them and clear the indegree */\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n-\t\tcommit->indegree = 1;\n+\t\t*slab_at(&indegree, commit) = 1;\n \t}\n \n \t/* update the indegree */\n@@ -530,9 +567,10 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\tstruct commit_list * parents = next->item->parents;\n \t\twhile (parents) {\n \t\t\tstruct commit *parent = parents->item;\n+\t\t\tint *pi = slab_at(&indegree, parent);\n \n-\t\t\tif (parent->indegree)\n-\t\t\t\tparent->indegree++;\n+\t\t\tif (*pi)\n+\t\t\t\t(*pi)++;\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n@@ -549,7 +587,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \n-\t\tif (commit->indegree == 1)\n+\t\tif (*slab_at(&indegree, commit) == 1)\n \t\t\tinsert = &commit_list_insert(commit, insert)->next;\n \t}\n \n@@ -570,8 +608,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\tcommit = work_item->item;\n \t\tfor (parents = commit->parents; parents ; parents = parents->next) {\n \t\t\tstruct commit *parent = parents->item;\n+\t\t\tint *pi = slab_at(&indegree, parent);\n \n-\t\t\tif (!parent->indegree)\n+\t\t\tif (!*pi)\n \t\t\t\tcontinue;\n \n \t\t\t/*\n@@ -579,7 +618,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t\t * when all their children have been emitted thereby\n \t\t\t * guaranteeing topological order.\n \t\t\t */\n-\t\t\tif (--parent->indegree == 1) {\n+\t\t\tif (--(*pi) == 1) {\n \t\t\t\tif (!lifo)\n \t\t\t\t\tcommit_list_insert_by_date(parent, &work);\n \t\t\t\telse\n@@ -590,10 +629,12 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\t * work_item is a commit all of whose children\n \t\t * have already been emitted. we can emit it now.\n \t\t */\n-\t\tcommit->indegree = 0;\n+\t\t*slab_at(&indegree, commit) = 0;\n \t\t*pptr = work_item;\n \t\tpptr = &work_item->next;\n \t}\n+\n+\tslab_clear(&indegree);\n }\n \n /* merge-base stuff */\ndiff --git a/commit.h b/commit.h\nindex 87b4b6c..8b1099f 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -15,7 +15,7 @@ struct commit {\n struct commit {\n \tstruct object object;\n \tvoid *util;\n-\tunsigned int indegree;\n+\tunsigned int index;\n \tunsigned long date;\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n"},{"id":"213711","messageId":"7v8v4rqxj6.fsf@alter.siamese.dyndns.org","threadId":"33430","inReplyTo":"20130409065256.GA20115@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] Using a bit more decoration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-09T20:06:21Z","receivedAt":"2013-04-09T20:06:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> +static inline int *slab_at(struct commit_slab *s, const struct commit *c)\n> +{\n> +\tif (s->alloc <= c->index) {\n> +\t\tint new_alloc = alloc_nr(s->alloc);\n> +\t\tif (new_alloc <= c->index)\n> +\t\t\tnew_alloc = c->index + 1;\n> +\n> +\t\ts->buf = xrealloc(s->buf, new_alloc * sizeof(*s->buf));\n> +\t\tmemset(s->buf + s->alloc, 0, new_alloc - s->alloc);\n> +\t\ts->alloc = new_alloc;\n> +\t}\n> +\treturn s->buf + c->index;\n> +}\n\nThis will hurt more as the number of objects we deal with grows (our\nALLOC_GROW() shares the same).\n\nI wonder if it might be a good idea to do\n\n\tstruct commit_slab {\n        \tint piece_size;\n\t\tint piece_count;\n\t\tstruct commit_slab_piece {\n                \tint *buf;\n\t\t} *piece;\n\t};\n\nand then make the look-up logic like this:\n\n\tint nth_piece, nth_slot;\n\n\tnth_piece = c->index / s->piece_size;\n        nth_slot = c->index % s->piece_size;\n        if (s->piece_count <= nth_piece) {\n\t\t/* xrealloc s->piece to grow, update s->piece_count */\n        }\n        if (!s->piece[nth_piece]) {\n\t\t/* xcalloc s->piece[nth_piece] to allocate */\n\t}\n        return s->piece[nth_piece]->buf + nth_slot;\n\nOther than that, looks like a good technology demonstration.\n"}]}