{"thread":{"id":"2757","subject":"type_size_sort","startedAt":"2005-12-06T21:19:21Z","lastAt":"2005-12-07T03:01:30Z","messageCount":7,"participants":["Morten Welinder","Andreas Ericsson","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"13279","messageId":"118833cc0512061319l3726fdfbs8286e7b3f5ab0713@mail.gmail.com","threadId":"2757","inReplyTo":null,"subject":"type_size_sort","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2005-12-06T21:19:21Z","receivedAt":"2005-12-06T21:19:21Z","isPatch":false,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"static int type_size_sort(const struct object_entry *a, const struct\nobject_entry *b)\n{\n...\n return a < b ? -1 : (a > b);\n}\n\nThis does not look valid. the standard says you must not depend on the\nlocation:\n\n\n [#4] When the same objects (consisting of size bytes,\n irrespective of their current positions in the array) are\n passed more than once to the comparison function, the\n results shall be consistent with one another. That is, for\n qsort they shall define a total ordering on the array, and\n for bsearch the same object shall always compare the same\n way with the key.\n\n\nM.\n"},{"id":"13282","messageId":"439604DF.5010603@op5.se","threadId":"2757","inReplyTo":"118833cc0512061319l3726fdfbs8286e7b3f5ab0713@mail.gmail.com","subject":"Re: type_size_sort","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2005-12-06T21:38:39Z","receivedAt":"2005-12-06T21:38:39Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Morten Welinder wrote:\n> static int type_size_sort(const struct object_entry *a, const struct\n> object_entry *b)\n> {\n> ...\n> return a < b ? -1 : (a > b);\n> }\n> \n> This does not look valid. the standard says you must not depend on the\n> location:\n> \n> \n> [#4] When the same objects (consisting of size bytes,\n> irrespective of their current positions in the array) are\n> passed more than once to the comparison function, the\n> results shall be consistent with one another. That is, for\n> qsort they shall define a total ordering on the array, and\n> for bsearch the same object shall always compare the same\n> way with the key.\n> \n\nIt's perfectly correct. If the same list was to be passed to \ncreate_sorted_list() twice it will come out exactly the same the second \ntime as it did the first. The only thing to remark on is that the return \nabove could be written as below instead:\n\n\treturn a - b;\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"13284","messageId":"7vpso92940.fsf@assigned-by-dhcp.cox.net","threadId":"2757","inReplyTo":"118833cc0512061319l3726fdfbs8286e7b3f5ab0713@mail.gmail.com","subject":"Re: type_size_sort","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-06T21:45:03Z","receivedAt":"2005-12-06T21:45:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Morten Welinder writes:\n\n> static int type_size_sort(const struct object_entry *a, const struct\n> object_entry *b)\n> {\n> ...\n> return a < b ? -1 : (a > b);\n> }\n>\n> This does not look valid.\n\nThen something like this?\n\n---\ndiff --git a/pack-objects.c b/pack-objects.c\nindex a62c9f8..c27fee5 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -296,7 +296,7 @@ static int type_size_sort(const struct o\n \t\treturn -1;\n \tif (a->size > b->size)\n \t\treturn 1;\n-\treturn a < b ? -1 : (a > b);\n+\treturn memcmp(a->sha1, b->sha1, 20);\n }\n \n struct unpacked {\n"},{"id":"13285","messageId":"7vlkyx2911.fsf@assigned-by-dhcp.cox.net","threadId":"2757","inReplyTo":"439604DF.5010603@op5.se","subject":"Re: type_size_sort","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-06T21:46:50Z","receivedAt":"2005-12-06T21:46:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Ericsson writes:\n\n\n> It's perfectly correct. If the same list was to be passed to \n> create_sorted_list() twice it will come out exactly the same the second \n> time as it did the first. The only thing to remark on is that the return \n> above could be written as below instead:\n>\n> \treturn a - b;\n\nAnd I suspect Morten would say the same thing about ptrdiff_t\ncould be larger than an int.\n\nI personally feel this would not make any practical difference\non sane architectures either way, though..\n"},{"id":"13301","messageId":"118833cc0512061651y57ddcdc7pd26996b40c08d225@mail.gmail.com","threadId":"2757","inReplyTo":"439604DF.5010603@op5.se","subject":"Re: type_size_sort","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2005-12-07T00:51:44Z","receivedAt":"2005-12-07T00:51:44Z","isPatch":false,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"> It's perfectly correct. If the same list was to be passed to\n> create_sorted_list() twice it will come out exactly the same the second\n> time as it did the first. The only thing to remark on is that the return\n> above could be written as below instead:\n>\n> return a - b;\n\nThat is not what the part of the standard I quoted says. It very\nclearly forbids the sorting function from depending on the pointers'\nvalues. I can even see an implementation actually using this\nrequirement.\n\nAnd it is well known that some qsort implementations will do nasty\nthings if the sorting order is not consistent. I've seen Perl core\ndumps on that account, although that is a while ago.\n\nM.\n"},{"id":"13305","messageId":"7vmzjdy721.fsf@assigned-by-dhcp.cox.net","threadId":"2757","inReplyTo":"118833cc0512061651y57ddcdc7pd26996b40c08d225@mail.gmail.com","subject":"Re: type_size_sort","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-07T02:28:22Z","receivedAt":"2005-12-07T02:28:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Morten Welinder writes:\n\n>> It's perfectly correct. If the same list was to be passed to\n>> create_sorted_list() twice it will come out exactly the same the second\n>> time as it did the first. The only thing to remark on is that the return\n>> above could be written as below instead:\n>>\n>> return a - b;\n>\n> That is not what the part of the standard I quoted says. It very\n> clearly forbids the sorting function from depending on the pointers'\n> values. I can even see an implementation actually using this\n> requirement.\n\nWhat you say is correct, and people should be careful when using\nqsort(), but it does not apply to this case. The patch I posted\nis not necessary. Andreas' rewrite quoted above, however, is\ninvalid when ptrdiff_t (a-b) overflows int range.\n\nThe code as written by Linus back on June 25 is correct, but\nthat sort callchain is written in an unusual way to confuse us\n(you were, and I was initially after seeing your message).\n\n(1) The caller look like this. It prepares an array of pointers\n in list[], calls qsort with sort_comparator() as the\n function to sort this list[]. Each element in this list[]\n is a pointer to struct object_entry.\n\n\tfor (i = 0; i < nr_objects; i++)\n\t\tlist[i] = objects + i;\n\tcurrent_sort = sort;\n\tqsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);\n\n(2) sort_comparator() is called by qsort() with the standard\n calling convention -- two pointers pointing into the array\n being sorted. It calls current_sort() function set up by\n (1), giving it the pointers *FETCHED* *FROM* the locations\n these two incoming pointers are pointing at.\n\n static entry_sort_t current_sort;\n static int sort_comparator(const void *_a, const void *_b)\n {\n struct object_entry *a = *(struct object_entry **)_a;\n struct object_entry *b = *(struct object_entry **)_b;\n return current_sort(a,b);\n }\n\n(3) Then type_size_sort() uses compariosn of these two pointers\n as the tiebreaker.\n\nNotice? The comparison of two pointers you originally pointed\nout is not about the location in list[]. They are values stored\nthere.\n"},{"id":"13306","messageId":"118833cc0512061901p565de8a8x5543c95903cd6c2a@mail.gmail.com","threadId":"2757","inReplyTo":"7vmzjdy721.fsf@assigned-by-dhcp.cox.net","subject":"Re: type_size_sort","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2005-12-07T03:01:30Z","receivedAt":"2005-12-07T03:01:30Z","isPatch":false,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"> Notice? The comparison of two pointers you originally pointed\n> out is not about the location in list[]. They are values stored\n> there.\n\nAh, right you are.\n\nMildly relatedly, notice that a