From: Matthias Kramm Date: Tue, 5 May 2009 20:51:11 +0000 (+0200) Subject: first prototype of splaying active list X-Git-Tag: polyok~8 X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=commitdiff_plain;h=c768cd47515e9101d8d38de85cc2f6fcbfccaef6 first prototype of splaying active list --- diff --git a/lib/MD5.c b/lib/MD5.c index c12b761..9e60f50 100644 --- a/lib/MD5.c +++ b/lib/MD5.c @@ -33,6 +33,7 @@ #include "../config.h" #include +#include #ifndef _NETINET6_MD5_H_ #define _NETINET6_MD5_H_ @@ -175,6 +176,24 @@ void hash_md5(const unsigned char*buf, int len, unsigned char*dest) MD5Final(dest, &ctx); } +void* init_md5() +{ + MD5_CTX* ctx = malloc(sizeof(MD5_CTX)); + memset(ctx, 0, sizeof(MD5_CTX)); + MD5Init(ctx); + return ctx; +} +void update_md5(void*ctx, unsigned char*data, int len) +{ + MD5Update(ctx, data, len); +} +void finish_md5(void*ctx, unsigned char*dest) +{ + MD5Final(dest, ctx); + free(ctx); +} + + char * crypt_md5(const char *pw, const char *salt) { MD5_CTX ctx,ctx1; diff --git a/lib/MD5.h b/lib/MD5.h index 0003492..ad54fe1 100644 --- a/lib/MD5.h +++ b/lib/MD5.h @@ -25,4 +25,8 @@ #define __MD5_h__ char * crypt_md5(const char *pw, const char *salt); void hash_md5(const unsigned char*buf, int len, unsigned char*dest); //dest needs to be 16 bytes wide + +void* init_md5(); +void update_md5(void*ctx, unsigned char*data, int len); +void finish_md5(void*ctx, unsigned char*dest); #endif diff --git a/lib/gfxpoly.c b/lib/gfxpoly.c index 76352af..902eaf8 100644 --- a/lib/gfxpoly.c +++ b/lib/gfxpoly.c @@ -302,7 +302,7 @@ intbbox_t get_svp_bbox(ArtSVP*svp, double zoom) #define B00000010 0x02 #define B00000001 0x01 -int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2) +static int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2) { if(!data1 || !data2) return 0; diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile index 8469965..326c8c6 100644 --- a/lib/gfxpoly/Makefile +++ b/lib/gfxpoly/Makefile @@ -1,4 +1,4 @@ -all: testheap test +all: test CC = gcc -g -O2 diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c index aece368..5d01c30 100644 --- a/lib/gfxpoly/active.c +++ b/lib/gfxpoly/active.c @@ -1,3 +1,4 @@ +#include #include "../q.h" #include "active.h" @@ -55,6 +56,22 @@ void actlist_verify(actlist_t*a, int32_t y) } } +static inline double cmp(segment_t*s, point_t p1, point_t p2) +{ + double d = LINE_EQ(p1, s); + if(d==0) { + d = LINE_EQ(p2, s); + if(d==0) { + /* We default to always inserting the new segment to the right of the old segment. + We do this so that we don't place new segments into the middle of already + overlapping lines which may have intersections scheduled. + */ + //fprintf(stderr, "Notice: actlist_find: both points (%d,%d) and (%d,%d) exactly on segment [%d]\n", p1.x, p1.y, p2.x, p2.y, s->nr); + } + } + return d; +} + segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) { /* this runs in O(n) right now, and should be optimized using a splay @@ -65,17 +82,7 @@ segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) segment_t*last=0, *s = a->list; if(!s) return last; while(s) { - double d = LINE_EQ(p1, s); - if(d==0) { - d = LINE_EQ(p2, s); - if(d==0) { - /* We default to always inserting the new segment to the right of the old segment. - We do this so that we don't place new segments into the middle of already - overlapping lines which may have intersections scheduled. - */ - //fprintf(stderr, "Notice: actlist_find: both points (%d,%d) and (%d,%d) exactly on segment [%d]\n", p1.x, p1.y, p2.x, p2.y, s->nr); - } - } + double d = cmp(s, p1, p2); if(d<0) break; last = s; @@ -84,6 +91,153 @@ segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) return last; } +#ifdef SPLAY + +#define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);};printf("%08x->%s now %08x\n", node, __STRING(side), child); + +// rotates segment's left node to the top +static inline segment_t*rotate_right(actlist_t*a, segment_t*s) +{ + /* s n + / \ + n -> s + \ / + l l + */ + assert(s->leftchild); + segment_t*p = s->parent; + segment_t*n = s->leftchild; + segment_t*l = s->rightchild; + LINK(n,rightchild,s); + LINK(s,leftchild,l); + n->parent = p; + if(p) { + if(p->leftchild == s) + p->leftchild = n; + else if(p->rightchild == s) + p->rightchild = n; + } else { + a->root = n; + } + return n; +} +// rotates segment's right node to the top +static inline segment_t*rotate_left(actlist_t*a, segment_t*s) +{ + /* s n + \ / + n -> s + / \ + r r + */ + assert(s->rightchild); + segment_t*p = s->parent; + segment_t*n = s->rightchild; + segment_t*r = n->leftchild; + LINK(n,leftchild,s); + LINK(s,rightchild,r); + n->parent = p; + if(p) { + if(p->leftchild == s) + p->leftchild = n; + else if(p->rightchild == s) + p->rightchild = n; + } else { + a->root = n; + } + return n; +} +static void move_to_root(actlist_t*a, segment_t*s) +{ + /* this is a textbook implementation of the three splay operations + zig, zig-zig and zig-zag */ + while(a->root != s) { + assert(s->parent); + segment_t*p = s->parent; + if(p == a->root) { + // zig + if(a->root->leftchild == s) { + rotate_right(a, a->root); + } else { + rotate_left(a, a->root); + } + assert(a->root == s); + } else { + segment_t*pp = p->parent; + if(p->leftchild == s && p->parent->leftchild == p->parent) { + // zig-zig (left) + rotate_right(a, pp); + rotate_right(a, pp); + } else if(p->rightchild == s && p->parent->rightchild == p->parent) { + // zig-zig (right) + rotate_left(a, pp); + rotate_left(a, pp); + } else if(p->leftchild == s && p->parent->rightchild == p->parent) { + // zig-zag (left) + rotate_right(a, p); + rotate_left(a, pp); + } else if(p->rightchild == s && p->parent->leftchild == p->parent) { + // zig-zag (right) + rotate_right(a, p); + rotate_left(a, pp); + } + } + } +} + +static int actlist_splay(actlist_t*a, point_t p1, point_t p2) +{ + if(!a->list) return; + + segment_t tmp; + memset(&tmp, 0, sizeof(tmp)); + segment_t*left=&tmp,*right=&tmp; + + while(1) { + if(cmp(a->root,p1,p2)<0) { + /* we're to the left of the root */ + if(!a->root->leftchild) + return -1; + if(cmp(a->root->leftchild,p1,p2)<0) { + /* we're also to the left of the root's left child + -> rotate right, so that the left child is root */ + segment_t*s = a->root->leftchild; + LINK(a->root, leftchild, s->rightchild); + LINK(s, rightchild, a->root); + a->root = s; + if(!a->root->leftchild) + return -1; + } + LINK(right, leftchild, a->root); + right = a->root; + a->root = a->root->leftchild; + } else /* cmp(a->root,p1,p2)>=0 */ { + /* we're to the right of the root */ + if(!a->root->rightchild) + return 1; + if(cmp(a->root->rightchild,p1,p2)>=0) { + /* we're also to the right of the root's right child + -> rotate left, so that the right child is root */ + segment_t*s = a->root->rightchild; + LINK(a->root, rightchild, s->leftchild); + LINK(s, leftchild, a->root); + a->root = s; + if(!a->root->rightchild) + return 1; + } + LINK(left, rightchild, a->root); + left = a->root; + a->root = a->root->rightchild; + } + } + LINK(left, rightchild, a->root->leftchild); + LINK(right, leftchild, a->root->rightchild); + LINK(a->root, leftchild, tmp.rightchild); + LINK(a->root, rightchild, tmp.leftchild); +} + +#endif + static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s) { s->left = left; @@ -97,12 +251,38 @@ static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s) s->left->right = s; if(s->right) s->right->left = s; + +#ifdef SPLAY + // we insert nodes not trees + assert(!s->leftchild); + assert(!s->rightchild); + + if(a->root) { + //if(actlist_splay(a, s->a, s->b) < 0) { + if(cmp(a->root, s->a, s->b) < 0) { + printf("new node %08x, link root (%08x) to the right\n", s, a->root); + LINK(s,rightchild,a->root); + // steal left child from (previous) root + LINK(s,leftchild,a->root->leftchild); + a->root->leftchild = 0; + } else { + printf("new node %08x, link root (%08x) to the left\n", s, a->root); + LINK(s,leftchild,a->root); + // steal right child from (previous) root + LINK(s,rightchild,a->root->rightchild); + a->root->rightchild = 0; + } + } + a->root = s; + a->root->parent = 0; +#endif + a->size++; } -void actlist_insert(actlist_t*a, point_t p, segment_t*s) +void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s) { - segment_t*left = actlist_find(a, p, s->b); + segment_t*left = actlist_find(a, p1, p2); actlist_insert_after(a, left, s); } @@ -118,6 +298,37 @@ void actlist_delete(actlist_t*a, segment_t*s) } s->left = s->right = 0; a->size--; +#ifdef SPLAY + printf("delete %08x\n", s); + move_to_root(a, s); + assert(a->root == s); + // delete root node + if(!a->root->leftchild) { + printf("shift %08x->rightchild (%08x) to root\n", a->root, a->root->rightchild); + a->root = a->root->rightchild; + } else if(!a->root->rightchild) { + printf("shift %08x->leftchild (%08x) to root\n", a->root, a->root->leftchild); + a->root = a->root->leftchild; + } else { + printf("freeing up %08x->left->right\n", a->root); + // free up root->left->right + segment_t*t = a->root->leftchild; + while(t->rightchild) { + segment_t*r = t->rightchild; + segment_t*l = r->leftchild; + LINK(r, leftchild, t); + LINK(t, rightchild, l); + t = r; + } + LINK(a->root,leftchild,t); + assert(!a->root->leftchild->rightchild); + LINK(a->root->leftchild,rightchild,a->root->right); + a->root = a->root->leftchild; + } + if(a->root) + a->root->parent = 0; + s->leftchild = s->rightchild = s->parent = 0; +#endif } int actlist_size(actlist_t*a) { @@ -154,6 +365,7 @@ segment_t* actlist_right(actlist_t*a, segment_t*s) void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2) { + // for splaying this needs to be rewritten (can't use insert_after) actlist_delete(a, s1); actlist_insert_after(a, s2, s1); } diff --git a/lib/gfxpoly/active.h b/lib/gfxpoly/active.h index f567bea..6809e7b 100644 --- a/lib/gfxpoly/active.h +++ b/lib/gfxpoly/active.h @@ -2,13 +2,14 @@ #define __active_h__ #include "poly.h" -//#include "splay.h" typedef struct _actlist { - //SPLAY_HEAD(root, actnode_t); segment_t*list; int size; +#ifdef SPLAY + segment_t*root; +#endif } actlist_t; actlist_t* actlist_new(); @@ -17,7 +18,7 @@ int actlist_size(actlist_t*a); void actlist_verify(actlist_t*a, int32_t y); void actlist_dump(actlist_t*a, int32_t y); segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2); // finds segment immediately to the left of p1 (breaking ties w/ p2) -void actlist_insert(actlist_t*a, point_t p, segment_t*s); +void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s); void actlist_delete(actlist_t*a, segment_t*s); void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2); segment_t* actlist_left(actlist_t*a, segment_t*s); diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 4d641a1..1ef8618 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -887,7 +887,8 @@ void event_apply(status_t*status, event_t*e) event_dump(e); #endif segment_t*s = e->s1; - actlist_insert(status->actlist, e->p, s); + assert(e->p.x == s->a.x && e->p.y == s->a.y); + actlist_insert(status->actlist, s->a, s->b, s); segment_t*left = actlist_left(status->actlist, s); segment_t*right = actlist_right(status->actlist, s); if(left) @@ -989,7 +990,8 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule) windstate_t before,after; switch(e->type) { case EVENT_START: { - actlist_insert(actlist, e->p, s); + assert(e->p.x == s->a.x && e->p.y == s->a.y); + actlist_insert(actlist, s->a, s->b, s); event_t e; e.type = EVENT_END; e.p = s->b; diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index b967567..fb1128c 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -6,6 +6,7 @@ //#define DEBUG #define CHECKS +//#define SPLAY typedef enum {DIR_UP, DIR_DOWN} segment_dir_t; typedef enum {EVENT_CROSS, EVENT_END, EVENT_CORNER, EVENT_START, EVENT_HORIZONTAL} eventtype_t; @@ -58,6 +59,11 @@ typedef struct _segment { windstate_t wind; int nr; +#ifdef SPLAY + struct _segment*parent; + struct _segment*leftchild; + struct _segment*rightchild; +#endif struct _segment*left; struct _segment*right; char changed;