/* tree.c   by Michael Thorpe   2000-06-10 */
/* FIXME: I assume that realloc(p,smallersize) will always return p */

#include <stdlib.h>
#include <string.h>
#include "tree.h"

/* There are still races here, but at least it's worse than nothing ;) */
#define initlock(tree) do{tree->lock=0;}while(0)
#define readlock(tree) do{while(tree->lock&1);tree->lock+=2;}while(0)
#define writelock(tree) do{while(tree->lock&1);tree->lock|=1;while(tree->lock&~1);}while(0)
#define readunlock(tree) do{tree->lock-=2;}while(0)
#define writeunlock(tree) do{tree->lock&=~1;}while(0)
#define swapvalues(a,b) do{treevalue swapvalues_tmp=(b);(b)=(a);(a)=swapvalues_tmp;}while(0)

#define TNSIZE(strlen) (sizeof(struct treenode)+(strlen))

typedef struct treenode treenode;
typedef TREE_VALUETYPE treevalue;

struct treenode {
   treenode *child,*next;
   treevalue value;
   char s[1];
};

struct tree {
   treenode *root;
   size_t size;
   int nodes;
   int lock;
};

struct match {
   int len,nodeslen;
   treenode **nodes;
};

tree *tree_create(void) {
   tree *newtree;

   newtree=(tree *)malloc(sizeof(tree));
   if(!newtree)
      return(0);
   newtree->root=0;
   newtree->size=0;
   newtree->nodes=0;
   newtree->lock=0;
   initlock(newtree);

   return(newtree);
}

static void treenode_destroy(tree *tree,treenode *node) {
   treenode *tmp;

   while(node) {
      if(node->child)
         treenode_destroy(tree,node->child);
      node=(tmp=node)->next;
      tree->size-=TNSIZE(strlen(tmp->s));
      tree->nodes--;
      free(tmp);
   }
}

int tree_destroy(tree *tree) {
   int i;

   writelock(tree);
   if(tree->root)
      treenode_destroy(tree,tree->root);
   i=tree->size+tree->nodes;
   tree->root=0; /* Just in case our caller isn't playing by the rules */
   writeunlock(tree);
   free(tree);

   return(i);
}

static int treenode_match_push(treenode *node,struct match *match) {
   treenode **tmp;

   tmp=(treenode **)realloc(match->nodes,sizeof(treenode *)*(match->nodeslen+1));
   if(!tmp)
      return(1);
   match->nodes=tmp;
   match->nodes[match->nodeslen++]=node;

   return(0);
}

static treenode *treenode_match(treenode *node,const char *s,struct match *match) {
   int i;
   treenode *tmp;

   for(;node;node=node->next) {
      if(node->s[0]) {
         for(i=0;node->s[i];i++)
            if(node->s[i] != s[i])
               break;
         if(!i)
            continue;
         if(!node->s[i]) {
            if(match) {
               match->len+=i;
               if(treenode_match_push(node,match))
                  goto fail;
            }
            if(node->child) {
               tmp=treenode_match(node->child,&s[i],match);
               if(tmp) {
                  node=tmp;
                  goto done;
               }
            }
            if(match)
               goto done;
            if(!s[i])
               goto done;
         }
         if(match)
            goto fail;
         for(tmp=node;tmp;tmp=tmp->next)
            if(!tmp->s[0])
               break;
         if(!tmp)
            goto fail;
         node=treenode_match(tmp,s,match);
         goto done;
      } else if(TREE_WILDCARD) {
         if(match) {
            if(s[0] != TREE_WILDCARD)
               continue;
            match->len++;
            if(treenode_match_push(node,match))
               goto fail;
            tmp=treenode_match(node->child,&s[1],match);
            if(tmp)
               node=tmp;
            goto done;
         }
         if(!node->child) {
            if(match) {
               match->len+=strlen(s);
               if(treenode_match_push(node,match))
                  goto fail;
            }
            goto done;
         }
         for(i=0;s[i];i++) {
            tmp=treenode_match(node->child,&s[i],match);
            if(tmp) {
               node=tmp;
               if(match) {
                  match->len+=i;
                  if(treenode_match_push(node,match))
                     goto fail;
               }
               goto done;
            }
         }
      }
   }

fail:
   node=0;
done:
   return(node);
}

