Added a simple index to apr_table_t to reduce the best-case

execution time for table lookups from O(n) to O(1).

The worst-case time remains O(n), but in httpd benchmarking
this indexing reduces the mean execution time of apr_table_get()
by 40% and apr_table_unset() by 60%.

The indexing will make it possible to speed up apr_table_vdo()
and apr_table_overlap() in the future, but I haven't changed
those yet.


git-svn-id: http://svn.apache.org/repos/asf/apr/apr/trunk@63721 13f79535-47bb-0310-9956-ffa450edef68

1 files changed, 238 insertions, 45 deletions

diff --git a/tables/apr_tables.c b/tables/apr_tables.c
index 6601a9168..12a5ebe8c 100644
--- a/tables/apr_tables.c
+++ b/tables/apr_tables.c
@@ -313,6 +313,12 @@ APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
 #define CASE_MASK 0xdfdfdfdf
 #endif
 
+#define TABLE_HASH_SIZE 32
+#define TABLE_INDEX_MASK 0x1f
+#define TABLE_HASH(key)  (TABLE_INDEX_MASK & *(unsigned char *)(key))
+#define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i)))
+#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (i)))
+
 /* Compute the "checksum" for a key, consisting of the first
  * 4 bytes, normalized for case-insensitivity and packed into
  * an int...this checksum allows us to do a single integer
@@ -355,6 +361,21 @@ struct apr_table_t {
     /** Who created the array. */
     void *creator;
 #endif
+    /* An index to speed up table lookups.  The way this works is:
+     *   - Take the requested key and compute its checksum
+     *   - Hash the checksum into the index:
+     *     - index_first[TABLE_HASH(checksum)] is the offset within
+     *       the table of the first entry with that key checksum
+     *     - index_last[TABLE_HASH(checksum)] is the offset within
+     *       the table of the first entry with that key checksum
+     *   - If (and only if) there is no entry in the table whose
+     *     checksum hashes to index element i, then the i'th bit
+     *     of index_initialized will be zero.  (Check this before
+     *     trying to use index_first[i] or index_last[i]!)
+     */
+    apr_uint32_t index_initialized;
+    int index_first[TABLE_HASH_SIZE];
+    int index_last[TABLE_HASH_SIZE];
 };
 
 /*
@@ -391,6 +412,7 @@ APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
 #ifdef MAKE_TABLE_PROFILE
     t->creator = __builtin_return_address(0);
 #endif
+    t->index_initialized = 0;
     return t;
 }
 
@@ -410,26 +432,55 @@ APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)
     make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
     memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
     new->a.nelts = t->a.nelts;
+    memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
+    memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
+    new->index_initialized = t->index_initialized;
     return new;
 }
 
+static void table_reindex(apr_table_t *t)
+{
+    int i;
+    int hash;
+    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
+
+    t->index_initialized = 0;
+    for (i = 0; i < t->a.nelts; i++, next_elt++) {
+        hash = TABLE_HASH(next_elt->key);
+        t->index_last[hash] = i;
+        if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+            t->index_first[hash] = i;
+            TABLE_SET_INDEX_INITIALIZED(t, hash);
+        }
+    }
+}
+
 APR_DECLARE(void) apr_table_clear(apr_table_t *t)
 {
     t->a.nelts = 0;
+    t->index_initialized = 0;
 }
 
 APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
 {
-    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
-    apr_table_entry_t *end_elt = next_elt + t->a.nelts;
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
     apr_uint32_t checksum;
+    int hash;
 
     if (key == NULL) {
 	return NULL;
     }
 
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        return NULL;
+    }
     COMPUTE_KEY_CHECKSUM(key, checksum);
-    for (; next_elt < end_elt; next_elt++) {
+    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
+    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
+
+    for (; next_elt <= end_elt; next_elt++) {
 	if ((checksum == next_elt->key_checksum) &&
             !strcasecmp(next_elt->key, key)) {
 	    return next_elt->val;
@@ -440,21 +491,36 @@ APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
 }
 
 APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
-			       const char *val)
+                                const char *val)
 {
-    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
-    apr_table_entry_t *end_elt = next_elt + t->a.nelts;
-    apr_table_entry_t *dst_elt;
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
     apr_uint32_t checksum;
+    int hash;
 
     COMPUTE_KEY_CHECKSUM(key, checksum);
-    for (; next_elt < end_elt; next_elt++) {
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
+    }
+    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
+    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
+
+    for (; next_elt <= end_elt; next_elt++) {
 	if ((checksum == next_elt->key_checksum) &&
             !strcasecmp(next_elt->key, key)) {
+
+            /* Found an existing entry with the same key, so overwrite it */
+
+            int must_reindex = 0;
+            apr_table_entry_t *dst_elt = NULL;
+
             next_elt->val = apr_pstrdup(t->a.pool, val);
