Date: Wed, 19 Sep 2007 04:10:08 GMT From: Garrett Wollman <wollman@bimajority.org> To: freebsd-bugs@FreeBSD.org Subject: Re: bin/116452: pkg_create uses bogosort? Message-ID: <200709190410.l8J4A8SX007825@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
The following reply was made to PR bin/116452; it has been noted by GNATS.
From: Garrett Wollman <wollman@bimajority.org>
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;
}
/*
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200709190410.l8J4A8SX007825>