/* ftree.c   by Michael Thorpe   2002-06-17 */
/* FIXME: We assume sane and consistent compiler struct layout */

#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/file.h>
#include "ftree.h"

#include <endian.h>
#if BYTE_ORDER != LITTLE_ENDIAN
#error "I don't yet have conversion routines for non-little endian machines."
#endif

#define TNODEI(t,i) (((ftreenode *)(t)->mem)[(i)])
#define TSIZEI(t,i) (((unsigned char *)&((ftreenode *)(t)->mem)[(i)])[-1])
#define THOLEI(t,i) (((ftreehole *)(t)->mem)[(i)])
#define TROOT(t) (((ftreehead *)t->mem)->root)

typedef struct ftreenode ftreenode;
typedef struct ftreehole ftreehole;
typedef struct ftreehead ftreehead;
typedef unsigned int idx;
typedef FTREE_VALUETYPE ftreevalue;

struct ftreenode {
   idx child,next;
   ftreevalue value;
   char s[1];
};

struct ftreehead {
   idx freetail,free,root;
   char magic[3];
};

struct ftreehole {
   idx prev,next;
   unsigned char size;
   unsigned char filler[7];
};

struct ftree {
   void *mem;
   int fd;
   unsigned int lock,writelock;
   size_t size;
};

struct match {
   int len;
   int nodeslen;
   idx *nodes;
};

static int ftree_resize(ftree *tree) {
   struct stat st;
   void *p;

   if(0>fstat(tree->fd,&st))
      goto fail;
   if(!tree->size || st.st_size != tree->size) {
      if(st.st_size) {
         if(tree->size)
/* BTW, it's kinda undefined what happens to tree->mem if mremap fails... */
            p=mremap(tree->mem,tree->size,st.st_size,MREMAP_MAYMOVE);
         else
            p=mmap(0,st.st_size,PROT_READ|PROT_WRITE,MAP_SHARED,tree->fd,0);
         if(p==(void *)-1)
            goto fail_zero;
         tree->mem=p;
         tree->size=st.st_size;
      } else if(tree->mem) {
         munmap(tree->mem,tree->size);
         tree->mem=0;
      }
   }
   tree->size=st.st_size;
   return(0);
fail_zero:
   tree->mem=0;
   tree->size=0;
fail:
   return(1);
}

/* FIXME: This declaration is bogus, and relies on the compiler optimizing
          the if() statement below away completely (also invalid with a
          non-32-bit FTREE_VALUETYPE */
void struct_ftreenode_ftreehole_or_ftreehead_is_the_wrong_size(void);
static int ftree_expand(ftree *tree) {
   struct ftreehead *head;
   struct ftreehole *hole;
   off_t off;
   ftreenode buf[256];

   if(16 != sizeof(ftreenode) || 16 != sizeof(ftreehole) || 16 != sizeof(ftreehead))
      struct_ftreenode_ftreehole_or_ftreehead_is_the_wrong_size();
   memset(buf,0,256*sizeof(ftreenode));
   off=lseek(tree->fd,0,SEEK_END);
   if(off==(off_t)-1)
      return(-1);
   if(off==(off_t)0) {
      head=(ftreehead *)buf;
      hole=(ftreehole *)(buf+1);
      head->root=0;
      head->free=1;
      head->freetail=1;
      head->magic[0]='M';
      head->magic[1]='T';
      head->magic[2]='\xFF';
      ((unsigned char *)hole)[-1]=0;
      hole->prev=0;
      hole->next=0;
      hole->size=254;
   } else {
      head=(ftreehead *)tree->mem;
      hole=(ftreehole *)buf;
      hole->prev=head->freetail;
      hole->next=0;
      hole->size=255;
      ((unsigned char *)tree->mem)[off-1]=0;
      if(head->freetail)
         THOLEI(tree,head->freetail).next=off/sizeof(ftreenode);
      else
         head->free=off/sizeof(ftreenode);
      head->freetail=off/sizeof(ftreenode);
   }
   if(256*sizeof(ftreenode) != write(tree->fd,buf,256*sizeof(ftreenode))) {
      ftruncate(tree->fd,off);
      return(-1);
   }
   ftree_resize(tree);
   return(0);
}