-            /* remove any other instances of this key */
-            dst_elt = NULL;
-            for (next_elt++; next_elt < end_elt; next_elt++) {
+
+            /* Remove any other instances of this key */
+            for (next_elt++; next_elt <= end_elt; next_elt++) {
                 if ((checksum == next_elt->key_checksum) &&
                     !strcasecmp(next_elt->key, key)) {
                     t->a.nelts--;
@@ -464,13 +530,32 @@ APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
                 }
                 else if (dst_elt) {
                     *dst_elt++ = *next_elt;
+                    must_reindex = 1;
                 }
+            }
 
+            /* If we've removed anything, shift over the remainder
+             * of the table (note that the previous loop didn't
+             * run to the end of the table, just to the last match
+             * for the index)
+             */
+            if (dst_elt) {
+                apr_table_entry_t *table_end =
+                    ((apr_table_entry_t *) t->a.elts) + t->a.nelts;
+                for (; next_elt < table_end; next_elt++) {
+                    *dst_elt++ = *next_elt;
+                }
+                must_reindex = 1;
+            }
+            if (must_reindex) {
+                table_reindex(t);
             }
             return;
         }
     }
 
+add_new_elt:
+    t->index_last[hash] = t->a.nelts;
     next_elt = (apr_table_entry_t *) table_push(t);
     next_elt->key = apr_pstrdup(t->a.pool, key);
     next_elt->val = apr_pstrdup(t->a.pool, val);
@@ -478,21 +563,36 @@ APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
 }
 
 APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
-				const char *val)
+                                 const char *val)
 {
-    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
-    apr_table_entry_t *end_elt = next_elt + t->a.nelts;
-    apr_table_entry_t *dst_elt;
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
     apr_uint32_t checksum;
+    int hash;
 
     COMPUTE_KEY_CHECKSUM(key, checksum);
-    for (; next_elt < end_elt; next_elt++) {
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
+    }
+    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
+    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
+
+    for (; next_elt <= end_elt; next_elt++) {
 	if ((checksum == next_elt->key_checksum) &&
             !strcasecmp(next_elt->key, key)) {
+
+            /* Found an existing entry with the same key, so overwrite it */
+
+            int must_reindex = 0;
+            apr_table_entry_t *dst_elt = NULL;
+
             next_elt->val = (char *)val;
-            /* remove any other instances of this key */
-            dst_elt = NULL;
-            for (next_elt++; next_elt < end_elt; next_elt++) {
+
+            /* Remove any other instances of this key */
+            for (next_elt++; next_elt <= end_elt; next_elt++) {
                 if ((checksum == next_elt->key_checksum) &&
                     !strcasecmp(next_elt->key, key)) {
                     t->a.nelts--;
@@ -502,13 +602,32 @@ APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
                 }
                 else if (dst_elt) {
                     *dst_elt++ = *next_elt;
+                    must_reindex = 1;
                 }
+            }
 
+            /* If we've removed anything, shift over the remainder
+             * of the table (note that the previous loop didn't
+             * run to the end of the table, just to the last match
+             * for the index)
+             */
+            if (dst_elt) {
+                apr_table_entry_t *table_end =
+                    ((apr_table_entry_t *) t->a.elts) + t->a.nelts;
+                for (; next_elt < table_end; next_elt++) {
+                    *dst_elt++ = *next_elt;
+                }
+                must_reindex = 1;
+            }
+            if (must_reindex) {
+                table_reindex(t);
             }
             return;
         }
     }
 
+add_new_elt:
+    t->index_last[hash] = t->a.nelts;
     next_elt = (apr_table_entry_t *) table_push(t);
     next_elt->key = (char *)key;
     next_elt->val = (char *)val;
@@ -517,18 +636,33 @@ APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
 
 APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
 {
-    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
+    apr_table_entry_t *next_elt;
     apr_table_entry_t *end_elt = next_elt + t->a.nelts;
     apr_table_entry_t *dst_elt;
     apr_uint32_t checksum;
+    int hash;
+    int must_reindex;
 
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        return;
+    }
     COMPUTE_KEY_CHECKSUM(key, checksum);
-    for (; next_elt < end_elt; next_elt++) {
+    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
+    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
+    must_reindex = 0;
+    for (; next_elt <= end_elt; next_elt++) {
 	if ((checksum == next_elt->key_checksum) &&
             !strcasecmp(next_elt->key, key)) {
+
+            /* Found a match: remove this entry, plus any additional
+             * matches for the same key that might follow
+             */
+            apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
+                t->a.nelts;
             t->a.nelts--;
             dst_elt = next_elt;
-            for (next_elt++; next_elt < end_elt; next_elt++) {
+            for (next_elt++; next_elt <= end_elt; next_elt++) {
                 if ((checksum == next_elt->key_checksum) &&
                     !strcasecmp(next_elt->key, key)) {
                     t->a.nelts--;
@@ -537,38 +671,67 @@ APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
                     *dst_elt++ = *next_elt;
                 }
             }
+
+            /* Shift over the remainder of the table (note that
+             * the previous loop didn't run to the end of the table,
+             * just to the last match for the index)
+             */
+            for (; next_elt < table_end; next_elt++) {
+                *dst_elt++ = *next_elt;
+            }
+            must_reindex = 1;
             break;
         }
     }
+    if (must_reindex) {
+        table_reindex(t);
+    }
 }
 
 APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
 				 const char *val)
 {
-    apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
-    int i;
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
     apr_uint32_t checksum;
+    int hash;
 
     COMPUTE_KEY_CHECKSUM(key, checksum);
-    for (i = 0; i < t->a.nelts; ++i) {
-	if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) {
-	    elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL);
-	    return;
-	}
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
     }
+    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
+    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
 
-    elts = (apr_table_entry_t *) table_push(t);
-    elts->key = apr_pstrdup(t->a.pool, key);
-    elts->val = apr_pstrdup(t->a.pool, val);
-    elts->key_checksum = checksum;
+    for (; next_elt <= end_elt; next_elt++) {
+	if ((checksum == next_elt->key_checksum) &&
+            !strcasecmp(next_elt->key, key)) {
+
+            /* Found an existing entry with the same key, so merge with it */
+	    next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
+                                        val, NULL);
+            return;
+        }
+    }
+
+add_new_elt:
+    t->index_last[hash] = t->a.nelts;
+    next_elt = (apr_table_entry_t *) table_push(t);
+    next_elt->key = apr_pstrdup(t->a.pool, key);
+    next_elt->val = apr_pstrdup(t->a.pool, val);
+    next_elt->key_checksum = checksum;
 }
 
 APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
 				  const char *val)
 {
-    apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
-    int i;
+    apr_table_entry_t *next_elt;
+    apr_table_entry_t *end_elt;
     apr_uint32_t checksum;
+    int hash;
 
 #ifdef POOL_DEBUG
     {
@@ -584,17 +747,32 @@ APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
 #endif
 
     COMPUTE_KEY_CHECKSUM(key, checksum);
-    for (i = 0; i < t->a.nelts; ++i) {
-	if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) {
-	    elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL);
-	    return;
-	}
+    hash = TABLE_HASH(key);
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+        goto add_new_elt;
     }
