From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS2116 193.90.0.0/16 X-Spam-Status: No, score=0.4 required=3.0 tests=AWL,BAYES_00,RCVD_IN_MSPIKE_BL, RCVD_IN_MSPIKE_ZBI,RCVD_IN_XBL,RDNS_NONE,SPF_FAIL,SPF_HELO_FAIL,URIBL_RED shortcircuit=no autolearn=no autolearn_force=no version=3.4.0 Received: from 80x24.org (unknown [193.90.12.89]) by dcvr.yhbt.net (Postfix) with ESMTP id 1D73A20193 for ; Sun, 10 Jul 2016 11:46:35 +0000 (UTC) From: Eric Wong To: spew@80x24.org Subject: [PATCH 4/4] http-walker: use hashmap to eliminate list scan Date: Sun, 10 Jul 2016 11:46:27 +0000 Message-Id: <20160710114627.21504-4-e@80x24.org> In-Reply-To: <20160710114627.21504-1-e@80x24.org> References: <20160710114627.21504-1-e@80x24.org> List-Id: We can reduce list walking in fill_active_slot by deleting items as we walk through the object request queue of pending objects. However, we still need to maintain a mapping of live objects for fetch_object, so introduce the use of a hashmap to keep track of all live object requests in O(1) average time. Signed-off-by: Eric Wong --- http-walker.c | 42 +++++++++++++++++++++++++++--------------- 1 file changed, 27 insertions(+), 15 deletions(-) diff --git a/http-walker.c b/http-walker.c index b9fe33a..25f63de 100644 --- a/http-walker.c +++ b/http-walker.c @@ -3,6 +3,7 @@ #include "walker.h" #include "http.h" #include "list.h" +#include "hashmap.h" struct alt_base { char *base; @@ -19,10 +20,11 @@ enum object_request_state { }; struct object_request { + struct hashmap_entry ent; + enum object_request_state state; struct walker *walker; unsigned char sha1[20]; struct alt_base *repo; - enum object_request_state state; struct http_object_request *req; struct list_head node; }; @@ -43,6 +45,7 @@ struct walker_data { }; static LIST_HEAD(object_queue_head); +static struct hashmap *object_requests; static void fetch_alternates(struct walker *walker, const char *base); @@ -116,6 +119,7 @@ static void release_object_request(struct object_request *obj_req) error("fd leakage in release: %d", obj_req->req->localfile); list_del(&obj_req->node); + hashmap_remove(object_requests, obj_req, obj_req->sha1); free(obj_req); } @@ -127,13 +131,12 @@ static int fill_active_slot(struct walker *walker) list_for_each_safe(pos, tmp, head) { obj_req = list_entry(pos, struct object_request, node); - if (obj_req->state == WAITING) { - if (has_sha1_file(obj_req->sha1)) - obj_req->state = COMPLETE; - else { - start_object_request(walker, obj_req); - return 1; - } + list_del(pos); + if (has_sha1_file(obj_req->sha1)) + obj_req->state = COMPLETE; + else { + start_object_request(walker, obj_req); + return 1; } } return 0; @@ -146,6 +149,8 @@ static void prefetch(struct walker *walker, unsigned char *sha1) struct walker_data *data = walker->data; newreq = xmalloc(sizeof(*newreq)); + hashmap_entry_init(&newreq->ent, sha1hash(sha1)); + hashmap_add(object_requests, &newreq->ent); newreq->walker = walker; hashcpy(newreq->sha1, sha1); newreq->repo = data->alt; @@ -436,15 +441,11 @@ static int fetch_object(struct walker *walker, unsigned char *sha1) { char *hex = sha1_to_hex(sha1); int ret = 0; - struct object_request *obj_req = NULL; + struct object_request *obj_req, key; struct http_object_request *req; - struct list_head *pos, *head = &object_queue_head; - list_for_each(pos, head) { - obj_req = list_entry(pos, struct object_request, node); - if (!hashcmp(obj_req->sha1, sha1)) - break; - } + hashmap_entry_init(&key, sha1hash(sha1)); + obj_req = hashmap_get(object_requests, &key, sha1); if (obj_req == NULL) return error("Couldn't find request for %s in the queue", hex); @@ -554,6 +555,12 @@ static void cleanup(struct walker *walker) } } +static int obj_req_cmp(const struct object_request *e1, + const struct object_request *e2, const unsigned char *sha1) +{ + return hashcmp(e1->sha1, sha1 ? sha1 : e2->sha1); +} + struct walker *get_http_walker(const char *url) { char *s; @@ -581,5 +588,10 @@ struct walker *get_http_walker(const char *url) add_fill_function(walker, (int (*)(void *)) fill_active_slot); #endif + if (!object_requests) { + object_requests = xmalloc(sizeof(*object_requests)); + hashmap_init(object_requests, (hashmap_cmp_fn)obj_req_cmp, 0); + } + return walker; } -- EW