svn commit: rev 65572 - in apr/apr/trunk: . tables

[th...@apache.org]

Author: thommay
Date: Sat Nov 13 18:33:07 2004
New Revision: 65572

Modified:
   apr/apr/trunk/CHANGES
   apr/apr/trunk/tables/apr_hash.c
Log:
Prevent unbounded memory use during repeated operations on a hash table.

The hash table was allocating new memory for each new insertion of an entry,
and not reclaiming it on deletions, so repetition of (insert, delete) caused
the memory use to keep growing.  This fix causes the memory freed by a deletion
to be reused by a subsequent insertion, so that the memory used by the hash
table is proportional to the maximum number of entries that it has ever held
simultaneously, rather than the number of insertions that have been performed.

* apr/tables/apr_hash.c:
  (apr_hash_t): Add new field "free", a free-list.
  (apr_hash_make, apr_hash_copy, apr_hash_merge): Initialise the free-list.
  (find_entry): Use an entry from the free-list if there is one.
  (apr_hash_set): Return a deleted entry to the free-list.


Modified: apr/apr/trunk/CHANGES
==============================================================================
--- apr/apr/trunk/CHANGES	(original)
+++ apr/apr/trunk/CHANGES	Sat Nov 13 18:33:07 2004
@@ -1,5 +1,8 @@
 Changes for APR 1.1 [Deferring these features when 1.0 is rolled out.]
 
+  *) Prevent unbounded memory use during repeated operations on a hash table.
+     [Julian Foad <julianfoad btopenworld.com>
+
   *) Moved repository to SVN
      [Hackathon]
 

Modified: apr/apr/trunk/tables/apr_hash.c
==============================================================================
--- apr/apr/trunk/tables/apr_hash.c	(original)
+++ apr/apr/trunk/tables/apr_hash.c	Sat Nov 13 18:33:07 2004
@@ -73,6 +73,7 @@
     apr_hash_index_t     iterator;  /* For apr_hash_first(NULL, ...) */
     unsigned int         count, max;
     apr_hashfunc_t       hash_func;
+    apr_hash_entry_t    *free;  /* List of recycled entries */
 };
 
 #define INITIAL_MAX 15 /* tunable == 2^n - 1 */
@@ -92,6 +93,7 @@
     apr_hash_t *ht;
     ht = apr_palloc(pool, sizeof(apr_hash_t));
     ht->pool = pool;
+    ht->free = NULL;
     ht->count = 0;
     ht->max = INITIAL_MAX;
     ht->array = alloc_array(ht, ht->max);
@@ -264,7 +266,10 @@
         return hep;
 
     /* add a new entry for non-NULL values */
-    he = apr_palloc(ht->pool, sizeof(*he));
+    if (he = ht->free)
+        ht->free = he->next;
+    else
+        he = apr_palloc(ht->pool, sizeof(*he));
     he->next = NULL;
     he->hash = hash;
     he->key  = key;
@@ -286,6 +291,7 @@
                     sizeof(*ht->array) * (orig->max + 1) +
                     sizeof(apr_hash_entry_t) * orig->count);
     ht->pool = pool;
+    ht->free = NULL;
     ht->count = orig->count;
     ht->max = orig->max;
     ht->hash_func = orig->hash_func;
@@ -333,7 +339,10 @@
     if (*hep) {
         if (!val) {
             /* delete entry */
+            apr_hash_entry_t *old = *hep;
             *hep = (*hep)->next;
+            old->next = ht->free;
+            ht->free = old;
             --ht->count;
         }
         else {
@@ -396,6 +405,7 @@
 
     res = apr_palloc(p, sizeof(apr_hash_t));
     res->pool = p;
+    res->free = NULL;
     res->hash_func = base->hash_func;
     res->count = base->count;
     res->max = (overlay->max > base->max) ? overlay->max : base->max;