first prototype of splaying active list

diff --git a/lib/MD5.c b/lib/MD5.c
index c12b761..9e60f50 100644 (file)
--- a/lib/MD5.c
+++ b/lib/MD5.c
@@ -33,6 +33,7 @@
 #include "../config.h"
 
 #include <string.h>
+#include <memory.h>
 
 #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 (file)
--- 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 (file)
--- 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 (file)
--- 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 (file)
--- a/lib/gfxpoly/active.c
+++ b/lib/gfxpoly/active.c
@@ -1,3 +1,4 @@
+#include <memory.h>
 #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 (file)
--- 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 (file)
--- 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 (file)
--- 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;