static idx ftree_malloc(ftree *tree,int slen) {
   idx b,i,order,size;
   ftreehole *hole;

   order=1+(slen+sizeof(ftreenode)-3)/sizeof(ftreenode);
   if(order>255)
      goto fail;
   if(!tree->mem && ftree_expand(tree))
      goto fail;
   if(!((ftreehead *)tree->mem)->free && ftree_expand(tree))
      goto fail;
   hole=(ftreehole *)tree->mem;
   i=((struct ftreehead *)tree->mem)->free;
   b=i;
   size=hole[i].size+1;
   while(size<order) {
      if(!hole[i].next) {
         if(ftree_expand(tree))
            goto fail;
         hole=(ftreehole *)tree->mem;
      }
      if(hole[i].next != i+hole[i].size+1) {
         b=hole[i].next;
         size=0;
      }
      i=hole[i].next;
      size+=hole[i].size+1;
   }
   if(size>order) {
      hole[b+order].size=size-order-1;
      hole[b+order].next=hole[i].next;
      hole[b+order].prev=i;
      hole[hole[i].next].prev=b+order;
      hole[i].next=b+order;
      TSIZEI(tree,b+order)=0;
   }
   TSIZEI(tree,b)=order;
   hole[hole[b].prev].next=hole[i].next;
   hole[hole[i].next].prev=hole[b].prev;
   return(b);
fail:
   return(0);
}

static void ftree_collapse(ftree *tree,idx a,idx b) {
   struct ftreehole *hole;
   unsigned char c;

   hole=(ftreehole *)tree->mem;
   if(hole[a].size+hole[b].size<255) {
      hole[hole[b].next].prev=a;
      hole[a].next=hole[b].next;
      hole[a].size+=hole[b].size+1;
   } else if(hole[b].size<255) {
      c=hole[a].size+hole[b].size-254;
      TSIZEI(tree,a+c)=0;
      hole[a+c].prev=a;
      hole[a+c].next=hole[b].next;
      hole[a+c].size=255;
      hole[a].next=a+c;
      hole[a].size=c-1;
   }
}

static void ftree_free(ftree *tree,idx orig) {
   idx i=0;
   ftreehole *hole;

   hole=(ftreehole *)tree->mem;
   if(orig<((ftreehead *)hole)->freetail)
      for(i=orig;TSIZEI(tree,i);i+=TSIZEI(tree,i))
         ;
   hole[orig].prev=hole[i].prev;
   hole[orig].next=i;
   hole[hole[i].prev].next=orig;
   hole[i].prev=orig;
   hole[orig].size=TSIZEI(tree,orig)-1;
   TSIZEI(tree,orig)=0;
   if(i && i==orig+hole[orig].size+1)
      ftree_collapse(tree,orig,i);
   if(hole[orig].prev && orig==hole[orig].prev+hole[hole[orig].prev].size+1)
      ftree_collapse(tree,hole[orig].prev,orig);
   if(tree->size<=256*sizeof(ftreehole))
      return;
   hole=(ftreehole *)tree->mem;
   i=hole[0].prev;
   if(!i)
      return;
   if(hole[i].size != 255)
      return;
   if(tree->size != (i+256)*sizeof(ftreehole))
      return;
   while(hole[i].prev && hole[i].prev==i-256)
      i=hole[i].prev;
   hole[0].prev=hole[i].prev;
   hole[hole[i].prev].next=0;
   ftruncate(tree->fd,i*sizeof(ftreehole));
   ftree_resize(tree);
}