static treenode *treenode_makerem(tree *tree,const char *s,treevalue value) {
   int i;
   treenode *node=0,*tmp=0,*tmp2;

   while(s[0]) {
      for(i=0;s[i] && s[i] != TREE_WILDCARD;i++)
         ;
      tmp2=(treenode *)malloc(TNSIZE(i));
      if(!tmp2)
         goto fail;
      tmp2->child=0;
      tmp2->next=0;
      if(node) {
         tmp->child=tmp2;
         tmp=tmp->child;
      } else
         node=tmp=tmp2;
      strncpy(tmp2->s,s,i);
      tmp2->s[i]='\0';
      tree->size+=TNSIZE(i);
      tree->nodes++;
      s+=(i?i:1);
      if(!s[0])
         tmp2->value=value;
      else
         tmp2->value=0;
   }

   return(node);
fail:
   while(node) {
      tmp=node;
      node=node->child;
      tree->size-=TNSIZE(strlen(tmp->s));
      tree->nodes--;
      free(tmp);
   }
   return(0);
}

static treenode *treenode_break(tree *tree,treenode *node,const char *s,treevalue value) {
   treenode *foo,*bar=0;
   int i,j;

   while(1) {
      for(i=0;s[i]==node->s[i];i++)
         ;
      if(!i)
         goto next;
      j=strlen(&node->s[i]);
      foo=(treenode *)malloc(TNSIZE(j));
      if(!foo)
         goto fail;
      if(s[i]) {
         bar=treenode_makerem(tree,&s[i],value);
         if(!bar) {
            free(foo);
            goto fail;
         }
      }
      strcpy(foo->s,&node->s[i]);
      if(!realloc(node,TNSIZE(i))) {
         free(foo);
         while(bar) {
            foo=bar;
            bar=bar->next;
            tree->size-=TNSIZE(strlen(foo->s));
            tree->nodes--;
            free(foo);
         }
         goto fail;
      }
      node->s[i]='\0';
      foo->value=node->value;
      node->value=0;
      if(!s[i])
         node->value=value;
      foo->child=node->child;
      node->child=foo;
      foo->next=bar;
      tree->size+=TNSIZE(i)+TNSIZE(j)-TNSIZE(j+i);
      tree->nodes++;
      goto done;
next:
      if(node->next)
         node=node->next;
      else {
         node->next=treenode_makerem(tree,s,value);
         node=node->next;
         goto done;
      }
   }

done:
   return(node);
fail:
   return(0);
}

int tree_add(tree *tree,const char *s,treevalue value) {
   treenode *node,*tmp;
   struct match match;

   if(!value)
      return(1);
   match.len=0;
   match.nodeslen=0;
   match.nodes=0;
   writelock(tree);
   if(!tree->root) {
      node=treenode_makerem(tree,s,value);
      if(!node)
         goto fail;
      tree->root=node;
      goto good;
   }
   node=treenode_match(tree->root,s,&match);
   free(match.nodes);
   if(!node) {
      if(!treenode_break(tree,tree->root,s,value))
         goto fail;
   } else if(!s[match.len]) {
      if(node->value)
         goto fail;
      node->value=value;
   } else if(node->child && node->child->s[0]) {
      if(!treenode_break(tree,node->child,&s[match.len],value))
         goto fail;
   } else {
      tmp=treenode_makerem(tree,&s[match.len],value);
      if(!tmp)
         goto fail;
      tmp->next=node->child;
      node->child=tmp;
   }

good:
   writeunlock(tree);
   return(0);
fail:
   writeunlock(tree);
   return(1);
}

