joes 2003/04/22 23:48:57
Modified: env mod_apreq.c
src apreq.h apreq_tables.c
t tables.c
Log:
Eliminate a few segfaults in tree insertion/deletion algorithms. Added test
handler and filter injection logic to mod_apreq.c
Revision Changes Path
1.8 +60 -12 httpd-apreq-2/env/mod_apreq.c
Index: mod_apreq.c
===================================================================
RCS file: /home/cvs/httpd-apreq-2/env/mod_apreq.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- mod_apreq.c 22 Apr 2003 21:21:18 -0000 1.7
+++ mod_apreq.c 23 Apr 2003 06:48:57 -0000 1.8
@@ -79,6 +79,7 @@
static const char env_name[] = "APACHE2";
static const char filter_name[] = "APREQ";
+
module AP_MODULE_DECLARE_DATA apreq_module;
static apr_pool_t *env_pool(void *ctx)
@@ -116,7 +117,7 @@
ctx->req = NULL;
ctx->jar = NULL;
ctx->bb_in = ctx->bb_parse = NULL;
- apr_table_add(r->notes, filter_name, (char *)ctx);
+ apr_table_addn(r->notes, filter_name, (char *)ctx);
}
return ctx;
}
@@ -143,7 +144,12 @@
apreq_request_t *oldreq = c->req;
if (oldreq == NULL) {
+ dAPREQ_LOG;
+ ap_filter_rec_t *f = ap_get_input_filter_handle(filter_name);
+ apreq_log(APREQ_DEBUG 0, r, "Adding APREQ filter to input
chain");
/* XXX: SOMEHOW INJECT APREQ INPUT FILTER */
+ ap_add_input_filter_handle(f, NULL, r, r->connection);
+
}
c->req = (apreq_request_t *)req;
@@ -162,8 +168,7 @@
static int dump_table(void *ctx, const char *key, const char *value)
{
request_rec *r = ctx;
- dAPREQ_LOG;
- apreq_log(APREQ_DEBUG 0, r, "%s => %s", key, value);
+ ap_rprintf(r, "\t%s => %s\n", key, value);
return 1;
}
@@ -200,7 +205,7 @@
ctx->bb_parse = apr_brigade_create(r->pool, f->c->bucket_alloc);
if (ctx->req == NULL) {
apreq_parser_t *parser;
- ctx->req = apreq_request(r,r->args);
+ ctx->req = apreq_request(r, NULL);
parser = apreq_make_parser(r->pool, APREQ_URL_ENCTYPE,
apreq_parse_urlencoded, NULL,
ctx->req);
apreq_register_parser(ctx->req, parser);
@@ -208,18 +213,17 @@
apreq_parse_multipart, NULL,
ctx->req);
apreq_register_parser(ctx->req, parser);
}
+ apreq_log(APREQ_DEBUG 0, r, "filter initialized");
}
else
ctx = (struct env_ctx *)f->ctx;
/* XXX configure filter & parser here */
+
rv = ap_get_brigade(f->next, ctx->bb_in, AP_MODE_READBYTES,
block, readbytes);
- apreq_log(APREQ_DEBUG rv, r, "dump args:");
- apreq_table_do(dump_table, r, ctx->req->args, NULL);
-
if (ctx->req->v.status == APR_INCOMPLETE) {
int saw_eos = 0;
@@ -239,6 +243,7 @@
}
}
+ apreq_log(APREQ_DEBUG 0, r, "filter parsing");
rv = apreq_parse(ctx->req, ctx->bb_parse);
if (rv == APR_INCOMPLETE && saw_eos == 1)
@@ -248,21 +253,64 @@
else {
APR_BRIGADE_CONCAT(bb, ctx->bb_in);
}
-
- if (ctx->req->body) {
- apreq_log(APREQ_DEBUG rv, r, "dump body:");
- apreq_table_do(dump_table, r, ctx->req->body, NULL);
- }
+ apreq_log(APREQ_DEBUG 0, r, "filter returned(%d)", rv);
return rv;
}
+static int test_handler(request_rec *r)
+{
+ apr_bucket_brigade *bb;
+ apreq_request_t *req;
+ apr_status_t s;
+ int saw_eos = 1;
+ dAPREQ_LOG;
+
+ if (strcmp(r->handler, "httpd-apreq") != 0)
+ return DECLINED;
+
+ apreq_log(APREQ_DEBUG 0, r, "initializing request");
+ req = apreq_request(r, NULL);
+
+
+ bb = apr_brigade_create(r->pool, r->connection->bucket_alloc);
+
+ do {
+ apr_bucket *e;
+ apreq_log(APREQ_DEBUG 0, r, "pulling content thru input filters");
+ s = ap_get_brigade(r->input_filters, bb, AP_MODE_READBYTES,
+ APR_BLOCK_READ, HUGE_STRING_LEN);
+
+ APR_BRIGADE_FOREACH(e,bb) {
+ if (APR_BUCKET_IS_EOS(e)) {
+ saw_eos = 1;
+ break;
+ }
+ }
+
+ apr_brigade_cleanup(bb);
+
+ } while (!saw_eos);
+
+ ap_set_content_type(r, "text/plain");
+ ap_rputs("GOT APREQ?\n\n",r);
+
+ ap_rputs("ARGS:\n");
+ apreq_table_do(dump_table, r, req->args, NULL);
+ if (req->body) {
+ ap_rputs("\nBODY:\n");
+ apreq_table_do(dump_table, r, req->body, NULL);
+ }
+ return OK;
+}
+
static void register_hooks (apr_pool_t *p)
{
ap_register_input_filter(filter_name, apreq_filter, NULL,
AP_FTYPE_CONTENT_SET);
+ ap_hook_handler(test_handler, NULL, NULL, APR_HOOK_MIDDLE);
}
1.15 +2 -2 httpd-apreq-2/src/apreq.h
Index: apreq.h
===================================================================
RCS file: /home/cvs/httpd-apreq-2/src/apreq.h,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -r1.14 -r1.15
--- apreq.h 21 Apr 2003 16:09:09 -0000 1.14
+++ apreq.h 23 Apr 2003 06:48:57 -0000 1.15
@@ -9,8 +9,8 @@
#endif
-#define APREQ_DECLARE(d) d
-#define APREQ_DECLARE_NONSTD(d) d
+#define APREQ_DECLARE(d) APR_DECLARE(d)
+#define APREQ_DECLARE_NONSTD(d) APR_DECLARE_NONSTD(d)
#define APREQ_URL_ENCTYPE "application/x-www-form-urlencoded"
#define APREQ_MFD_ENCTYPE "multipart/form-data"
#define APREQ_XML_ENCTYPE "application/xml"
1.20 +48 -106 httpd-apreq-2/src/apreq_tables.c
Index: apreq_tables.c
===================================================================
RCS file: /home/cvs/httpd-apreq-2/src/apreq_tables.c,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -r1.19 -r1.20
--- apreq_tables.c 22 Apr 2003 03:50:25 -0000 1.19
+++ apreq_tables.c 23 Apr 2003 06:48:57 -0000 1.20
@@ -207,12 +207,6 @@
return 0;
}
-/* XXX Are these macros really needed? */
-#define TREE_PUSH 1
-#define TREE_REPLACE 2
-
-#define TREE_POP 1
-#define TREE_DROP 2
static int insert(apreq_table_entry_t *o, int *root, int x,
apreq_table_entry_t *elt,
@@ -222,76 +216,49 @@
int s = search(o, &x, elt->key);
if (s == 0) { /* found */
- if (x < 0) { /* empty tree */
+ int parent = x;
+ if (parent < 0) { /* empty tree */
*root = idx;
elt->tree[LEFT] = -1;
elt->tree[RIGHT] = -1;
elt->tree[PARENT] = -1;
+ elt->color = BLACK;
return -1;
}
- switch (flags) {
- int parent;
-
- case TREE_PUSH:
- parent = x;
-
- while (parent[o].tree[NEXT] >= 0)
- parent = parent[o].tree[NEXT];
-
- parent[o].tree[NEXT] = idx;
- elt->tree[PARENT] = -1;
- elt->tree[RIGHT] = -1;
- elt->tree[LEFT] = -1;
- return x;
-
- case TREE_REPLACE:
- parent = x[o].tree[PARENT];
-
- if (x[o].tree[LEFT] >= 0)
- x[o].tree[LEFT][o].tree[PARENT] = idx;
-
- if (x[o].tree[RIGHT] >= 0)
- x[o].tree[RIGHT][o].tree[PARENT] = idx;
-
- if (parent >= 0)
- parent[o].tree[LR(x)] = idx;
- else
- *root = idx;
+ elt->color = parent[o].color;
- elt->tree[PARENT] = parent;
- elt->tree[RIGHT] = x[o].tree[RIGHT];
- elt->tree[LEFT] = x[o].tree[LEFT];
- elt->color = x[o].color;
+ while (parent[o].tree[NEXT] >= 0)
+ parent = parent[o].tree[NEXT];
- return x;
-
- default:
- return -1;
- }
+ parent[o].tree[NEXT] = idx;
+ elt->tree[PARENT] = -1;
+ elt->tree[RIGHT] = -1;
+ elt->tree[LEFT] = -1;
+ return x;
}
/* The element wasn't in the tree, so add it */
x[o].tree[s < 0 ? LEFT : RIGHT] = idx;
+
elt->tree[PARENT] = x;
elt->tree[RIGHT] = -1;
elt->tree[LEFT] = -1;
elt->color = RED;
-
if (flags & TF_BALANCE) {
while (idx[o].tree[PARENT] >= 0 && idx[o].tree[PARENT][o].color ==
RED)
{
- /* parent , grandparent, & parent_sibling nodes all exist */
+ /* parent & grandparent exist, parent_sibling may not */
int parent = idx[o].tree[PARENT];
int grandparent = parent[o].tree[PARENT];
register const int parent_direction = LR(parent);
int parent_sibling = grandparent[o].tree[!parent_direction];
- if (parent_sibling[o].color == RED) {
+ if (parent_sibling >= 0 && parent_sibling[o].color == RED) {
parent[o].color = BLACK;
parent_sibling[o].color = BLACK;
grandparent[o].color = RED;
@@ -300,13 +267,14 @@
}
else { /* parent_sibling->color == BLACK */
- if ( LR(idx) != parent_direction ) { /* opposite direction */
- rotate(o, root, parent, parent_direction); /* demotes
idx */
+ if ( LR(idx) != parent_direction ) {
+ /* demote parent & swap idx with parent */
+ rotate(o, root, parent, parent_direction);
idx = parent;
- parent = idx[o].tree[PARENT]; /* idx's old
sibling */
- /* grandparent is unchanged */
+ parent = idx[o].tree[PARENT];
}
+ /* promote parent */
parent[o].color = BLACK;
grandparent[o].color = RED;
rotate(o, root, grandparent, !parent_direction);
@@ -323,61 +291,43 @@
{
int x,y;
- if ((flags & TREE_POP) && idx[o].tree[NEXT] >= 0) {
- /* pop elt off the stack */
- x = idx[o].tree[PARENT];
- y = idx[o].tree[NEXT];
- idx[o].tree[NEXT] = 0;
-
- y[o].tree[PARENT] = x;
- y[o].tree[LEFT] = idx[o].tree[LEFT];
- y[o].tree[RIGHT] = idx[o].tree[RIGHT];
- y[o].color = idx[o].color;
+ if (idx[o].tree[LEFT] < 0 || idx[o].tree[RIGHT] < 0) {
+ x = y = 1 + idx[o].tree[RIGHT] + idx[o].tree[LEFT];
- if (x >= 0)
- x[o].tree[LR(idx)] = y;
- else
- *root = y;
- idx[o].tree[PARENT] = -1;
- idx[o].tree[LEFT] = -1;
- idx[o].tree[RIGHT] = -1;
+ if (idx[o].tree[PARENT] >= 0)
+ idx[o].tree[PARENT][o].tree[LR(idx)] = x;
+ else
+ *root = x;
- return;
+ if (x >= 0)
+ x[o].tree[PARENT] = idx[o].tree[PARENT];
+ else
+ return;
}
-
- if (idx[o].tree[LEFT] < 0 || idx[o].tree[RIGHT] < 0)
- y = idx;
else {
y = idx[o].tree[RIGHT];
while (y[o].tree[LEFT] >= 0)
y = y[o].tree[LEFT];
- }
- /* x is y's only child */
- x = (y[o].tree[LEFT] >= 0) ? y[o].tree[LEFT] : y[o].tree[RIGHT];
+ x = y[o].tree[RIGHT];
- /* remove y from the parent chain */
- x[o].tree[PARENT] = y[o].tree[PARENT];
+ if (y[o].tree[PARENT] != idx) {
+ y[o].tree[RIGHT] = idx[o].tree[RIGHT];
- if (y[o].tree[PARENT] >= 0)
- y[o].tree[PARENT][o].tree[LR(y)] = x;
- else
- *root = x;
+ if (x >= 0) {
+ x[o].tree[PARENT] = y[o].tree[PARENT];
+ y[o].tree[PARENT][o].tree[LR(y)] = x;
+ }
+ }
- if (y != idx) { /* swap y[o] with idx[o] */
y[o].tree[LEFT] = idx[o].tree[LEFT];
- y[o].tree[RIGHT] = idx[o].tree[RIGHT];
y[o].tree[PARENT] = idx[o].tree[PARENT];
- if (y[o].tree[PARENT] >= 0)
- y[o].tree[PARENT][o].tree[LR(y)] = y;
+ if (idx[o].tree[PARENT] >= 0)
+ idx[o].tree[PARENT][o].tree[LR(idx)] = y;
else
*root = y;
-
- idx[o].tree[LEFT] = -1;
- idx[o].tree[RIGHT] = -1;
- idx[o].tree[PARENT] = -1;
}
if (y[o].color == RED) {
@@ -385,9 +335,10 @@
return;
}
+
/* rebalance tree (standard double-black promotion) */
- x[o].color = idx[o].color; /* should this be y[o].color ??? */
+ x[o].color = idx[o].color;
if (flags & TF_BALANCE) {
while (x != *root && x[o].color == BLACK)
@@ -455,7 +406,7 @@
a[o].tree[PARENT] = -1;
}
- if (insert(o,&a,a,b+o, TREE_PUSH) < 0)
+ if (insert(o,&a,a,b+o,0) < 0)
rv = b;
if (b[o].tree[PARENT] >= 0)
@@ -666,8 +617,7 @@
memset(t->root,-1,TABLE_HASH_SIZE * sizeof(int));
for (idx = 0; idx < t->a.nelts; ++idx)
- insert(o, &t->root[TABLE_HASH(idx[o].key)], -1, &idx[o],
- TF_BALANCE | TREE_PUSH);
+ insert(o, &t->root[TABLE_HASH(idx[o].key)], -1, &idx[o],
TF_BALANCE);
t->flags |= TF_BALANCE;
}
@@ -874,12 +824,6 @@
int idx = t->root[TABLE_HASH(key)];
apreq_table_entry_t *o = (apreq_table_entry_t *)t->a.elts;
-#ifdef POOL_DEBUG
- {
- /* XXX */
- }
-#endif
-
if (idx >= 0 && search(o,&idx,key) == 0) {
int n;
idx[o].val = val;
@@ -895,7 +839,7 @@
e->val = val;
e->tree[NEXT] = -1;
insert((apreq_table_entry_t *)t->a.elts,
- &t->root[TABLE_HASH(key)],idx,e,TREE_PUSH);
+ &t->root[TABLE_HASH(key)],idx,e,t->flags);
}
}
@@ -909,7 +853,7 @@
LOCK_TABLE(t);
- delete(o,&t->root[TABLE_HASH(key)],idx,TREE_DROP);
+ delete(o,&t->root[TABLE_HASH(key)],idx, t->flags);
for ( n=idx; n>=0; n=n[o].tree[NEXT] )
KILL(t,n);
@@ -962,7 +906,7 @@
e->val = val;
e->tree[NEXT] = -1;
insert((apreq_table_entry_t *)t->a.elts,
- &t->root[TABLE_HASH(key)],idx,e,TREE_PUSH);
+ &t->root[TABLE_HASH(key)],idx,e,t->flags);
}
return val->status;
}
@@ -986,7 +930,7 @@
elt->key = val->name;
elt->val = val;
elt->tree[NEXT] = -1;
- insert(o, root, *root, elt, TREE_PUSH);
+ insert(o, root, *root, elt, t->flags);
return APR_SUCCESS;
}
@@ -1022,7 +966,6 @@
if (DEAD(idx))
continue;
-
if (idx[o].tree[NEXT] >= 0)
idx[o].tree[NEXT] += n;
@@ -1039,8 +982,7 @@
else if ( idx[o].tree[PARENT] >= 0 ||
s->root[hash] == idx-n )
{
- insert(o, &t->root[hash], t->root[hash], idx+o,
- TREE_PUSH | TF_BALANCE);
+ insert(o, &t->root[hash], t->root[hash], idx+o, TF_BALANCE);
}
}
}
1.7 +44 -33 httpd-apreq-2/t/tables.c
Index: tables.c
===================================================================
RCS file: /home/cvs/httpd-apreq-2/t/tables.c,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- tables.c 21 Apr 2003 18:45:57 -0000 1.6
+++ tables.c 23 Apr 2003 06:48:57 -0000 1.7
@@ -75,14 +75,18 @@
{
t1 = apreq_make_table(p, 5);
CuAssertPtrNotNull(tc, t1);
+ apreq_table_balance(t1,1);
}
static void table_get(CuTest *tc)
{
const char *val;
+ apreq_table_set(t1, V(APREQ_URL_ENCTYPE,"foo"));
+ apreq_table_set(t1, V(APREQ_MFD_ENCTYPE,"bar"));
- apreq_table_set(t1, V("foo","bar"));
- val = apreq_table_get(t1,"foo");
+ val = apreq_table_get(t1,APREQ_URL_ENCTYPE);
+ CuAssertStrEquals(tc,"foo",val);
+ val = apreq_table_get(t1,APREQ_MFD_ENCTYPE);
CuAssertStrEquals(tc,"bar",val);
}
@@ -114,23 +118,46 @@
apreq_table_add(t1, V("add", "foo"));
val = apreq_table_get(t1, "add");
CuAssertStrEquals(tc, "bar", val);
- apreq_table_add(t1, V("fl", "left"));
- apreq_table_add(t1, V("fr", "right"));
- apreq_table_add(t1, V("fll", "left-left"));
- apreq_table_add(t1, V("frr", "right-right"));
- apreq_table_add(t1, V("frl", "right-left"));
- apreq_table_add(t1, V("flr", "left-right"));
- apreq_table_add(t1, V("b", "bah"));
+
+
+ apreq_table_add(t1, V("f", "top"));
+ apreq_table_add(t1, V("fo", "child"));
+ apreq_table_add(t1, V("fro", "child-right"));
+
+ /*
+ * f(5) black fo(6) black
+ * fo(6) red => f(5)red fro(7)red
+ * fro(7) red
+ *
+ */
+
+
+ apreq_table_add(t1, V("flo", "child-left"));
+ apreq_table_add(t1, V("flr", "child-left-right"));
+ apreq_table_add(t1, V("frr", "child-right-right"));
+ apreq_table_add(t1, V("frl", "child-right-left"));
+ apreq_table_add(t1, V("flr", "child-left-right"));
+ apreq_table_add(t1, V("fll", "child-left-left"));
+ apreq_table_add(t1, V("foo", "bar"));
+ apreq_table_add(t1, V("b", "bah humbug"));
val = apreq_table_get(t1, "foo");
CuAssertStrEquals(tc, "bar", val);
- val = apreq_table_get(t1, "fl");
- CuAssertStrEquals(tc, "left", val);
- val = apreq_table_get(t1, "fr");
- CuAssertStrEquals(tc, "right", val);
+ val = apreq_table_get(t1, "flr");
+ CuAssertStrEquals(tc, "child-left-right", val);
+}
+
+static void table_unset(CuTest *tc) {
+ const char *val;
+ apreq_table_unset(t1, "flo");
+ val = apreq_table_get(t1, "flo");
+ CuAssertPtrEquals(tc, NULL, val);
+
+ val = apreq_table_get(t1, "fro");
+ CuAssertStrEquals(tc, "child-right", val);
val = apreq_table_get(t1, "fll");
- CuAssertStrEquals(tc, "left-left", val);
+ CuAssertStrEquals(tc, "child-left-left", val);
val = apreq_table_get(t1, "frl");
- CuAssertStrEquals(tc, "right-left", val);
+ CuAssertStrEquals(tc, "child-right-left", val);
}
@@ -159,22 +186,6 @@
CuAssertIntEquals(tc, 0, apreq_table_nelts(t1));
}
-static void table_unset(CuTest *tc)
-{
- const char *val;
- apreq_table_t *t;
-
- t = apreq_table_make(p, 1);
- apreq_table_set(t, V("a", "1"));
- apreq_table_set(t, V("b", "2"));
- apreq_table_unset(t, "b");
- CuAssertIntEquals(tc, 1, apreq_table_nelts(t));
- val = apreq_table_get(t, "a");
- CuAssertStrEquals(tc, val, "1");
- val = apreq_table_get(t, "b");
- CuAssertPtrEquals(tc, NULL, val);
-}
-
static void table_overlap(CuTest *tc)
{
const char *val;
@@ -301,13 +312,13 @@
CuSuite *suite = CuSuiteNew("Table");
SUITE_ADD_TEST(suite, table_make);
- SUITE_ADD_TEST(suite, table_get);
+ SUITE_ADD_TEST(suite, table_get);
SUITE_ADD_TEST(suite, table_set);
SUITE_ADD_TEST(suite, table_getnotthere);
SUITE_ADD_TEST(suite, table_add);
+ SUITE_ADD_TEST(suite, table_unset);
SUITE_ADD_TEST(suite, table_nelts);
SUITE_ADD_TEST(suite, table_clear);
- SUITE_ADD_TEST(suite, table_unset);
SUITE_ADD_TEST(suite, table_overlap);
SUITE_ADD_TEST(suite, table_elts);
SUITE_ADD_TEST(suite, table_overlay);
