Missing files (Re: Mega-patch for 2.2.Stable3 + fastest redirector in town)

Turns out that I forgot to include the (modified) heap.c and heap.h files.
You need those to compile the lot (sorry for the confusion).
Here they are in patch format:
-------------------cut here------------------------
diff -U 2 -b -B -p -r -d --horizon-lines=2 -X /usr/local/etc/xdiff squid-2.2.STABLE3/include/heap.h squid-B2/include/heap.h
--- squid-2.2.STABLE3/include/heap.h Wed Jun 23 20:20:48 1999
+++ squid-B2/include/heap.h Sun Jun 20 13:06:40 1999
@@ -0,0 +1,153 @@
+/****************************************************************************
+ * Heap data structure. Used to store objects for cache replacement. The
+ * heap is implemented as a contiguous array in memory. Heap sort and heap
+ * update are done in-place. The heap is ordered with the smallest value at
+ * the top of the heap (as in the smallest object key value). Child nodes
+ * are larger than their parent.
+ ****************************************************************************/
+
+#ifndef _heap_h_INCLUDED
+#define _heap_h_INCLUDED
+
+/*
+ * Typdefs for non-synchronized heap implementation.
+ */
+typedef unsigned long mutex_t;
+# define mutex_lock(m) (void)0
+# define mutex_unlock(m) (void)0
+# define mutex_trylock(m) (void)0
+# define mutex_init(m) ((m)=123456)
+
+/*
+ * Function for generating heap keys. The first argument will typically be
+ * a dws_md_p passed in as a void *. Should find a way to get type safety
+ * without having heap know all about metadata objects... The second arg is
+ * the current aging factor for the heap.
+ */
+# define _HEAPTYPE void *
+# define _HEAPKEY double
+# define _HEAPKEYSTORED float /* no need to store doubles */
+
+typedef _HEAPKEY (*key_func) (_HEAPTYPE, _HEAPKEY);
+
+
+/*
+ * Heap node. Has a key value generated by a key_func, id (array index) so
+ * it can be quickly found in its heap, and a pointer to a data object that
+ * key_func can generate a key from.
+ */
+typedef struct _heap_node {
+ _HEAPKEYSTORED key;
+ unsigned long id;
+ _HEAPTYPE data;
+} heap_node, *heap_node_p;
+
+
+/*
+ * Heap object. Holds an array of heap_node objects along with a heap size
+ * (array length), the index of the last heap element, and a key generation
+ * function. Also stores aging factor for this heap.
+ */
+typedef struct _heap {
+ mutex_t lock;
+ unsigned long size;
+ unsigned long last;
+ key_func gen_key; /* key generator for heap */
+ _HEAPKEY age; /* aging factor for heap */
+ heap_node ** nodes;
+} heap, *heap_p;
+
+/****************************************************************************
+ * Public functions
+ ****************************************************************************/
+
+/*
+ * Create and initialize a new heap.
+ */
+extern heap_p new_heap(int init_size, key_func gen_key);
+
+/*
+ * Delete a heap and clean up its memory. Does not delete what the heap
+ * nodes are pointing to!
+ */
+extern void delete_heap(heap_p);
+
+/*
+ * Insert a new node into a heap, returning a pointer to it. The heap_node
+ * object returned is used to update or delete a heap object. Nothing else
+ * should be done with this data structure (especially modifying it!) The
+ * heap does not assume ownership of the data passed to it.
+ */
+extern heap_node_p heap_insert(heap_p, _HEAPTYPE dat);
+
+/*
+ * Delete a node out of a heap. Returns the heap data from the deleted
+ * node. The caller is responsible for freeing this data.
+ */
+extern _HEAPTYPE heap_delete(heap_p, heap_node_p elm);
+
+/*
+ * The semantics of this routine is the same as the followings:
+ * heap_delete(hp, elm);
+ * heap_insert(hp, dat);
+ * Returns the old data object from elm (the one being replaced). The
+ * caller must free this as necessary.
+ */
+extern _HEAPTYPE heap_update(heap_p, heap_node* elm, _HEAPTYPE dat);
+
+/*
+ * Generate a heap key for a given data object. Alternative macro form:
+ */
+#ifdef MACRO_DEBUG
+extern _HEAPKEY heap_gen_key(heap_p hp, _HEAPTYPE dat);
+#else
+# define heap_gen_key(hp,md) ((hp)->gen_key((md),(hp)->age))
+#endif /* MACRO_DEBUG */
+
+
+/*
+ * Extract the minimum (root) element and maintain the heap property.
+ * Returns the data pointed to by the root node, which the caller must
+ * free as necessary.
+ */
+extern _HEAPTYPE heap_extractmin(heap_p);
+
+/*
+ * Extract the last leaf node (does not change the heap property).
+ * Returns the data that had been in the heap which the caller must free if
+ * necessary. Note that the last node is guaranteed to be less than its
+ * parent, but may not be less than any of the other (leaf or parent) notes
+ * in the tree. This operation is fast but imprecise.
+ */
+extern _HEAPTYPE heap_extractlast(heap_p hp);
+
+/*
+ * Get the root key, the nth key, the root (smallest) element, or the nth
+ * element. None of these operations modify the heap.
+ */
+extern _HEAPKEY heap_peepminkey(heap_p);
+extern _HEAPKEY heap_peepkey(heap_p, int n);
+
+extern _HEAPTYPE heap_peepmin(heap_p);
+extern _HEAPTYPE heap_peep(heap_p, int n);
+
+/*
+ * Is the heap empty? How many nodes (data objects) are in it?
+ */
+#ifdef MACRO_DEBUG
+extern int heap_empty(heap_p);
+extern int heap_nodes(heap_p);
+#else /* MACRO_DEBUG */
+# define heap_nodes(heap) ((heap)->last)
+# define heap_empty(heap) (((heap)->last <= 0) ? 1 : 0)
+#endif /* MACRO_DEBUG */
+
+/*
+ * Print the heap or a node in the heap.
+ */
+extern void heap_print(heap_p);
+extern void heap_printnode(char *msg, heap_node_p elm);
+
+extern int verify_heap_property(heap_p);
+
+#endif /* _heap_h_INCLUDED */
diff -U 2 -b -B -p -r -d --horizon-lines=2 -X /usr/local/etc/xdiff squid-2.2.STABLE3/lib/heap.c squid-B2/lib/heap.c
--- squid-2.2.STABLE3/lib/heap.c Wed Jun 23 20:20:44 1999
+++ squid-B2/lib/heap.c Sun Jun 20 11:47:29 1999
@@ -0,0 +1,607 @@
+#define HPL_REPL 1
+/****************************************************************************
+ * Heap implementation
+ ****************************************************************************/
+
+#include <stdlib.h>
+#include "malloc.h"
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "heap.h"
+
+/*
+ * Private function prototypes.
+ */
+static void _heap_ify_up(heap_p hp, heap_node_p elm);
+static void _heap_ify_down(heap_p hp, heap_node_p elm);
+static int _heap_should_grow(heap_p hp);
+static void _heap_grow(heap_p hp);
+static void _heap_swap_element(heap_p hp, heap_node_p elm1, heap_node_p elm2);
+static unsigned _heap_node_exist(heap_p hp, int id);
+
+extern void*alloc_heap_node(void);
+extern void memFree_heap_node(void *);
+
+#ifdef HEAP_DEBUG
+void _heap_print_tree(heap_p hp, heap_node_p node);
+#endif /* HEAP_DEBUG */
+
+#define Left(x) (2 * (x) + 1)
+#define Right(x) (2 * (x) + 2)
+#define Parent(x) ((unsigned)((x)-1)/2)
+
+#define Threshold 10000
+#define NormalRate 2
+#define SlowRate 1.5
+#define MinSize 32
+
+/****************************************************************************
+ * Public functions
+ ****************************************************************************/
+
+/*
+ * Return a newly created heap. INITSIZE is the initial size of the heap.
+ */
+heap_p
+new_heap(int initSize, key_func gen_key)
+{
+ heap_p hp = (heap_p) malloc(sizeof(heap));
+ assert(hp != NULL);
+
+ if (initSize <= 0)
+ initSize = MinSize;
+
+ hp->nodes = (heap_node_p *)calloc(initSize, sizeof(heap_node_p));
+ assert(hp->nodes != NULL);
+
+ hp->size = initSize;
+ hp->last = 0;
+ hp->gen_key = gen_key;
+ hp->age = 0;
+
+ return hp;
+}
+
+
+/*
+ * Free memory used by a heap. Does not free the metadata pointed to by the
+ * heap nodes, only the heap's internal memory.
+ */
+void
+delete_heap(heap_p hp)
+{
+ int i;
+ assert(hp);
+ for (i = 0; i < hp->last; i++) {
+ memFree_heap_node(hp->nodes[i]);
+ }
+ free(hp->nodes);
+ free(hp);
+}
+
+/*
+ * True if a node with ID exists in HP.
+ */
+static unsigned
+_heap_node_exist(heap_p hp, int id)
+{
+ if ((id >= hp->last) || (id < 0) || (hp->nodes[id] == NULL) ||
+ hp->nodes[id]->id != id)
+ return 0;
+ return 1;
+}
+
+/*
+ * Insert DAT based on KY into HP maintaining the heap property. Return the
+ * newly inserted heap node. The fields of ELM other than ID are never
+ * changed until ELM is deleted from HP, i.e. caller can assume that the
+ * heap node always exist at the same place in memory unless heap_delete or
+ * heap_extractmin is called on that node. This function exposes the heap's
+ * internal data structure to the caller. This is required in order to do
+ * O(lgN) deletion.
+ */
+heap_node_p
+heap_insert(heap_p hp, void * dat)
+{
+ heap_node* elm = (heap_node*)alloc_heap_node();
+ checkheap(0);
+
+ elm->key = heap_gen_key(hp, dat);
+ elm->data = dat;
+
+ if (_heap_should_grow(hp))
+ _heap_grow(hp);
+
+ hp->nodes[hp->last] = elm;
+ elm->id = hp->last;
+ hp->last += 1;
+
+ _heap_ify_up(hp, elm);
+
+ /*
+ * Set the pointer in the metadata to point to this heap node.
+ */
+ #ifdef HPL_REPL
+ /* The following must be done immediately upon return! */
+ #else /* HPL_REPL */
+ md_set_node(dat, elm);
+ #endif /* HPL_REPL */
+
+ checkheap(0);
+ return elm;
+}
+
+static
+void _heap_order(heap_p hp, heap_node_p elm)
+{
+ checkheap(0);
+ if (elm->id > 0 &&
+ elm->key < hp->nodes[Parent(elm->id)]->key)
+ _heap_ify_up(hp, elm); /* COOL! */
+ _heap_ify_down(hp, elm);
+ checkheap(0);
+}
+
+/*
+ * Delete ELM while maintaining the heap property. ELM may be modified.
+ * Assumes that ELM is not NULL and frees it. Returns the data pointed to
+ * in, which the caller must free if necessary.
+ */
+_HEAPTYPE
+heap_delete(heap_p hp, heap_node_p elm)
+{
+ heap_node_p lastNode;
+ _HEAPTYPE data = elm->data;
+ checkheap(0);
+
+ assert(_heap_node_exist(hp, hp->last-1));
+
+ if (elm->id != --hp->last) {
+ lastNode = hp->nodes[hp->last];
+ hp->nodes[elm->id] = lastNode;
+ lastNode->id = elm->id;
+
+ _heap_order(hp, lastNode);
+ }
+
+ memFree_heap_node(elm);
+
+ /*
+ * Remove the pointer back to the heap from the metadata.
+ * Then free the element that was just deleted.
+ */
+ #ifdef HPL_REPL
+ /* The following must be done immediately upon return! */
+ #else /* HPL_REPL */
+ md_set_node(data, NULL);
+ #endif /* HPL_REPL */
+
+ checkheap(0);
+ return data;
+}
+
+/*
+ * Delete the last element (leaf) out of the heap. Does not require a
+ * heapify operation.
+ */
+
+#ifndef heap_gen_key
+/*
+ * Function to generate keys. See macro definition in heap.h.
+ */
+_HEAPKEY
+heap_gen_key(heap_p hp, _HEAPTYPE dat)
+{
+ checkheap(0);
+ return hp->gen_key(dat, hp->age);
+}
+#endif /* heap_gen_key */
+
+
+/*
+ * Returns the data of the node with the largest KEY value and removes that
+ * node from the heap. Returns NULL if the heap was empty.
+ */
+_HEAPTYPE
+heap_extractmin(heap_p hp)
+{
+ checkheap(0);
+ if (hp->last <= 0)
+ return NULL;
+
+ return heap_delete(hp, hp->nodes[0]); /* Delete the root */
+}
+
+
+/*
+ * Remove the last node in HP. Frees the heap internal structure and
+ * returns the data pointes to by the last node.
+ */
+_HEAPTYPE
+heap_extractlast(heap_p hp)
+{
+ _HEAPTYPE data;
+ checkheap(0);
+ assert (_heap_node_exist(hp, hp->last-1));
+ data = hp->nodes[--hp->last]->data;
+ memFree_heap_node(hp->nodes[hp->last]);
+ checkheap(0);
+ return data;
+}
+
+
+/*
+ * The semantics of this routine is the same as the followings:
+ * heap_delete(hp, elm);
+ * heap_insert(hp, dat);
+ * Returns the old data object from elm (the one being replaced). The
+ * caller must free this as necessary.
+ */
+_HEAPTYPE
+heap_update(heap_p hp, heap_node* elm, void* dat)
+{
+ _HEAPTYPE old = elm->data;
+ _HEAPKEY ky = heap_gen_key(hp, dat);
+ assert (_heap_node_exist(hp, elm->id));
+ checkheap(0);
+
+ elm->key = ky;
+ elm->data = dat;
+
+ _heap_order(hp, elm);
+
+ checkheap(0);
+ return old;
+}
+
+
+/*
+ * A pointer to the root node's DATA.
+ */
+void*
+heap_peepmin(heap_p hp)
+{
+ checkheap(0);
+ assert(_heap_node_exist(hp, 0));
+ return hp->nodes[0]->data;
+}
+
+
+/*
+ * The KEY of the root node.
+ */
+_HEAPKEY
+heap_peepminkey(heap_p hp)
+{
+ assert(_heap_node_exist(hp, 0));
+ checkheap(0);
+ return hp->nodes[0]->key;
+}
+
+
+/*
+ * Same as heap_peep except that this return the KEY of the node.
+ * Only meant for iteration.
+ */
+_HEAPKEY
+heap_peepkey(heap_p hp, int n)
+{
+ assert(_heap_node_exist(hp, n));
+ checkheap(0);
+ return hp->nodes[n]->key;
+}
+
+
+/*
+ * A pointer to Nth node's DATA. The caller can iterate through HP by
+ * calling this routine. eg. Caller can execute the following code:
+ * for(i = 0; i < heap_nodes(hp); i++)
+ * data = heap_peep(hp, i);
+ */
+void*
+heap_peep(heap_p hp, int n)
+{
+ void* data;
+ assert(_heap_node_exist(hp, n));
+ data = hp->nodes[n]->data;
+ checkheap(0);
+ return data;
+}
+
+
+#ifndef heap_nodes
+/*
+ * Current number of nodes in HP.
+ */
+int
+heap_nodes(heap_p hp)
+{
+ return hp->last;
+}
+#endif /* heap_nodes */
+
+
+#ifndef heap_empty
+/*
+ * Determine if the heap is empty. Returns 1 if HP has no elements and 0
+ * otherwise.
+ */
+int
+heap_empty(heap_p hp)
+{
+ return (hp->last <= 0) ? 1 : 0;
+}
+#endif /* heap_empty */
+
+/****************** Private Functions *******************/
+
+/*
+ * Maintain the heap order property (parent is smaller than children) which
+ * may only be violated at ELM downwards. Assumes caller has locked the heap.
+ */
+static void
+_heap_ify_down(heap_p hp, heap_node_p elm)
+{
+ heap_node* kid;
+ int left, right;
+ for(;;) {
+ assert(_heap_node_exist(hp, elm->id));
+ left = Left(elm->id);
+ right = Right(elm->id);
+ if (hp->last <= left) // At the bottom of the heap (no child).
+ break;
+ else if (hp->last <= right) { // Only left child exists.
+ assert(_heap_node_exist(hp, left));
+ kid = hp->nodes[left];
+ } else {
+ assert(_heap_node_exist(hp, left));
+ assert(_heap_node_exist(hp, right));
+ if (hp->nodes[right]->key < hp->nodes[left]->key)
+ kid = hp->nodes[right];
+ else
+ kid = hp->nodes[left];
+ }
+ if (elm->key <= kid->key)
+ break;
+ _heap_swap_element(hp, kid, elm);
+ }
+}
+
+
+/*
+ * Maintain the heap property above ELM. Caller has locked the heap.
+ */
+static void
+_heap_ify_up(heap_p hp, heap_node_p elm)
+{
+ heap_node_p parentNode;
+ assert(_heap_node_exist(hp, elm->id));
+ while (elm->id > 0) {
+ assert(_heap_node_exist(hp, elm->id));
+ parentNode = hp->nodes[Parent(elm->id)];
+ assert(_heap_node_exist(hp, parentNode->id));
+ if (parentNode->key <= elm->key)
+ break;
+ _heap_swap_element(hp, parentNode, elm); /* Demote the parent. */
+ }
+}
+
+
+/*
+ * Swap the position of ELM1 and ELM2 in heap structure. Their IDs are also
+ * swapped.
+ */
+static void
+_heap_swap_element(heap_p hp, heap_node_p elm1, heap_node_p elm2)
+{
+ int elm1Id = elm1->id;
+ elm1->id = elm2->id;
+ elm2->id = elm1Id;
+ hp->nodes[elm1->id] = elm1;
+ hp->nodes[elm2->id] = elm2;
+}
+
+
+
+#ifdef NOTDEF
+/*
+ * Copy KEY and DATA fields of SRC to DEST. ID field is NOT copied.
+ */
+static void
+_heap_copy_element(heap_node_p src, heap_node_p dest)
+{
+ dest->key = src->key;
+ dest->data = src->data;
+}
+#endif /* NOTDEF */
+
+
+/*
+ * True if HP needs to be grown in size.
+ */
+static int
+_heap_should_grow(heap_p hp)
+{
+ if (hp->size <= hp->last)
+ return 1;
+ return 0;
+}
+
+
+/*
+ * Grow HP.
+ */
+static void
+_heap_grow(heap_p hp)
+{
+ int newSize;
+ //heap_node_p * newNodes;
+
+ if (hp->size > Threshold)
+ newSize = hp->size * SlowRate;
+ else
+ newSize = hp->size * NormalRate;
+
+ hp->nodes = (heap_node_p *)realloc(hp->nodes, newSize * sizeof(heap_node_p));
+ //for(i = 0; i < hp->size; i++)
+ //newNodes[i] = hp->nodes[i];
+ //free(hp->nodes);
+ //hp->nodes = newNodes;
+ hp->size = newSize;
+}
+
+
+/****************************************************************************
+ * Printing and debug functions
+ ****************************************************************************/
+
+/*
+ * Print the heap in element order, id..last.
+ */
+void
+heap_print_inorder(heap_p hp, int id)
+{
+ while (id < hp->last) {
+ printf("%d <- %d -> %d\tKey = %.04f\n", Parent(id), id, Left(id), hp->nodes[id]->key);
+ id++;
+ }
+}
+
+/*
+ * Returns 1 if HP maintians the heap property and 0 otherwise.
+ */
+int
+verify_heap_property(heap_p hp)
+{
+ int i = 0;
+ int correct = 1;
+ for(i = 0; i < hp->last / 2; i++) {
+ correct = 1;
+ if (_heap_node_exist(hp, Left(i)))
+ if (hp->nodes[i]->key > hp->nodes[Left(i)]->key)
+ correct = 0;
+ if (_heap_node_exist(hp, Right(i)))
+ if (hp->nodes[i]->key > hp->nodes[Right(i)]->key)
+ correct = 0;
+ if (!correct) {
+ printf("verifyHeap: violated at %d", i);
+ heap_print_inorder(hp, 0);
+ break;
+ }
+ }
+ return correct;
+}
+
+#ifdef MEASURE_HEAP_SKEW
+
+/****************************************************************************
+ * Heap skew computation
+ ****************************************************************************/
+
+int
+compare_heap_keys(const void * a, const void * b)
+{
+ heap_node ** an = (heap_node**)a;
+ heap_node ** bn = (heap_node**)b;
+ float cmp = (*an)->key - (*bn)->key;
+ if (cmp < 0)
+ return -1;
+ else
+ return 1;
+}
+
+/*
+ * Compute the heap skew for HEAP, a measure of how out-of-order the
+ * elements in the heap are. The skew of a heap node is the difference
+ * between its current position in the heap and where it would be if the
+ * heap were in sorted order. To compute this we have to sort the heap. At
+ * the end if the flag REPLACE is non-zero the heap will be returned in
+ * sorted order (with skew == 0). Note: using REPLACE does not help the
+ * performance of the heap, so only do this if you really want to have a
+ * sorted heap. It is faster not to replace.
+ */
+float
+calc_heap_skew(heap_p heap, int replace)
+{
+ heap_node ** nodes;
+ long id, diff, skew = 0;
+ #ifdef HEAP_DEBUG_SKEW
+ long skewsq = 0;
+ #endif /* HEAP_DEBUG_SKEW */
+ float norm = 0;
+ unsigned long max;
+
+ /*
+ * Lock the heap to copy it. If replacing it need to keep the heap locked
+ * until we are all done.
+ */
+ mutex_lock(hp->lock);
+
+ max = heap_nodes(heap);
+
+ /*
+ * Copy the heap nodes to a new storage area for offline sorting.
+ */
+ nodes = (heap_node **)malloc(max * sizeof(heap_node *));
+ memcpy(nodes, heap->nodes, max * sizeof(heap_node *));
+
+ if (replace == 0) {
+ /*
+ * Unlock the heap to allow updates from other threads before the sort.
+ * This allows other heap operations to proceed concurrently with the
+ * heap skew computation on the heap at the time of the call ...
+ */
+ mutex_unlock(hp->lock);
+ }
+
+ qsort(nodes, max, sizeof(heap_node *), compare_heap_keys);
+
+ for (id=0; id < max; id++) {
+ diff = id - nodes[id]->id;
+ skew += abs(diff);
+
+ #ifdef HEAP_DEBUG_SKEW
+ skewsq += diff*diff;
+ #ifdef HEAP_DEBUG_ALL
+ printf("%d\tKey = %f, diff = %d\n", id, nodes[id]->key, diff);
+ #endif /* HEAP_DEBUG */
+ #endif /* HEAP_DEBUG_SKEW */
+ }
+
+ if (replace != 0) {
+ /*
+ * Replace the original heap with the newly sorted heap and let it
+ * continue. Then compute the skew using the copy of the previous heap
+ * which we maintain as private data.
+ */
+ memcpy(heap->nodes, nodes, max * sizeof(heap_node *));
+
+ for (id = 0; id < max; id++) {
+ /*
+ * Fix up all the ID values in the copied nodes.
+ */
+ heap->nodes[id]->id = id;
+ }
+
+ mutex_unlock(hp->lock);
+ }
+
+ /*
+ * The skew value is normalized to a range of [0..1]; the distribution
+ * appears to be a skewed Gaussian distribution. For random insertions
+ * into a heap the normalized skew will be slightly less than 0.5. The
+ * maximum value of skew/N^2 (for any value of N) is about 0.39 and is
+ * fairly stable.
+ */
+ norm = skew*2.56/(max*max);
+
+ /*
+ * Free the nodes array; note this is just an array of pointers, not data!
+ */
+ free(nodes);
+ return norm;
+}
+
+#endif /* MEASURE_HEAP_SKEW */
-------------------cut here------------------------

-- 
Sincerely,                                                          srb@cuci.nl
           Stephen R. van den Berg (AKA BuGless).
"<Clarions sounding> *No one* expects the Spanish inquisition!"