From owner-freebsd-bugs@FreeBSD.ORG Wed Sep 19 04:10:09 2007 Return-Path: Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 2562616A418 for ; Wed, 19 Sep 2007 04:10:09 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:4f8:fff6::28]) by mx1.freebsd.org (Postfix) with ESMTP id C8CC613C46E for ; Wed, 19 Sep 2007 04:10:08 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1]) by freefall.freebsd.org (8.14.1/8.14.1) with ESMTP id l8J4A8J1007828 for ; Wed, 19 Sep 2007 04:10:08 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.1/8.14.1/Submit) id l8J4A8SX007825; Wed, 19 Sep 2007 04:10:08 GMT (envelope-from gnats) Date: Wed, 19 Sep 2007 04:10:08 GMT Message-Id: <200709190410.l8J4A8SX007825@freefall.freebsd.org> To: freebsd-bugs@FreeBSD.org From: Garrett Wollman Cc: Subject: Re: bin/116452: pkg_create uses bogosort? X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Garrett Wollman List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 19 Sep 2007 04:10:09 -0000 The following reply was made to PR bin/116452; it has been noted by GNATS. From: Garrett Wollman To: FreeBSD-gnats-submit@FreeBSD.org Cc: Subject: Re: bin/116452: pkg_create uses bogosort? Date: Wed, 19 Sep 2007 00:04:29 -0400 I tracked this issue down as far as isinstalledpkg(). Here is a patch that memoizes the result of isinstalledpkg(). I haven't tested this code outside of pkg_create so I do not know if there needs to be an invalidation mechanism (e.g., for pkg_install when installing dependencies recursively). It's possible that only "yes" responses should be memoized. -GAWollman Index: lib/match.c =================================================================== RCS file: /home/ncvs/src/usr.sbin/pkg_install/lib/match.c,v retrieving revision 1.19.8.1 diff -u -r1.19.8.1 match.c --- lib/match.c 27 Sep 2005 13:39:06 -0000 1.19.8.1 +++ lib/match.c 19 Sep 2007 03:11:07 -0000 @@ -307,6 +307,17 @@ } /* + * Small linked list to memoize results of isinstalledpkg(). A hash table + * would be faster but for n ~= 1000 may be overkill. + */ +struct iip_memo { + LIST_ENTRY(iip_memo) iip_link; + char *iip_name; + int iip_result; +}; +LIST_HEAD(, iip_memo) iip_memo = LIST_HEAD_INITIALIZER(iip_memo); + +/* * * Return 1 if the specified package is installed, * 0 if not, and -1 if an error occured. @@ -314,18 +325,53 @@ int isinstalledpkg(const char *name) { - char buf[FILENAME_MAX]; - char buf2[FILENAME_MAX]; - - snprintf(buf, sizeof(buf), "%s/%s", LOG_DIR, name); - if (!isdir(buf) || access(buf, R_OK) == FAIL) - return 0; - - snprintf(buf2, sizeof(buf2), "%s/%s", buf, CONTENTS_FNAME); - if (!isfile(buf2) || access(buf2, R_OK) == FAIL) - return -1; + int result; + char *buf, *buf2; + struct iip_memo *memo; + + LIST_FOREACH(memo, &iip_memo, iip_link) { + if (strcmp(memo->iip_name, name) == 0) + return memo->iip_result; + } + + buf2 = NULL; + asprintf(&buf, "%s/%s", LOG_DIR, name); + if (buf == NULL) + goto errout; + if (!isdir(buf) || access(buf, R_OK) == FAIL) { + result = 0; + } else { + asprintf(&buf2, "%s/%s", buf, CONTENTS_FNAME); + if (buf2 == NULL) + goto errout; + + if (!isfile(buf2) || access(buf2, R_OK) == FAIL) + result = -1; + else + result = 1; + } - return 1; + free(buf); + buf = strdup(name); + if (buf == NULL) + goto errout; + free(buf2); + buf2 = NULL; + + memo = malloc(sizeof *memo); + if (memo == NULL) + goto errout; + memo->iip_name = buf; + memo->iip_result = result; + LIST_INSERT_HEAD(&iip_memo, memo, iip_link); + return result; + +errout: + if (buf != NULL) + free(buf); + if (buf2 != NULL) + free(buf2); + return -1; } /*