From 11fa1ab8b496338e51d272775cf9badab94eb9fa Mon Sep 17 00:00:00 2001 From: Karsten Blees Date: Sun, 15 Jan 2012 02:30:02 +0100 Subject: [PATCH] Win32: keep the environment sorted The Windows environment is sorted, keep it that way for O(log n) environment access. Change compareenv to compare only the keys, so that it can be used to find an entry irrespective of the value. Change lookupenv to binary seach for an entry. Return one's complement of the insert position if not found (libc's bsearch returns NULL). Replace MSVCRT's getenv with a minimal do_getenv based on the binary search function. Change do_putenv to insert new entries at the correct position. Simplify the function by swapping if conditions and using memmove instead of for loops. Move qsort from make_environment_block to mingw_startup. We still need to sort on startup to make sure that the environment is sorted according to our compareenv function (while Win32 / CreateProcess requires the environment block to be sorted case-insensitively, CreateProcess currently doesn't enforce this, and some applications such as bash just don't care). Note that environment functions are _not_ thread-safe and are not required to be so by POSIX, the application is responsible for synchronizing access to the environment. MSVCRT's getenv and our new getenv implementation are better than that in that they are thread-safe with respect to other getenv calls as long as the environment is not modified. Git's indiscriminate use of getenv in background threads currently requires this property. Signed-off-by: Karsten Blees --- compat/mingw.c | 98 +++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 62 insertions(+), 36 deletions(-) diff --git a/compat/mingw.c b/compat/mingw.c index c7eff9473a..5d4e69a558 100644 --- a/compat/mingw.c +++ b/compat/mingw.c @@ -737,23 +737,42 @@ char *mingw_getcwd(char *pointer, int len) return pointer; } -static int compareenv(const void *a, const void *b) +/* + * Compare environment entries by key (i.e. stopping at '=' or '\0'). + */ +static int compareenv(const void *v1, const void *v2) { - char *const *ea = a; - char *const *eb = b; - return strcasecmp(*ea, *eb); + const char *e1 = *(const char**)v1; + const char *e2 = *(const char**)v2; + + for (;;) { + int c1 = *e1++; + int c2 = *e2++; + c1 = (c1 == '=') ? 0 : tolower(c1); + c2 = (c2 == '=') ? 0 : tolower(c2); + if (c1 > c2) + return 1; + if (c1 < c2) + return -1; + if (c1 == 0) + return 0; + } } -static int lookupenv(char **env, const char *name, size_t nmln) +static int bsearchenv(char **env, const char *name, size_t size) { - int i; - - for (i = 0; env[i]; i++) { - if (!strncasecmp(env[i], name, nmln) && '=' == env[i][nmln]) - /* matches */ - return i; + unsigned low = 0, high = size; + while (low < high) { + unsigned mid = low + ((high - low) >> 1); + int cmp = compareenv(&env[mid], &name); + if (cmp < 0) + low = mid + 1; + else if (cmp > 0) + high = mid; + else + return mid; } - return -1; + return ~low; /* not found, return 1's complement of insert position */ } /* @@ -763,26 +782,24 @@ static int lookupenv(char **env, const char *name, size_t nmln) */ static int do_putenv(char **env, const char *name, int size, int free_old) { - char *eq = strchrnul(name, '='); - int i = lookupenv(env, name, eq-name); + int i = bsearchenv(env, name, size - 1); - if (i < 0) { - if (*eq) { - env[size - 1] = (char*) name; - env[size] = NULL; + /* optionally free removed / replaced entry */ + if (i >= 0 && free_old) + free(env[i]); + + if (strchr(name, '=')) { + /* if new value ('key=value') is specified, insert or replace entry */ + if (i < 0) { + i = ~i; + memmove(&env[i + 1], &env[i], (size - i) * sizeof(char*)); size++; } - } - else { - if (free_old) - free(env[i]); - if (*eq) - env[i] = (char*) name; - else { - for (; env[i]; i++) - env[i] = env[i+1]; - size--; - } + env[i] = (char*) name; + } else if (i >= 0) { + /* otherwise ('key') remove existing entry */ + size--; + memmove(&env[i], &env[i + 1], (size - i) * sizeof(char*)); } return size; } @@ -792,15 +809,24 @@ static int environ_size = 0; /* allocated size of environ array, in bytes */ static int environ_alloc = 0; -#undef getenv +static char *do_getenv(const char *name) +{ + char *value; + int pos = bsearchenv(environ, name, environ_size - 1); + if (pos < 0) + return NULL; + value = strchr(environ[pos], '='); + return value ? &value[1] : NULL; +} + char *mingw_getenv(const char *name) { - char *result = getenv(name); + char *result = do_getenv(name); if (!result && !strcmp(name, "TMPDIR")) { /* on Windows it is TMP and TEMP */ - result = getenv("TMP"); + result = do_getenv("TMP"); if (!result) - result = getenv("TEMP"); + result = do_getenv("TEMP"); } else if (!result && !strcmp(name, "TERM")) { /* simulate TERM to enable auto-color (see color.c) */ @@ -1025,9 +1051,6 @@ static wchar_t *make_environment_block(char **deltaenv) for (i = 0; deltaenv && deltaenv[i]; i++) size = do_putenv(tmpenv, deltaenv[i], size, 0); - /* environment must be sorted */ - qsort(tmpenv, size - 1, sizeof(char*), compareenv); - /* create environment block from temporary environment */ for (i = 0; tmpenv[i]; i++) { size = 2 * strlen(tmpenv[i]) + 2; /* +2 for final \0 */ @@ -2107,6 +2130,9 @@ void mingw_startup() environ[i] = NULL; free(buffer); + /* sort environment for O(log n) getenv / putenv */ + qsort(environ, i, sizeof(char*), compareenv); + /* initialize critical section for waitpid pinfo_t list */ InitializeCriticalSection(&pinfo_cs); -- 2.11.4.GIT