summaryrefslogtreecommitdiff
path: root/list.h
Commit message (Collapse)AuthorAgeFilesLines
* list: avoid incompatibility with *BSD sys/queue.hew/http-walkerEric Wong2016-07-181-0/+2
| | | | | | | | | | | | The OS X build pulls in sys/queue.h, which pollutes the preprocessor namespace with a macro generically named LIST_HEAD, and clashes with the name we use here. ref: http://mid.gmane.org/FB76544F-16F7-45CA-9649-FD62EE44B0DE@gmail.com Reported-by: Lars Schneider <larsxschneider@gmail.com> Signed-off-by: Eric Wong <e@80x24.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* http-walker: reduce O(n) ops with doubly-linked listEric Wong2016-07-121-0/+164
Using the a Linux-kernel-derived doubly-linked list implementation from the Userspace RCU library allows us to enqueue and delete items from the object request queue in constant time. This change reduces enqueue times in the prefetch() function where object request queue could grow to several thousand objects. I left out the list_for_each_entry* family macros from list.h which relied on the __typeof__ operator as we support platforms without it. Thus, list_entry (aka "container_of") needs to be called explicitly inside macro-wrapped for loops. The downside is this costs us an additional pointer per object request, but this is offset by reduced overhead on queue operations leading to improved performance and shorter queue depths. Signed-off-by: Eric Wong <e@80x24.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>