From b5daac869e021ea9e03bc16e655e197506716c40 Mon Sep 17 00:00:00 2001 From: phk Date: Wed, 21 Jun 2006 08:09:02 +0000 Subject: [PATCH] Add a binary heap implementation for keeping track of objects expiry time. git-svn-id: svn+ssh://projects.linpro.no/svn/varnish/trunk@217 d4fa192b-c00b-0410-8231-f00ffab90ce4 --- varnish-cache/include/Makefile.am | 1 + varnish-cache/include/binary_heap.h | 49 ++++ varnish-cache/lib/libvarnish/Makefile.am | 1 + varnish-cache/lib/libvarnish/binary_heap.c | 260 +++++++++++++++++++++ varnish-cache/lib/libvcl/vcl_fixed_token.c | 2 +- 5 files changed, 312 insertions(+), 1 deletion(-) create mode 100644 varnish-cache/include/binary_heap.h create mode 100644 varnish-cache/lib/libvarnish/binary_heap.c diff --git a/varnish-cache/include/Makefile.am b/varnish-cache/include/Makefile.am index b863ca77..cc0f58db 100644 --- a/varnish-cache/include/Makefile.am +++ b/varnish-cache/include/Makefile.am @@ -1,6 +1,7 @@ # $Id$ include_HEADERS = \ + binary_heap.h \ compat.h \ hash.h \ libvarnish.h \ diff --git a/varnish-cache/include/binary_heap.h b/varnish-cache/include/binary_heap.h new file mode 100644 index 00000000..e27d2696 --- /dev/null +++ b/varnish-cache/include/binary_heap.h @@ -0,0 +1,49 @@ +/* + * $Id$ + * + * Binary Heap API (see: http://en.wikipedia.org/wiki/Binary_heap) + * + * XXX: doesn't scale back the array of pointers when items are deleted. + */ + +/* Public Interface --------------------------------------------------*/ + +struct binheap; + +typedef int binheap_cmp_t(void *priv, void *a, void *b); + /* + * Comparison function. + * Should return true if item 'a' should be closer to the root + * than item 'b' + */ + +typedef void binheap_update_t(void *priv, void *a, unsigned newidx); + /* + * Update function (optional) + * When items move in the tree, this function gets called to + * notify the item of its new index. + * Only needed if deleting non-root items. + */ + +struct binheap *binheap_new(void *priv, binheap_cmp_t, binheap_update_t); + /* + * Create Binary tree + * 'priv' is passed to cmp and update functions. + */ + +void binheap_insert(struct binheap *, void *); + /* + * Insert an item + */ + +void binheap_delete(struct binheap *, unsigned idx); + /* + * Delete an item + * The root item has 'idx' zero + */ + +void *binheap_root(struct binheap *); + /* + * Return the root item + */ + diff --git a/varnish-cache/lib/libvarnish/Makefile.am b/varnish-cache/lib/libvarnish/Makefile.am index 9e2c7a71..fbf4848d 100644 --- a/varnish-cache/lib/libvarnish/Makefile.am +++ b/varnish-cache/lib/libvarnish/Makefile.am @@ -6,5 +6,6 @@ lib_LTLIBRARIES = libvarnish.la libvarnish_la_SOURCES = \ argv.c \ + binary_heap.c \ cli.c \ time.c diff --git a/varnish-cache/lib/libvarnish/binary_heap.c b/varnish-cache/lib/libvarnish/binary_heap.c new file mode 100644 index 00000000..44219d46 --- /dev/null +++ b/varnish-cache/lib/libvarnish/binary_heap.c @@ -0,0 +1,260 @@ +/* + * $Id$ + * + * Implementation of a binary heap API + * + * We use a malloc(3)/realloc(3) array to store the pointers using the + * classical FORTRAN strategy. + * + * XXX: the array is not scaled back when items are deleted. + */ + +#include +#include +#include + +#include "binary_heap.h" + +/* Private definitions -----------------------------------------------*/ + +#define MIN_LENGTH 16 + +struct binheap { + unsigned magic; +#define BINHEAP_MAGIC 0xf581581aU /* from /dev/random */ + void *priv; + binheap_cmp_t *cmp; + binheap_update_t *update; + void **array; + unsigned length; + unsigned next; + unsigned granularity; +}; + +#define PARENT(u) (((u) - 1) / 2) +#define CHILD(u,n) ((u) * 2 + (n)) + +/* Implementation ----------------------------------------------------*/ + +static void +binheap_update(struct binheap *bh, unsigned u) +{ + assert(bh->magic == BINHEAP_MAGIC); + assert(u < bh->next); + if (bh->update == NULL) + return; + bh->update(bh->priv, bh->array[u], u); +} + +struct binheap * +binheap_new(void *priv, binheap_cmp_t *cmp_f, binheap_update_t *update_f) +{ + struct binheap *bh; + + bh = calloc(sizeof *bh, 1); + if (bh == NULL) + return (bh); + bh->priv = priv; + bh->cmp = cmp_f; + bh->update = update_f; + bh->next = 0; + bh->length = MIN_LENGTH; + bh->array = calloc(sizeof *bh->array, bh->length); + assert(bh->array != NULL); + bh->granularity = getpagesize() / sizeof *bh->array; + bh->magic = BINHEAP_MAGIC; + return (bh); +} + +static void +binhead_swap(struct binheap *bh, unsigned u, unsigned v) +{ + void *p; + + assert(bh->magic == BINHEAP_MAGIC); + assert(u < bh->next); + assert(v < bh->next); + p = bh->array[u]; + bh->array[u] = bh->array[v]; + bh->array[v] = p; + binheap_update(bh, u); + binheap_update(bh, v); +} + +static unsigned +binheap_trickleup(struct binheap *bh, unsigned u) +{ + unsigned v; + + assert(bh->magic == BINHEAP_MAGIC); + while (u > 0) { + v = PARENT(u); + if (bh->cmp(bh->priv, bh->array[u], bh->array[v])) { + binhead_swap(bh, u, v); + u = v; + } else + break; + } + return (u); +} + +static void +binheap_trickledown(struct binheap *bh, unsigned u) +{ + unsigned v1, v2; + + assert(bh->magic == BINHEAP_MAGIC); + while (1) { + v1 = CHILD(u, 1); + if (v1 >= bh->next) + return; + v2 = CHILD(u, 2); + if (v2 >= bh->next) { + if (!bh->cmp(bh->priv, bh->array[u], bh->array[v1])) + binhead_swap(bh, u, v1); + return; + } + if (bh->cmp(bh->priv, bh->array[v1], bh->array[v2])) { + if (!bh->cmp(bh->priv, bh->array[u], bh->array[v1])) { + binhead_swap(bh, u, v1); + u = v1; + continue; + } + } else { + if (!bh->cmp(bh->priv, bh->array[u], bh->array[v2])) { + binhead_swap(bh, u, v2); + u = v2; + continue; + } + } + return; + } +} + +void +binheap_insert(struct binheap *bh, void *p) +{ + unsigned u; + + assert(bh->magic == BINHEAP_MAGIC); + assert(bh->length >= bh->next); + if (bh->length == bh->next) { + if (bh->length >= bh->granularity * 32) + bh->length += bh->granularity * 32; + else if (bh->length > bh->granularity) + bh->length += bh->granularity; + else + bh->length += bh->length; + bh->array = realloc(bh->array, bh->length * sizeof *bh->array); + assert(bh->array != NULL); + } + u = bh->next++; + bh->array[u] = p; + binheap_update(bh, u); + binheap_trickleup(bh, u); +} + +void * +binheap_root(struct binheap *bh) +{ + + assert(bh->magic == BINHEAP_MAGIC); + if(bh->next == 0) + return (NULL); + return (bh->array[0]); +} + +void +binheap_delete(struct binheap *bh, unsigned idx) +{ + + assert(bh->magic == BINHEAP_MAGIC); + assert(bh->next > 0); + assert(idx < bh->next); + if (idx == --bh->next) + return; + bh->array[idx] = bh->array[bh->next]; + binheap_update(bh, idx); + binheap_trickledown(bh, idx); + /* XXX: free part of array ? */ +} + + +#ifdef TEST_DRIVER +/* Test driver -------------------------------------------------------*/ + +#include + +static int +cmp(void *priv, void *a, void *b) +{ + + return (*(unsigned *)a < *(unsigned *)b); +} + +void +update(void *priv, void *a, unsigned u) +{ + printf("%p is now %u\n", a, u); +} + +static void +dump(struct binheap *bh, const char *what, unsigned ptr) +{ + FILE *f; + unsigned u, *up; + + printf("dump\n"); + f = popen("dot -Tps >> /tmp/_.ps", "w"); + assert(f != NULL); + fprintf(f, "digraph binheap {\n"); + fprintf(f, "size=\"7,10\"\n"); + fprintf(f, "ptr [label=\"%s\"]\n", what); + fprintf(f, "ptr -> node_%u\n", ptr); + for (u = 0; u < bh->next; u++) { + up = bh->array[u]; + fprintf(f, "node_%u [label=\"%u\"];\n", u, *up); + if (u > 0) + fprintf(f, "node_%u -> node_%u\n", PARENT(u), u); + } + fprintf(f, "}\n"); + pclose(f); +} + +#define N 31 +int +main(int argc, char **argv) +{ + struct binheap *bh; + unsigned l[N], u, *up, lu; + + srandomdev(); + u = random(); + printf("Seed %u\n", u); + srandom(u); + system("echo %! > /tmp/_.ps"); + bh = binheap_new(NULL, cmp, update); + for (u = 0; u < N; u++) { + l[u] = random() % 1000; + binheap_insert(bh, &l[u]); + if (1) + dump(bh, "Insert", 0); + } + printf("Inserts done\n"); + lu = 0; + while(1) { + up = binheap_root(bh); + if (up == NULL) + break; + assert(*up >= lu); + lu = *up; + u = random() % bh->next; + binheap_delete(bh, u); + if (1) + dump(bh, "Delete", u); + } + printf("Deletes done\n"); + + return (0); +} +#endif diff --git a/varnish-cache/lib/libvcl/vcl_fixed_token.c b/varnish-cache/lib/libvcl/vcl_fixed_token.c index f51309fd..2b833d7f 100644 --- a/varnish-cache/lib/libvcl/vcl_fixed_token.c +++ b/varnish-cache/lib/libvcl/vcl_fixed_token.c @@ -473,7 +473,7 @@ vcl_output_lang_h(FILE *f) fputs("char *VRT_GetReq(struct sess *);\n", f); fputs("void VRT_handling(struct sess *sp, unsigned hand);\n", f); fputs("int VRT_obj_valid(struct sess *);\n", f); - fputs("int VRT_obj_cachable(struct sess *);\n", f); + fputs("int VRT_obj_cacheable(struct sess *);\n", f); fputs("\n", f); fputs("void VRT_set_backend_hostname(struct backend *, const char *);\n", f); fputs("void VRT_set_backend_portname(struct backend *, const char *);\n", f); -- 2.39.5