<pre style='margin:0'>
Rainer Müller (raimue) pushed a commit to branch master
in repository macports-base.
</pre>
<p><a href="https://github.com/macports/macports-base/commit/1b07064687ffb55df286b8e365b2d5ad7da37ff0">https://github.com/macports/macports-base/commit/1b07064687ffb55df286b8e365b2d5ad7da37ff0</a></p>
<pre style="white-space: pre; background: #F8F8F8"><span style='display:block; white-space:pre;color:#808000;'>commit 1b07064687ffb55df286b8e365b2d5ad7da37ff0
</span>Author: Clemens Lang <cal@macports.org>
AuthorDate: Tue Oct 10 02:49:29 2017 +0200
<span style='display:block; white-space:pre;color:#404040;'> tracelib: Use binary search in dep_check()
</span><span style='display:block; white-space:pre;color:#404040;'>
</span><span style='display:block; white-space:pre;color:#404040;'> Keeping the list of dependencies sorted allows using binary search when
</span><span style='display:block; white-space:pre;color:#404040;'> determining whether a file is provided by a port in the dependency tree.
</span><span style='display:block; white-space:pre;color:#404040;'>
</span><span style='display:block; white-space:pre;color:#404040;'> Depending on the length of the list of dependencies, this can yield
</span><span style='display:block; white-space:pre;color:#404040;'> build time improvements of around 10 %.
</span><span style='display:block; white-space:pre;color:#404040;'>
</span><span style='display:block; white-space:pre;color:#404040;'> Additionally, use Tcl's list functions to interpret the list of
</span><span style='display:block; white-space:pre;color:#404040;'> dependencies rather than splitting at whitespaces manually.
</span>---
src/pextlib1.0/tracelib.c | 81 ++++++++++++++++++++++++++++++++++++-----------
1 file changed, 62 insertions(+), 19 deletions(-)
<span style='display:block; white-space:pre;color:#808080;'>diff --git a/src/pextlib1.0/tracelib.c b/src/pextlib1.0/tracelib.c
</span><span style='display:block; white-space:pre;color:#808080;'>index 1706c5f..6bfed82 100644
</span><span style='display:block; white-space:pre;background:#e0e0ff;'>--- a/src/pextlib1.0/tracelib.c
</span><span style='display:block; white-space:pre;background:#e0e0ff;'>+++ b/src/pextlib1.0/tracelib.c
</span><span style='display:block; white-space:pre;background:#e0e0e0;'>@@ -101,7 +101,8 @@ static void peerpid_list_walk(bool (*callback)(int sock, pid_t pid, const char *
</span> static char *name;
static char *sandbox;
static size_t sandboxLength;
<span style='display:block; white-space:pre;background:#ffe0e0;'>-static char *depends;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+static char **depends = NULL;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+static size_t dependsLength = 0;
</span> static int sock = -1;
static int kq = -1;
/* EVFILT_USER isn't available (< 10.6), use the self-pipe trick to return from
<span style='display:block; white-space:pre;background:#e0e0e0;'>@@ -351,9 +352,6 @@ static int TracelibSetNameCmd(Tcl_Interp *interp, int objc, Tcl_Obj *CONST objv[
</span> return TCL_ERROR;
}
<span style='display:block; white-space:pre;background:#ffe0e0;'>- // initialize the depends field, in case we don't actually have any dependencies
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- depends = NULL;
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>-
</span> return TCL_OK;
}
<span style='display:block; white-space:pre;background:#e0e0e0;'>@@ -605,7 +603,6 @@ static void sandbox_violation(int sock UNUSED, const char *path, sandbox_violati
</span> */
static void dep_check(int sock, char *path) {
char *port = 0;
<span style='display:block; white-space:pre;background:#ffe0e0;'>- char *t;
</span> int fs_cs = -1;
reg_registry *reg;
reg_entry entry;
<span style='display:block; white-space:pre;background:#e0e0e0;'>@@ -650,12 +647,23 @@ static void dep_check(int sock, char *path) {
</span> answer(sock, "#");
}
<span style='display:block; white-space:pre;background:#ffe0e0;'>- /* check our list of dependencies */
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- for (t = depends; t && *t; t += strlen(t) + 1) {
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- if (strcmp(t, port) == 0) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* check our list of dependencies; use binary search */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ size_t left = 0;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ size_t right = dependsLength;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ while (left < right) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ size_t index = left + (right - left) / 2;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ int result = strcmp(depends[index], port);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ if (result == 0) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* found the port */
</span> free(port);
answer(sock, "+");
return;
<span style='display:block; white-space:pre;background:#e0ffe0;'>+ } else if (result < 0) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* continue search right */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ left = index + 1;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ } else {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* continue search left */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ right = index;
</span> }
}
<span style='display:block; white-space:pre;background:#e0e0e0;'>@@ -969,7 +977,11 @@ static int TracelibCleanCmd(Tcl_Interp *interp UNUSED) {
</span> safe_free(name);
}
<span style='display:block; white-space:pre;background:#e0ffe0;'>+ for (size_t i = 0; i < dependsLength; ++i) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ safe_free(depends[i]);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ }
</span> safe_free(depends);
<span style='display:block; white-space:pre;background:#e0ffe0;'>+ dependsLength = 0;
</span>
enable_fence = 0;
return TCL_OK;
<span style='display:block; white-space:pre;background:#e0e0e0;'>@@ -1004,28 +1016,59 @@ static int TracelibCloseSocketCmd(Tcl_Interp *interp UNUSED) {
</span> return TCL_OK;
}
<span style='display:block; white-space:pre;background:#e0ffe0;'>+static int pointer_strcmp(const char** a, const char** b) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ return strcmp(*a, *b);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+}
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+
</span> static int TracelibSetDeps(Tcl_Interp *interp, int objc, Tcl_Obj *CONST objv[]) {
<span style='display:block; white-space:pre;background:#ffe0e0;'>- char *t, * d;
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- size_t l;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ Tcl_Obj **objects;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ int length;
</span> if (objc != 3) {
Tcl_WrongNumArgs(interp, 2, objv, "number of arguments should be exactly 3");
return TCL_ERROR;
}
<span style='display:block; white-space:pre;background:#ffe0e0;'>- d = Tcl_GetString(objv[2]);
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- l = strlen(d);
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- depends = malloc(l + 2);
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- if (!depends) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ if (TCL_OK != Tcl_ListObjGetElements(interp, objv[2], &length, &objects)) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ return TCL_ERROR;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ }
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* When called twice, do not leak memory */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ if (depends) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ for (size_t i = 0; i < dependsLength; ++i) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ free(depends[i]);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ }
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ free(depends);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ }
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ depends = NULL;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ dependsLength = 0;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* Allocate memory as needed */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ if (NULL == (depends = malloc(length * sizeof(*depends)))) {
</span> Tcl_SetResult(interp, "memory allocation failed", TCL_STATIC);
return TCL_ERROR;
}
<span style='display:block; white-space:pre;background:#ffe0e0;'>- depends[l + 1] = 0;
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- strlcpy(depends, d, l + 2);
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- for (t = depends; *t; ++t)
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- if (*t == ' ') {
</span><span style='display:block; white-space:pre;background:#ffe0e0;'>- *t++ = 0;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* Copy all objects over */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ for (int i = 0; i < length; ++i) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ if (NULL == (depends[i] = strdup(Tcl_GetString(objects[i])))) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* Allocation failed, clean up what we have so far */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ for (int j = 0; j < i; ++j) {
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ free(depends[j]);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ }
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ free(depends);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ depends = NULL;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ dependsLength = 0;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ Tcl_SetResult(interp, "memory allocation failed", TCL_STATIC);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ return TCL_ERROR;
</span> }
<span style='display:block; white-space:pre;background:#e0ffe0;'>+ dependsLength++;
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ }
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ /* Sort all dependencies so we can use binary searching */
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ qsort(depends, dependsLength, sizeof(*depends),
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+ (int (*)(const void*, const void*)) pointer_strcmp);
</span><span style='display:block; white-space:pre;background:#e0ffe0;'>+
</span> return TCL_OK;
}
</pre><pre style='margin:0'>
</pre>