+    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
+    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
 
-    elts = (apr_table_entry_t *) table_push(t);
-    elts->key = (char *)key;
-    elts->val = (char *)val;
-    elts->key_checksum = checksum;
+    for (; next_elt <= end_elt; next_elt++) {
+	if ((checksum == next_elt->key_checksum) &&
+            !strcasecmp(next_elt->key, key)) {
+
+            /* Found an existing entry with the same key, so merge with it */
+	    next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
+                                        val, NULL);
+            return;
+        }
+    }
+
+add_new_elt:
+    t->index_last[hash] = t->a.nelts;
+    next_elt = (apr_table_entry_t *) table_push(t);
+    next_elt->key = (char *)key;
+    next_elt->val = (char *)val;
+    next_elt->key_checksum = checksum;
 }
 
 APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
@@ -602,7 +780,14 @@ APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
 {
     apr_table_entry_t *elts;
     apr_uint32_t checksum;
+    int hash;
 
+    hash = TABLE_HASH(key);
+    t->index_last[hash] = t->a.nelts;
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+    }
     COMPUTE_KEY_CHECKSUM(key, checksum);
     elts = (apr_table_entry_t *) table_push(t);
     elts->key = apr_pstrdup(t->a.pool, key);
@@ -615,6 +800,7 @@ APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
 {
     apr_table_entry_t *elts;
     apr_uint32_t checksum;
+    int hash;
 
 #ifdef POOL_DEBUG
     {
@@ -629,6 +815,12 @@ APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
     }
 #endif
 
+    hash = TABLE_HASH(key);
+    t->index_last[hash] = t->a.nelts;
+    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
+        t->index_first[hash] = t->a.nelts;
+        TABLE_SET_INDEX_INITIALIZED(t, hash);
+    }
     COMPUTE_KEY_CHECKSUM(key, checksum);
     elts = (apr_table_entry_t *) table_push(t);
     elts->key = (char *)key;
@@ -664,7 +856,7 @@ APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,
     res->a.pool = p;
     copy_array_hdr_core(&res->a, &overlay->a);
     apr_array_cat(&res->a, &base->a);
-
+    table_reindex(res);
     return res;
 }
 
@@ -1108,5 +1300,6 @@ APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
             elt->key_checksum = cat_keys[i].elt->key_checksum;
         }
     }
+    table_reindex(a);
 }