static idx ftree_realloc(ftree *tree,idx orig,idx slen) {
   idx i,new,order;
   ftreehole *hole;

   order=1+(slen+sizeof(ftreenode)-3)/sizeof(ftreenode);
   i=TSIZEI(tree,orig);
   new=orig;
   if(order<i) {
      TSIZEI(tree,orig)=order;
      orig+=order;
      TSIZEI(tree,orig)=i-order;
      ftree_free(tree,orig);
   } else if(order>i) {
      hole=tree->mem;
      new=i;
      if(orig+order<=hole[0].prev)
         while(order>i && !TSIZEI(tree,orig+i))
            i+=hole[orig+i].size+1;
      if(order<=i) {
         hole[hole[orig+new].prev].next=orig+order;
         hole[orig+order].prev=hole[orig+new].prev;
         if(order<i) {
            TSIZEI(tree,orig+order)=0;
            hole[orig+order].next=orig+i;
            hole[orig+order].size=i-order-1;
         }
         return(orig);
      }
/* FIXME: Do we really want to punt without checking for space before orig? */
      new=ftree_malloc(tree,slen);
      if(new) {
         memcpy(&TNODEI(tree,new),&TNODEI(tree,orig),sizeof(ftreenode)*TSIZEI(tree,orig)-1);
         ftree_free(tree,orig);
      }
   }
   return(new);
}

/* FIXME: These should really be atomic memory locks in case of threads */
int ftree_readlock(ftree *tree) {
   if(tree->lock++)
      return(0);
   return(flock(tree->fd,LOCK_SH) || ftree_resize(tree));
}

int ftree_writelock(ftree *tree) {
   if(tree->lock && !tree->writelock)
      return(1);
   tree->writelock++;
   if(tree->lock++)
      return(0);
   return(flock(tree->fd,LOCK_EX) || ftree_resize(tree));
}

int ftree_readunlock(ftree *tree) {
   if(!tree->lock)
      return(1);
   if(!--tree->lock)
      return(flock(tree->fd,LOCK_UN));
   return(0);
}

/* FIXME: Can we downgrade a LOCK_EX into a LOCK_SH without dropping it? */
int ftree_writeunlock(ftree *tree) {
   if(!tree->writelock)
      return(1);
   if(!--tree->writelock)
      msync(tree->mem,tree->size,MS_SYNC|MS_INVALIDATE);
   if(!--tree->lock)
      return(flock(tree->fd,LOCK_UN));
   return(0);
}

ftree *ftree_open(const char *file,int flags) {
   ftree *t;

   t=(ftree *)malloc(sizeof(ftree));
   if(!t)
      goto done;
   t->fd=open(file,O_RDWR|flags,0666);
   if(0>t->fd)
      goto fail_free;
   t->lock=0;
   t->writelock=0;
   t->mem=0;
   t->size=0;
   if(ftree_resize(t))
      goto fail_close;
   if(!t->mem)
      goto done;
   if(t->size<sizeof(ftreehead))
      goto fail_unmap;
   if(!strncmp("MT\xFF",((ftreehead *)t->mem)->magic,3))
      goto done;
fail_unmap:
   munmap(t->mem,t->size);
fail_close:
   close(t->fd);
fail_free:
   free(t);
   t=0;
done:
   return(t);
}

int ftree_close(ftree *tree) {
   int retval=-1;

   if(tree->mem && munmap(tree->mem,tree->size))
      goto fail;
   tree->mem=0;
   tree->size=0;
   if(0>tree->fd || close(tree->fd))
      goto fail;
   free(tree);
   retval=0;
fail:
   return(retval);
}

static idx ftreenode_match_push(idx node,struct match *match) {
   idx *tmp;

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

   return(0);
}