treevalue tree_del(tree *tree,const char *s) {
   int i,j;
   treenode *parent,*stay,*go,*tmp;
   struct match match;
   treevalue retval=0;

   match.len=0;
   match.nodeslen=0;
   match.nodes=0;
   parent=stay=go=0;
   writelock(tree);
   if(!tree->root)
      goto done;
   treenode_match(tree->root,s,&match);
   if(!match.nodeslen)
      goto done;
   if(match.len != strlen(s))
      goto done;
   tmp=match.nodes[match.nodeslen-1];
   if(tmp->child) {
      if(!tmp->value)
         goto done;
      swapvalues(tmp->value,retval);
      goto done;
   }
   for(i=match.nodeslen-2;i>=0;i--) {
      if(match.nodes[i]->value || match.nodes[i]->child->next) {
         stay=match.nodes[i];
         go=match.nodes[i+1];
         if(i)
            parent=match.nodes[i-1];
         break;
      }
   }
   if(!stay) {
      if(tree->root->next) {
         go=match.nodes[0];
         if(tree->root==go)
            tree->root=go->next;
         else {
            for(stay=tree->root;go != stay->next;stay=stay->next)
               ;
            stay->next=go->next;
         }
      } else {
         go=tree->root;
         tree->root=0;
      }
      goto nukeit;
   }
   if(stay->child==go)
      stay->child=go->next;
   else if(stay->child->next==go)
      stay->child->next=go->next;
   else {
      for(stay=stay->child->next;go != stay->next;stay=stay->next)
         ;
      stay->next=go->next;
      goto nukeit;
   }
   if(!stay->child)
      goto nukeit;
   if(stay->child->next)
      goto nukeit;
   if(!stay->s[0] || !stay->child->s[0])
      goto nukeit;
   if(stay->value)
      goto nukeit;
   i=strlen(stay->s);
   j=strlen(stay->child->s);
   tmp=(treenode *)realloc(stay,TNSIZE(i+j));
   if(!tmp)
      goto nukeit;
   tree->size+=TNSIZE(i+j)-TNSIZE(i)-TNSIZE(j);
   tree->nodes--;
   strcat(tmp->s,tmp->child->s);
   if(tmp != stay) {
      if(parent) {
         if(parent->child==stay) {
            parent->child=tmp;
            parent=0;
         } else
            parent=parent->child;
      } else {
         if(tree->root==stay)
            tree->root=tmp;
         else
            parent=tree->root;
      }
      if(parent) {
         while(stay != parent->next)
            parent=parent->next;
         parent->next=tmp;
      }
      stay=tmp;
   }
   parent=stay->child;
   stay->child=parent->child;
   stay->value=parent->value;
   free(parent);
nukeit:
   while(go) {
      retval=go->value;
      stay=go->child;
      tree->size-=TNSIZE(strlen(go->s));
      tree->nodes--;
      free(go);
      go=stay;
   }
done:
   free(match.nodes);
   writeunlock(tree);
   return(retval);
}

treevalue tree_match(tree *tree,const char *s) {
   treevalue value;
   treenode *node;

   value=0;
   if(tree->root) {
      readlock(tree);
      node=treenode_match(tree->root,s,0);
      if(node)
         value=node->value;
      readunlock(tree);
   }

   return(value);
}

treevalue tree_change(tree *tree,const char *s,treevalue new) {
   treenode *node;
   struct match match;

   if(!tree->root)
      return(0);
   match.len=0;
   match.nodeslen=0;
   match.nodes=0;
   readlock(tree);
   node=treenode_match(tree->root,s,&match);
   if(node)
      swapvalues(new,node->value);
   else
      new=0;
   readunlock(tree);
   free(match.nodes);

   return(new);
}

size_t tree_getsize(tree *tree) {
   return(tree->size);
}

int tree_getnodes(tree *tree) {
   return(tree->nodes);
}

static int treenode_dump(treenode *node,int (*func)(const char *,int,treevalue),int depth) {
   while(node) {
      if((*func)(node->s,depth,node->value))
         return(1);
      if(node->child)
         if(treenode_dump(node->child,func,depth+1))
            return(1);
      node=node->next;
   }

   return(0);
}

int tree_dump(tree *tree,int (*func)(const char *,int,treevalue)) {
   int i;

   readlock(tree);
   i=treenode_dump(tree->root,func,0);
   readunlock(tree);

   return(i);
}