summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGlenn Strauss <gstrauss@gluelogic.com>2019-10-15 22:45:30 -0400
committerGlenn Strauss <gstrauss@gluelogic.com>2019-10-15 22:54:45 -0400
commite38e145bea99a7f30c96a7061e1b6f076cec90ff (patch)
treedd4f242de437a37c6653318e4468563ee2f7bcba
parent7fe60a080df476d093ff9727f4cd073f886c947c (diff)
downloadlighttpd1.4-e38e145bea99a7f30c96a7061e1b6f076cec90ff.tar.gz
lighttpd1.4-e38e145bea99a7f30c96a7061e1b6f076cec90ff.zip
[core] array a->sorted[] as ptrs rather than pos
While slightly more memory use in 64-bit (though same memory use as prior versions of lighttpd), avoids bouncing through second array when searching in sorted list. Most use of arrays in lighttpd is to build a list once, and elements are not removed from the list.
-rw-r--r--src/array.c55
-rw-r--r--src/array.h5
-rw-r--r--src/mod_alias.c10
-rw-r--r--src/mod_ssi.c4
-rw-r--r--src/mod_status.c6
5 files changed, 37 insertions, 43 deletions
diff --git a/src/array.c b/src/array.c
index 8739e9d6..de9f93af 100644
--- a/src/array.c
+++ b/src/array.c
@@ -88,7 +88,7 @@ data_unset *array_pop(array * const a) {
a->used --;
du = a->data[a->used];
- force_assert(a->sorted[a->used] == a->used); /* only works on "simple" lists */
+ force_assert(a->sorted[a->used] == du); /* only works on "simple" lists */
a->data[a->used] = NULL;
return du;
@@ -117,7 +117,7 @@ static int array_keycmp(const char * const a, const size_t alen, const char * co
return alen < blen ? -1 : alen > blen ? 1 : array_caseless_compare(a, b, blen);
}
-/* returns pos into a->sorted[] which contains index to data in a->data[]
+/* returns pos into a->sorted[] which contains copy of data (ptr) in a->data[]
* if pos >= 0, or returns -pos-1 if that is the position-1 in a->sorted[]
* where the key needs to be inserted (-1 to avoid -0)
*/
@@ -130,7 +130,7 @@ static int32_t array_get_index(const array * const a, const char * const k, cons
uint32_t lower = 0, upper = a->used;
while (lower != upper) {
uint32_t probe = (lower + upper) / 2;
- const buffer * const b = &a->data[a->sorted[probe]]->key;
+ const buffer * const b = &a->sorted[probe]->key;
/* key is non-empty (0==b->used), though possibly blank (1==b->used),
* if inserted into key-value array */
/*force_assert(b && b->used);*/
@@ -150,42 +150,34 @@ static int32_t array_get_index(const array * const a, const char * const k, cons
__attribute_hot__
data_unset *array_get_element_klen(const array * const a, const char *key, const size_t klen) {
const int32_t ipos = array_get_index(a, key, klen);
- return ipos >= 0 ? a->data[a->sorted[ipos]] : NULL;
+ return ipos >= 0 ? a->sorted[ipos] : NULL;
}
/* non-const (data_config *) for configparser.y (not array_get_element_klen())*/
data_unset *array_get_data_unset(const array * const a, const char *key, const size_t klen) {
const int32_t ipos = array_get_index(a, key, klen);
- return ipos >= 0 ? a->data[a->sorted[ipos]] : NULL;
+ return ipos >= 0 ? a->sorted[ipos] : NULL;
}
data_unset *array_extract_element_klen(array * const a, const char *key, const size_t klen) {
const int32_t ipos = array_get_index(a, key, klen);
if (ipos < 0) return NULL;
+ /* remove entry from a->sorted: move everything after pos one step left */
+ data_unset * const entry = a->sorted[ipos];
const uint32_t last_ndx = --a->used;
- const uint32_t ndx = a->sorted[ipos], pos = (uint32_t)ipos;
- data_unset * const entry = a->data[ndx];
-
- /* now we need to swap it with the last element (if it isn't already the last element) */
- if (ndx != last_ndx) {
- /* to swap we also need to modify the index in a->sorted - find pos of last_elem there */
- int32_t last_elem_pos = array_get_index(a, CONST_BUF_LEN(&a->data[last_ndx]->key));
- /* last element must be present at the expected position */
- force_assert(last_ndx == a->sorted[last_elem_pos]);
-
- /* move entry from last_ndx to ndx */
- a->data[ndx] = a->data[last_ndx];
-
- /* fix index entry for moved entry */
- a->sorted[last_elem_pos] = ndx;
- }
-
- /* remove entry in a->sorted: move everything after pos one step to the left */
- if (pos != last_ndx) {
- memmove(a->sorted + pos, a->sorted + pos + 1, (last_ndx - pos) * sizeof(*a->sorted));
- }
+ if (last_ndx != (uint32_t)ipos) {
+ data_unset ** const d = a->sorted + ipos;
+ memmove(d, d+1, (last_ndx - (uint32_t)ipos) * sizeof(*d));
+ }
+ if (entry != a->data[last_ndx]) {
+ /* walk a->data[] to find data ptr */
+ /* (not checking (ndx <= last_ndx) since entry must be in a->data[]) */
+ uint32_t ndx = 0;
+ while (entry != a->data[ndx]) ++ndx;
+ a->data[ndx] = a->data[last_ndx]; /* swap with last element */
+ }
a->data[last_ndx] = NULL;
return entry;
}
@@ -233,9 +225,10 @@ static void array_insert_data_at_pos(array * const a, data_unset * const entry,
/* move everything one step to the right */
if (pos != ndx) {
- memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
+ data_unset ** const d = a->sorted + pos;
+ memmove(d+1, d, (ndx - pos) * sizeof(*a->sorted));
}
- a->sorted[pos] = ndx;
+ a->sorted[pos] = entry;
if (prev) prev->fn->free(prev); /* free prior data, if any, from slot */
}
@@ -260,7 +253,7 @@ static data_string * array_insert_string_at_pos(array * const a, const uint32_t
int * array_get_int_ptr(array * const a, const char * const k, const size_t klen) {
int32_t ipos = array_get_index(a, k, klen);
- if (ipos >= 0) return &((data_integer *)a->data[a->sorted[ipos]])->value;
+ if (ipos >= 0) return &((data_integer *)a->sorted[ipos])->value;
data_integer * const di =array_insert_integer_at_pos(a,(uint32_t)(-ipos-1));
buffer_copy_string_len(&di->key, k, klen);
@@ -270,7 +263,7 @@ int * array_get_int_ptr(array * const a, const char * const k, const size_t klen
buffer * array_get_buf_ptr(array * const a, const char * const k, const size_t klen) {
int32_t ipos = array_get_index(a, k, klen);
- if (ipos >= 0) return &((data_string *)a->data[a->sorted[ipos]])->value;
+ if (ipos >= 0) return &((data_string *)a->sorted[ipos])->value;
data_string * const ds = array_insert_string_at_pos(a, (uint32_t)(-ipos-1));
buffer_copy_string_len(&ds->key, k, klen);
@@ -297,7 +290,7 @@ static data_unset **array_find_or_insert(array * const a, data_unset * const ent
/* try to find the entry */
const int32_t ipos = array_get_index(a, CONST_BUF_LEN(&entry->key));
- if (ipos >= 0) return &a->data[a->sorted[ipos]];
+ if (ipos >= 0) return &a->sorted[ipos];
array_insert_data_at_pos(a, entry, (uint32_t)(-ipos - 1));
return NULL;
diff --git a/src/array.h b/src/array.h
index 47c9921c..31b50527 100644
--- a/src/array.h
+++ b/src/array.h
@@ -24,9 +24,8 @@ typedef struct data_unset {
} data_unset;
typedef struct {
- data_unset **data;
-
- uint32_t *sorted;
+ data_unset **data;
+ data_unset **sorted;
uint32_t used; /* <= INT32_MAX */
uint32_t size;
diff --git a/src/mod_alias.c b/src/mod_alias.c
index 7b817be4..55b591ca 100644
--- a/src/mod_alias.c
+++ b/src/mod_alias.c
@@ -99,9 +99,9 @@ SETDEFAULTS_FUNC(mod_alias_set_defaults) {
size_t j, k;
for (j = 0; j < a->used; j ++) {
- const buffer *prefix = &a->data[a->sorted[j]]->key;
+ const buffer *prefix = &a->sorted[j]->key;
for (k = j + 1; k < a->used; k ++) {
- const buffer *key = &a->data[a->sorted[k]]->key;
+ const buffer *key = &a->sorted[k]->key;
if (buffer_string_length(key) < buffer_string_length(prefix)) {
break;
@@ -110,7 +110,11 @@ SETDEFAULTS_FUNC(mod_alias_set_defaults) {
break;
}
/* ok, they have same prefix. check position */
- if (a->sorted[j] < a->sorted[k]) {
+ const data_unset *dj = a->sorted[j];
+ const data_unset *dk = a->sorted[k];
+ const data_unset **data = (const data_unset **)a->data;
+ while (*data != dj && *data != dk) ++data;
+ if (*data == dj) {
log_error_write(srv, __FILE__, __LINE__, "SBSBS",
"url.alias: `", key, "' will never match as `", prefix, "' matched first");
return HANDLER_ERROR;
diff --git a/src/mod_ssi.c b/src/mod_ssi.c
index c36f8f2c..4f9dfa0b 100644
--- a/src/mod_ssi.c
+++ b/src/mod_ssi.c
@@ -742,7 +742,7 @@ static int process_ssi_stmt(server *srv, connection *con, handler_ctx *p, const
b = srv->tmp_buf;
buffer_clear(b);
for (i = 0; i < p->ssi_vars->used; i++) {
- data_string *ds = (data_string *)p->ssi_vars->data[p->ssi_vars->sorted[i]];
+ data_string *ds = (data_string *)p->ssi_vars->sorted[i];
buffer_append_string_buffer(b, &ds->key);
buffer_append_string_len(b, CONST_STR_LEN("="));
@@ -750,7 +750,7 @@ static int process_ssi_stmt(server *srv, connection *con, handler_ctx *p, const
buffer_append_string_len(b, CONST_STR_LEN("\n"));
}
for (i = 0; i < p->ssi_cgi_env->used; i++) {
- data_string *ds = (data_string *)p->ssi_cgi_env->data[p->ssi_cgi_env->sorted[i]];
+ data_string *ds = (data_string *)p->ssi_cgi_env->sorted[i];
buffer_append_string_buffer(b, &ds->key);
buffer_append_string_len(b, CONST_STR_LEN("="));
diff --git a/src/mod_status.c b/src/mod_status.c
index c762442e..a89ab3bf 100644
--- a/src/mod_status.c
+++ b/src/mod_status.c
@@ -753,11 +753,9 @@ static handler_t mod_status_handle_server_statistics(server *srv, connection *co
b = chunkqueue_append_buffer_open(con->write_queue);
for (i = 0; i < st->used; i++) {
- size_t ndx = st->sorted[i];
-
- buffer_append_string_buffer(b, &st->data[ndx]->key);
+ buffer_append_string_buffer(b, &st->sorted[i]->key);
buffer_append_string_len(b, CONST_STR_LEN(": "));
- buffer_append_int(b, ((data_integer *)(st->data[ndx]))->value);
+ buffer_append_int(b, ((data_integer *)st->sorted[i])->value);
buffer_append_string_len(b, CONST_STR_LEN("\n"));
}
chunkqueue_append_buffer_commit(con->write_queue);