static idx ftreenode_match(ftreenode *tree,idx node,const char *s,struct match *match) {
   int i;
   idx tmp;

   for(;node;node=tree[node].next) {
      if(tree[node].s[0]) {
         for(i=0;tree[node].s[i];i++)
            if(tree[node].s[i] != s[i])
               break;
         if(!i)
            continue;
         if(!tree[node].s[i]) {
            if(match) {
               match->len+=i;
               if(ftreenode_match_push(node,match))
                  goto fail;
            }
            if(tree[node].child) {
               tmp=ftreenode_match(tree,tree[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=tree[tmp].next)
            if(!tree[tmp].s[0])
               break;
         if(!tmp)
            goto fail;
         node=ftreenode_match(tree,tmp,s,match);
         goto done;
      } else if(FTREE_WILDCARD) {
         if(match) {
            if(s[0] != FTREE_WILDCARD)
               continue;
            match->len++;
            if(ftreenode_match_push(node,match))
               goto fail;
            if(!tree[node].child)
               goto done;
            tmp=ftreenode_match(tree,tree[node].child,&s[1],match);
            if(tmp)
               node=tmp;
            goto done;
         }
         if(!tree[node].child) {
            if(match) {
               match->len+=strlen(s);
               if(ftreenode_match_push(node,match))
                  goto fail;
            }
            goto done;
         }
         for(i=0;s[i];i++) {
            tmp=ftreenode_match(tree,tree[node].child,&s[i],match);
            if(tmp) {
               node=tmp;
               if(match) {
                  match->len+=i;
                  if(ftreenode_match_push(node,match))
                     goto fail;
               }
               goto done;
            }
         }
      }
   }
fail:
   node=0;
done:
   return(node);
}

static idx ftreenode_makerem(ftree *tree,const char *s,ftreevalue value) {
   int i;
   idx node=0,tmp=0,tmp2;

   while(s[0]) {
      for(i=0;s[i] && s[i] != FTREE_WILDCARD;i++)
         ;
      tmp2=ftree_malloc(tree,i);
      if(!tmp2)
         goto fail;
      TNODEI(tree,tmp2).child=0;
      TNODEI(tree,tmp2).next=0;
      if(node) {
         TNODEI(tree,tmp).child=tmp2;
         tmp=TNODEI(tree,tmp).child;
      } else
         node=tmp=tmp2;
      strncpy(TNODEI(tree,tmp2).s,s,i);
      TNODEI(tree,tmp2).s[i]='\0';
      s+=(i?i:1);
      TNODEI(tree,tmp2).value=(s[0]?0:value);
   }
   return(node);
fail:
   while(node) {
      tmp=node;
      node=TNODEI(tree,node).child;
      ftree_free(tree,tmp);
   }
   return(0);
}

static idx ftreenode_break(ftree *tree,idx node,const char *s,ftreevalue value) {
   idx foo,bar=0;
   int i,j;

   while(1) {
      for(i=0;s[i]==TNODEI(tree,node).s[i];i++)
         ;
      if(!i)
         goto next;
      j=strlen(&TNODEI(tree,node).s[i]);
      foo=ftree_malloc(tree,j);
      if(!foo)
         goto fail;
      if(s[i]) {
         bar=ftreenode_makerem(tree,&s[i],value);
         if(!bar) {
            ftree_free(tree,foo);
            goto fail;
         }
      }
      strcpy(TNODEI(tree,foo).s,&TNODEI(tree,node).s[i]);
      if(!ftree_realloc(tree,node,i)) {
         ftree_free(tree,foo);
         while(bar) {
            foo=bar;
            bar=TNODEI(tree,bar).next;
            ftree_free(tree,foo);
         }
         goto fail;
      }
      TNODEI(tree,node).s[i]='\0';
      TNODEI(tree,foo).value=TNODEI(tree,node).value;
      TNODEI(tree,node).value=0;
      if(!s[i])
         TNODEI(tree,node).value=value;
      TNODEI(tree,foo).child=TNODEI(tree,node).child;
      TNODEI(tree,node).child=foo;
      TNODEI(tree,foo).next=bar;
      goto done;
next:
      if(TNODEI(tree,node).next)
         node=TNODEI(tree,node).next;
      else {
         TNODEI(tree,node).next=ftreenode_makerem(tree,s,value);
         node=TNODEI(tree,node).next;
         goto done;
      }
   }

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

int ftree_add(ftree *tree,const char *s,ftreevalue value) {
   idx node,tmp;
   struct match match;

   if(!value)
      return(1);
   match.len=0;
   match.nodeslen=0;
   match.nodes=0;
   if(ftree_writelock(tree))
      goto fail;
   if(!tree->mem || !TROOT(tree)) {
      node=ftreenode_makerem(tree,s,value);
      if(!node)
         goto fail;
      TROOT(tree)=node;
      goto good;
   }
   node=ftreenode_match((ftreenode *)tree->mem,TROOT(tree),s,&match);
   free(match.nodes);
   if(!node) {
      if(!ftreenode_break(tree,TROOT(tree),s,value))
         goto fail;
   } else if(!s[match.len]) {
      if(TNODEI(tree,node).value)
         goto fail;
      TNODEI(tree,node).value=value;
   } else if(TNODEI(tree,node).child && TNODEI(tree,TNODEI(tree,node).child).s[0]) {
      if(!ftreenode_break(tree,TNODEI(tree,node).child,&s[match.len],value))
         goto fail;
   } else {
      tmp=ftreenode_makerem(tree,&s[match.len],value);
      if(!tmp)
         goto fail;
      TNODEI(tree,tmp).next=TNODEI(tree,node).child;
      TNODEI(tree,node).child=tmp;
   }
good:
   ftree_writeunlock(tree);
   return(0);
fail:
   ftree_writeunlock(tree);
   return(1);
}

ftreevalue ftree_del(ftree *tree,const char *s) {
   int i,j;
   idx parent,stay,go,tmp;
   struct match match;
   ftreevalue retval=0;

   match.len=0;
   match.nodeslen=0;
   match.nodes=0;
   parent=stay=go=0;
   if(ftree_writelock(tree))
      goto done;
   if(!tree->mem || !TROOT(tree))
      goto done;
   ftreenode_match((ftreenode *)tree->mem,TROOT(tree),s,&match);
   if(!match.nodeslen)
      goto done;
   if(match.len != strlen(s))
      goto done;
   tmp=match.nodes[match.nodeslen-1];
   if(TNODEI(tree,tmp).child) {
      if(TNODEI(tree,tmp).value) {
         retval=TNODEI(tree,tmp).value;
         TNODEI(tree,tmp).value=0;
      }
      goto done;
   }
   for(i=match.nodeslen-2;i>=0;i--) {
      if(TNODEI(tree,match.nodes[i]).value || TNODEI(tree,TNODEI(tree,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(TNODEI(tree,TROOT(tree)).next) {
         go=match.nodes[0];
         if(TROOT(tree)==go)
            TROOT(tree)=TNODEI(tree,go).next;
         else {
            for(stay=TROOT(tree);go != TNODEI(tree,stay).next;stay=TNODEI(tree,stay).next)
               ;
            TNODEI(tree,stay).next=TNODEI(tree,go).next;
         }
      } else {
         go=TROOT(tree);
         TROOT(tree)=0;
      }
      goto nukeit;
   }
   if(TNODEI(tree,stay).child==go)
      TNODEI(tree,stay).child=TNODEI(tree,go).next;
   else if(TNODEI(tree,TNODEI(tree,stay).child).next==go)
      TNODEI(tree,TNODEI(tree,stay).child).next=TNODEI(tree,go).next;
   else {
      for(stay=TNODEI(tree,TNODEI(tree,stay).child).next;go != TNODEI(tree,stay).next;stay=TNODEI(tree,stay).next)
         ;
      TNODEI(tree,stay).next=TNODEI(tree,go).next;
      goto nukeit;
   }
   if(!TNODEI(tree,stay).child)
      goto nukeit;
   if(TNODEI(tree,TNODEI(tree,stay).child).next)
      goto nukeit;
   if(!TNODEI(tree,stay).s[0] || !TNODEI(tree,TNODEI(tree,stay).child).s[0])
      goto nukeit;
   if(TNODEI(tree,stay).value)
      goto nukeit;
   i=strlen(TNODEI(tree,stay).s);
   j=strlen(TNODEI(tree,TNODEI(tree,stay).child).s);
   tmp=ftree_realloc(tree,stay,i+j);
   if(!tmp)
      goto nukeit;
   strcat(TNODEI(tree,tmp).s,TNODEI(tree,TNODEI(tree,tmp).child).s);
   if(tmp != stay) {
      if(parent) {
         if(TNODEI(tree,parent).child==stay) {
            TNODEI(tree,parent).child=tmp;
            parent=0;
         } else
            parent=TNODEI(tree,parent).child;
      } else {
         if(TROOT(tree)==stay)
            TROOT(tree)=tmp;
         else
            parent=TROOT(tree);
      }
      if(parent) {
         while(stay != TNODEI(tree,parent).next)
            parent=TNODEI(tree,parent).next;
         TNODEI(tree,parent).next=tmp;
      }
      stay=tmp;
   }
   parent=TNODEI(tree,stay).child;
   TNODEI(tree,stay).child=TNODEI(tree,parent).child;
   TNODEI(tree,stay).value=TNODEI(tree,parent).value;
   ftree_free(tree,parent);
nukeit:
   while(go) {
      retval=TNODEI(tree,go).value;
      stay=TNODEI(tree,go).child;
      ftree_free(tree,go);
      go=stay;
   }
done:
   free(match.nodes);
   ftree_writeunlock(tree);
   return(retval);
}

ftreevalue ftree_match(ftree *tree,const char *s) {
   ftreevalue value=0;
   idx node;

   if(ftree_readlock(tree))
      goto done;
   if(tree->mem) {
      node=ftreenode_match((ftreenode *)tree->mem,TROOT(tree),s,0);
      if(node)
         value=TNODEI(tree,node).value;
   }
   ftree_readunlock(tree);
done:
   return(value);
}

ftreevalue ftree_change(ftree *tree,const char *s,ftreevalue new) {
   idx node;
   struct match match;
   ftreevalue old=0;

   match.len=0;
   match.nodeslen=0;
   match.nodes=0;
/* FIXME: How about a readlock-only, potentially race-prone version? */
   if(ftree_writelock(tree))
      goto fail;
   if(!tree->mem)
      goto fail;
   node=ftreenode_match((ftreenode *)tree->mem,TROOT(tree),s,&match);
   if(node) {
      old=TNODEI(tree,node).value;
      TNODEI(tree,node).value=new;
   }
   free(match.nodes);
fail:
   ftree_writeunlock(tree);
   return(old);
}

size_t ftree_getsize(ftree *tree) {
   size_t size=0;

   if(!ftree_readlock(tree))
      size=tree->size;
   ftree_readunlock(tree);
   return(size);
}

static int ftreenode_dump(ftreenode *base,idx node,int (*func)(const char *,int,ftreevalue),int depth) {
   while(node) {
      if((*func)(base[node].s,depth,base[node].value))
         return(1);
      if(base[node].child)
         if(ftreenode_dump(base,base[node].child,func,depth+1))
            return(1);
      node=base[node].next;
   }
   return(0);
}

int ftree_dump(ftree *tree,int (*func)(const char *,int,ftreevalue)) {
   int i=0;

   if(!ftree_readlock(tree) && tree->size && ((struct ftreehead *)tree->mem)->root)
      i=ftreenode_dump((ftreenode *)tree->mem,((struct ftreehead *)tree->mem)->root,func,0);
   ftree_readunlock(tree);
   return(i);
}

struct fulldump {
   char *s;
   struct fulldump *next;
};

static int ftreenode_dumpfullnow(struct fulldump *base,int (*func)(const char *,ftreevalue),ftreevalue value) {
   char *s;
   int i,j;
   struct fulldump *fd;

   for(fd=base,i=0;fd;fd=fd->next)
      i+=strlen(fd->s);
   s=(char *)malloc(i+1);
   if(!s)
      return(-1);
   s[i]='\0';
   for(fd=base;fd;fd=fd->next) {
      j=strlen(fd->s);
      i-=j;
      memcpy(&s[i],fd->s,j);
   }
   i=(*func)(s,value);
   free(s);
   return(i);
}
   
static int ftreenode_dumpfull(ftreenode *base,idx node,int (*func)(const char *,ftreevalue),struct fulldump *next) {
   struct fulldump fd;

   fd.next=next;
   while(node) {
      fd.s=base[node].s;
      if(base[node].value && ftreenode_dumpfullnow(&fd,func,base[node].value))
         return(1);
      if(base[node].child)
         if(ftreenode_dumpfull(base,base[node].child,func,&fd))
            return(1);
      node=base[node].next;
   }
   return(0);
}

int ftree_dumpfull(ftree *tree,int (*func)(const char *,ftreevalue)) {
   int i=0;

   if(!ftree_readlock(tree) && tree->size && ((struct ftreehead *)tree->mem)->root)
      i=ftreenode_dumpfull((ftreenode *)tree->mem,((struct ftreehead *)tree->mem)->root,func,0);
   ftree_readunlock(tree);
   return(i);
}