native/common/jk_map.c (700 lines of code) (raw):

/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /*************************************************************************** * Description: General purpose map object * * Author: Gal Shachor <shachor@il.ibm.com> * * Author: Mladen Turk <mturk@apache.org> * ***************************************************************************/ #if defined(AS400) && !defined(AS400_UTF8) #include "apr_xlate.h" #endif #include "jk_global.h" #include "jk_pool.h" #include "jk_util.h" #include "jk_map.h" #define CAPACITY_INC_SIZE (50) #define LENGTH_OF_LINE (8192) #define JK_MAP_RECURSION (20) #define JK_MAP_REFERENCE (".reference") #define JK_MAP_REFERENCE_SZ (strlen(JK_MAP_REFERENCE)) /* Taken from APR tables/apr_hash.c */ /* * This is the popular `times 33' hash algorithm which is used by * perl and also appears in Berkeley DB. This is one of the best * known hash functions for strings because it is both computed * very fast and distributes very well. * * The originator may be Dan Bernstein but the code in Berkeley DB * cites Chris Torek as the source. The best citation I have found * is "Chris Torek, Hash function for text in C, Usenet message * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich * Salz's USENIX 1992 paper about INN which can be found at * <http://citeseer.nj.nec.com/salz92internetnews.html>. * * The magic of number 33, i.e. why it works better than many other * constants, prime or not, has never been adequately explained by * anyone. So I try an explanation: if one experimentally tests all * multipliers between 1 and 256 (as I did while writing a low-level * data structure library some time ago) one detects that even * numbers are not useable at all. The remaining 128 odd numbers * (except for the number 1) work more or less all equally well. * They all distribute in an acceptable way and this way fill a hash * table with an average percent of approx. 86%. * * If one compares the chi^2 values of the variants (see * Bob Jenkins ``Hashing Frequently Asked Questions'' at * http://burtleburtle.net/bob/hash/hashfaq.html for a description * of chi^2), the number 33 not even has the best value. But the * number 33 and a few other equally good numbers like 17, 31, 63, * 127 and 129 have nevertheless a great advantage to the remaining * numbers in the large set of possible multipliers: their multiply * operation can be replaced by a faster operation based on just one * shift plus either a single addition or subtraction operation. And * because a hash function has to both distribute good _and_ has to * be very fast to compute, those few numbers should be preferred. * * -- Ralf S. Engelschall <rse@engelschall.com> */ #define COMPUTE_KEY_HASH(key, hash) \ { \ const unsigned char *p; \ hash = 0; \ for (p = (const unsigned char *)key; *p; p++) { \ hash = hash * 33 + *p; \ } \ } static volatile int global_map_id = 0; static void trim_prp_comment(char *prp); static size_t trim(char *s); static int map_realloc(jk_map_t *m); static char *jk_map_replace_properties(jk_map_t *m, jk_map_t *env, char *value); int jk_map_alloc(jk_map_t **m) { if (m) { *m = (jk_map_t *)calloc(1, sizeof(jk_map_t)); if (*m) return jk_map_open(*m); } return JK_FALSE; } int jk_map_free(jk_map_t **m) { int rc = JK_FALSE; if (m && *m) { jk_map_close(*m); free(*m); *m = NULL; } return rc; } int jk_map_open(jk_map_t *m) { int rc = JK_FALSE; if (m) { jk_open_pool(&m->p, m->buf, sizeof(jk_pool_atom_t) * SMALL_POOL_SIZE); m->id = ++global_map_id; m->capacity = 0; m->size = 0; m->keys = NULL; m->names = NULL; m->values = NULL; rc = JK_TRUE; } return rc; } int jk_map_close(jk_map_t *m) { int rc = JK_FALSE; if (m) { jk_close_pool(&m->p); rc = JK_TRUE; } return rc; } void *jk_map_get(jk_map_t *m, const char *name, const void *def) { const void *rc = (void *)def; if (m && name) { unsigned int i; unsigned int hash; COMPUTE_KEY_HASH(name, hash) for (i = 0; i < m->size; i++) { if (m->keys[i] == hash && strcmp(m->names[i], name) == 0) { rc = m->values[i]; break; } } } return (void *)rc; /* DIRTY */ } int jk_map_get_id(jk_map_t *m, const char *name) { int rc = -1; if (m && name) { unsigned int i; unsigned int hash; COMPUTE_KEY_HASH(name, hash) for (i = 0; i < m->size; i++) { if (m->keys[i] == hash && strcmp(m->names[i], name) == 0) { rc = i; break; } } } return rc; } const char *jk_map_get_string(jk_map_t *m, const char *name, const char *def) { const char *rc = def; if (m && name) { unsigned int i; unsigned int hash; COMPUTE_KEY_HASH(name, hash) for (i = 0; i < m->size; i++) { if (m->keys[i] == hash && strcmp(m->names[i], name) == 0) { rc = m->values[i]; break; } } } return rc; } int jk_map_get_int(jk_map_t *m, const char *name, int def) { char buf[100]; const char *rc; size_t len; int int_res; sprintf(buf, "%d", def); rc = jk_map_get_string(m, name, buf); len = strlen(rc); if (len) { const char *lastchar = &rc[0] + len - 1; int multit = 1; if ('m' == *lastchar || 'M' == *lastchar) { multit = 1024 * 1024; } else if ('k' == *lastchar || 'K' == *lastchar) { multit = 1024; } /* Safe because atoi() will stop at any non-numeric lastchar */ int_res = atoi(rc) * multit; } else int_res = def; return int_res; } double jk_map_get_double(jk_map_t *m, const char *name, double def) { char buf[100]; const char *rc; sprintf(buf, "%f", def); rc = jk_map_get_string(m, name, buf); return atof(rc); } int jk_map_get_bool(jk_map_t *m, const char *name, int def) { char buf[100]; const char *rc; sprintf(buf, "%d", def); rc = jk_map_get_string(m, name, buf); return jk_get_bool_code(rc, def); } char **jk_map_get_string_list(jk_map_t *m, const char *name, unsigned int *list_len, const char *def) { const char *l = jk_map_get_string(m, name, def); char **ar = NULL; #ifdef _MT_CODE_PTHREAD char *lasts; #endif *list_len = 0; if (l) { unsigned capacity = 0; unsigned idex = 0; char *p; char *v = jk_pool_strdup(&m->p, l); if (!v) { return NULL; } /* * GS, in addition to VG's patch, we now need to * strtok also by a "*" */ #ifdef _MT_CODE_PTHREAD for (p = strtok_r(v, " \t,", &lasts); p; p = strtok_r(NULL, " \t,", &lasts)) #else for (p = strtok(v, " \t,"); p; p = strtok(NULL, " \t,")) #endif { if (idex == capacity) { ar = jk_pool_realloc(&m->p, sizeof(char *) * (capacity + 5), ar, sizeof(char *) * capacity); if (!ar) { return NULL; } capacity += 5; } ar[idex] = jk_pool_strdup(&m->p, p); idex++; } *list_len = idex; } return ar; } int *jk_map_get_int_list(jk_map_t *m, const char *name, unsigned int *list_len, const char *def) { const char *l = jk_map_get_string(m, name, def); int *ar = NULL; #ifdef _MT_CODE_PTHREAD char *lasts; #endif if (l) { unsigned int capacity = 0; unsigned int idex = 0; char *p; char *v = jk_pool_strdup(&m->p, l); if (!v) { return NULL; } /* * GS, in addition to VG's patch, we now need to * strtok also by a "*" */ #ifdef _MT_CODE_PTHREAD for (p = strtok_r(v, " \t,", &lasts); p; p = strtok_r(NULL, " \t,", &lasts)) #else for (p = strtok(v, " \t,"); p; p = strtok(NULL, " \t,")) #endif { if (idex == capacity) { ar = jk_pool_realloc(&m->p, sizeof(int) * (capacity + 5), ar, sizeof(int) * capacity); if (!ar) { return NULL; } capacity += 5; } ar[idex] = atoi(p); idex++; } *list_len = idex; } return ar; } int jk_map_add(jk_map_t *m, const char *name, const void *value) { int rc = JK_FALSE; if (m && name) { unsigned int hash; COMPUTE_KEY_HASH(name, hash) map_realloc(m); if (m->size < m->capacity) { m->values[m->size] = value; m->names[m->size] = jk_pool_strdup(&m->p, name); m->keys[m->size] = hash; m->size++; rc = JK_TRUE; } } return rc; } int jk_map_put(jk_map_t *m, const char *name, const void *value, void **old) { int rc = JK_FALSE; if (m && name) { unsigned int i; unsigned int hash; COMPUTE_KEY_HASH(name, hash) for (i = 0; i < m->size; i++) { if (m->keys[i] == hash && strcmp(m->names[i], name) == 0) { break; } } if (i < m->size) { if (old) *old = (void *)m->values[i]; /* DIRTY */ m->values[i] = value; rc = JK_TRUE; } else { rc = jk_map_add(m, name, value); } } return rc; } static int jk_map_validate_property(char *prp, jk_log_context_t *l) { /* check the worker properties */ if (!jk_is_valid_property(prp)) { jk_log(l, JK_LOG_ERROR, "The attribute '%s' is not supported - please check" " the documentation for the supported attributes.", prp); return JK_FALSE; } if (jk_is_deprecated_property(prp)) { jk_log(l, JK_LOG_WARNING, "The attribute '%s' is deprecated - please check" " the documentation for the correct replacement.", prp); } return JK_TRUE; } static int jk_map_handle_duplicates(jk_map_t *m, const char *prp, char **v, int treatment, jk_log_context_t *l) { const char *oldv = jk_map_get_string(m, prp, NULL); if (oldv) { if ((treatment == JK_MAP_HANDLE_DUPLICATES) && jk_is_unique_property(prp) == JK_FALSE) { char *tmpv = jk_pool_alloc(&m->p, strlen(*v) + strlen(oldv) + 3); if (tmpv) { char sep = '*'; if (jk_is_path_property(prp)) sep = PATH_SEPERATOR; else if (jk_is_cmd_line_property(prp)) sep = ' '; else if (jk_is_list_property(prp)) sep = ','; sprintf(tmpv, "%s%c%s", oldv, sep, *v); } *v = tmpv; if (JK_IS_DEBUG_LEVEL(l)) jk_log(l, JK_LOG_DEBUG, "Concatenated value is: %s -> %s", prp, *v); return JK_FALSE; } else { jk_log(l, JK_LOG_WARNING, "Duplicate key '%s' detected - previous value '%s'" " will be overwritten with '%s'.", prp, oldv ? oldv : "(null)", v ? *v : "(null)"); return JK_TRUE; } } else { return JK_TRUE; } } int jk_map_read_property(jk_map_t *m, jk_map_t *env, const char *str, int treatment, jk_log_context_t *l) { int rc = JK_TRUE; char buf[LENGTH_OF_LINE + 1]; char *prp = &buf[0]; if (strlen(str) > LENGTH_OF_LINE) { jk_log(l, JK_LOG_ERROR, "Line too long (%d > %d), ignoring entry", strlen(str), LENGTH_OF_LINE); return JK_FALSE; } strcpy(prp, str); if (trim(prp)) { char *v = strchr(prp, '='); if (v) { *v = '\0'; v++; if (trim(v) && trim(prp)) { if (treatment == JK_MAP_HANDLE_RAW) { v = jk_pool_strdup(&m->p, v); } else { if (jk_map_validate_property(prp, l) == JK_FALSE) return JK_FALSE; v = jk_map_replace_properties(m, env, v); if (jk_map_handle_duplicates(m, prp, &v, treatment, l) == JK_TRUE) v = jk_pool_strdup(&m->p, v); } if (v) { if (JK_IS_DEBUG_LEVEL(l)) jk_log(l, JK_LOG_DEBUG, "Adding property '%s' with value '%s' to map.", prp, v); jk_map_put(m, prp, v, NULL); } else { JK_LOG_NULL_PARAMS(l); rc = JK_FALSE; } } } } return rc; } int jk_map_read_properties(jk_map_t *m, jk_map_t *env, const char *f, time_t *modified, int treatment, jk_log_context_t *l) { int rc = JK_FALSE; if (m && f) { struct stat statbuf; FILE *fp; if (jk_stat(f, &statbuf) == -1) return JK_FALSE; #if defined(AS400) && !defined(AS400_UTF8) fp = fopen(f, "r, o_ccsid=0"); #else fp = fopen(f, "r"); #endif if (fp) { char buf[LENGTH_OF_LINE + 1]; char *prp; rc = JK_TRUE; while (NULL != (prp = fgets(buf, LENGTH_OF_LINE, fp))) { trim_prp_comment(prp); if (*prp) { if ((rc = jk_map_read_property(m, env, prp, treatment, l)) == JK_FALSE) break; } } fclose(fp); if (modified) *modified = statbuf.st_mtime; } } return rc; } int jk_map_size(jk_map_t *m) { if (m) { return m->size; } return -1; } const char *jk_map_name_at(jk_map_t *m, int idex) { if (m && idex >= 0) { return m->names[idex]; /* DIRTY */ } return NULL; } void *jk_map_value_at(jk_map_t *m, int idex) { if (m && idex >= 0) { return (void *)m->values[idex]; /* DIRTY */ } return NULL; } void jk_map_dump(jk_map_t *m, jk_log_context_t *l) { if (m) { int s = jk_map_size(m); int i; for (i=0;i<s;i++) { if (!jk_map_name_at(m, i)) { jk_log(l, JK_LOG_WARNING, "Map contains empty name at index %d\n", i); } if (!jk_map_value_at(m, i)) { jk_log(l, JK_LOG_WARNING, "Map contains empty value for name '%s' at index %d\n", jk_map_name_at(m, i), i); } if (JK_IS_DEBUG_LEVEL(l)) { jk_log(l, JK_LOG_DEBUG, "Dump of map %d: '%s' -> '%s'", m->id, jk_map_name_at(m, i) ? jk_map_name_at(m, i) : "(null)", jk_map_value_at(m, i) ? jk_map_value_at(m, i) : "(null)"); } } } } int jk_map_copy(jk_map_t *src, jk_map_t *dst) { int sz = jk_map_size(src); int i; for (i = 0; i < sz; i++) { const char *name = jk_map_name_at(src, i); if (jk_map_get(dst, name, NULL) == NULL) { if (!jk_map_put(dst, name, jk_pool_strdup(&dst->p, jk_map_get_string(src, name, NULL)), NULL)) { return JK_FALSE; } } } return JK_TRUE; } static void trim_prp_comment(char *prp) { #if defined(AS400) && !defined(AS400_UTF8) char *comment; /* lots of lines that translate a '#' realtime deleted */ comment = strchr(prp, *APR_NUMBERSIGN); #else char *comment = strchr(prp, '#'); #endif if (comment) { *comment = '\0'; } } static size_t trim(char *s) { size_t first; size_t len; /* check for empty strings */ if (!(len = strlen(s))) return 0; for (len = len - 1; (len > 0) && jk_isspace(s[len]); len--); if ((len > 0) || !jk_isspace(s[len])) { len++; } s[len] = '\0'; len++; for (first = 0; (s[first] != '\0') && jk_isspace(s[first]); first++); if (first > 0) { memmove(s, s + first, len - first); } return len; } static int map_realloc(jk_map_t *m) { if (m->size == m->capacity) { const char **names; const void **values; unsigned int *keys; int capacity = m->capacity + CAPACITY_INC_SIZE; size_t old_sz = m->capacity * sizeof(void *); size_t new_sz = capacity * sizeof(void *); names = (const char **)jk_pool_realloc(&m->p, new_sz, m->names, old_sz); values = (const void **)jk_pool_realloc(&m->p, new_sz, m->values, old_sz); keys = (unsigned int *)jk_pool_realloc(&m->p, new_sz, m->keys, old_sz); if (values && names && keys) { m->names = names; m->values = values; m->keys = keys; m->capacity = capacity; return JK_TRUE; } } return JK_FALSE; } /** * Replace $(property) in value. * */ static char *jk_map_replace_properties(jk_map_t *m, jk_map_t *env, char *value) { char *rc = value; char *env_start = rc; int rec = 0; while ((env_start = strstr(env_start, "$(")) != NULL) { char *env_end = strstr(env_start, ")"); if (rec++ > 20) return rc; if (env_end) { char env_name[LENGTH_OF_LINE + 1] = ""; const char *env_value; #if defined(WIN32) char env_buf[LENGTH_OF_LINE + 1]; #endif *env_end = '\0'; strcpy(env_name, env_start + 2); *env_end = ')'; env_value = jk_map_get_string(m, env_name, NULL); if (!env_value) { env_value = getenv(env_name); } if (!env_value && env) { /* Search inside local environment table */ env_value = jk_map_get_string(env, env_name, NULL); } #if defined(WIN32) if (!env_value) { /* Try the env block from calling process */ if (GetEnvironmentVariable(env_name, env_buf, sizeof(env_buf))) env_value = &env_buf[0]; } #endif if (env_value) { size_t offset = 0; char *new_value = jk_pool_alloc(&m->p, (sizeof(char) * (strlen(rc) + strlen(env_value)))); if (!new_value) { break; } *env_start = '\0'; strcpy(new_value, rc); strcat(new_value, env_value); strcat(new_value, env_end + 1); offset = env_start - rc + strlen(env_value); rc = new_value; /* Avoid recursive subst */ env_start = rc + offset; } else { env_start = env_end; } } else { break; } } return rc; } /** * Resolve references * */ int jk_map_resolve_references(jk_map_t *m, const char *prefix, int wildcard, int depth, jk_log_context_t *l) { int rc = JK_FALSE; JK_TRACE_ENTER(l); if (m && prefix) { if (depth <= JK_MAP_RECURSION) { size_t prelen = strlen(prefix); unsigned int i; rc = JK_TRUE; if (JK_IS_DEBUG_LEVEL(l)) jk_log(l, JK_LOG_DEBUG, "Checking for references with prefix %s with%s wildcard (recursion %d)", prefix, wildcard? "" : "out", depth); for (i = 0; i < m->size; i++) { char *v = (char *)m->values[i]; if (v && *v && !strncmp(m->names[i], prefix, prelen)) { size_t remain = strlen(m->names[i]) - prelen; if ((remain == JK_MAP_REFERENCE_SZ) || (wildcard && remain > JK_MAP_REFERENCE_SZ)) { remain = strlen(m->names[i]) - JK_MAP_REFERENCE_SZ; if (!strncmp(m->names[i] + remain, JK_MAP_REFERENCE, JK_MAP_REFERENCE_SZ)) { char *from = jk_pool_alloc(&m->p, (sizeof(char) * (strlen(v) + 2))); char *to = jk_pool_alloc(&m->p, (sizeof(char) * (remain + 2))); if (!from || !to) { jk_log(l, JK_LOG_ERROR, "Error in string allocation"); rc = JK_FALSE; break; } strcpy(from, v); *(from+strlen(v)) = '.'; *(from+strlen(v)+1) = '\0'; strncpy(to, m->names[i], remain); *(to+remain) = '.'; *(to+remain+1) = '\0'; rc = jk_map_resolve_references(m, v, 0, depth+1, l); if (rc == JK_FALSE) { break; } if (JK_IS_DEBUG_LEVEL(l)) jk_log(l, JK_LOG_DEBUG, "Copying values from %s to %s", from, to); rc = jk_map_inherit_properties(m, from, to, l); if (rc == JK_FALSE) { break; } } } } } } else { jk_log(l, JK_LOG_ERROR, "Recursion limit %d for worker references with prefix '%s' reached", JK_MAP_RECURSION, prefix); } } else { JK_LOG_NULL_PARAMS(l); } JK_TRACE_EXIT(l); return rc; } /** * Inherit properties * */ int jk_map_inherit_properties(jk_map_t *m, const char *from, const char *to, jk_log_context_t *l) { int rc = JK_FALSE; const char *prp; char *to_prp; if (m && from && to) { unsigned int i; for (i = 0; i < m->size; i++) { if (!strncmp(m->names[i], from, strlen(from))) { rc = JK_TRUE; prp = m->names[i] + strlen(from); to_prp = jk_pool_alloc(&m->p, (sizeof(char) * (strlen(to) + strlen(prp) + 1))); if (!to_prp) { jk_log(l, JK_LOG_ERROR, "Error in string allocation for attribute '%s.%s'", to, prp); rc = JK_FALSE; break; } strcpy(to_prp, to); strcat(to_prp, prp); if (jk_map_get_id(m, to_prp) < 0) { rc = jk_map_add(m, to_prp, m->values[i]); if (rc == JK_FALSE) { jk_log(l, JK_LOG_ERROR, "Error when adding attribute '%s'", to_prp); break; } } } } if (rc == JK_FALSE) { jk_log(l, JK_LOG_ERROR, "Reference '%s' not found", from); } } else { JK_LOG_NULL_PARAMS(l); } return rc; }