spiceparser/mergedup.c

   1 /********************
   2     This file is part of the software library CADLIB written by Conrad Ziesler
   3     Copyright 2003, Conrad Ziesler, all rights reserved.
   4
   5 *************************
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19
  20 ******************/
  21 /* mergedup.c  -> code to find and merge common entities,
  22                   works in nlogn time, for general entities
  23
  24 Conrad Ziesler
  25 */
  26
  27 #include "debug.h"
  28 #include "mergedup.h"
  29
  30
  31
  32
  33 mergedup_t *mergedup_alloc(int q, int qs)
  34 {
  35   mergedup_t *m;
  36   int es=sizeof(sortlist_t)+qs-1;
  37
  38   m=malloc(sizeof(mergedup_t) +  (es * q) + ((q>>3)+2));
  39   assert(m!=NULL);
  40   m->flb=(q>>3)+2;
  41   m->qs=qs;
  42   m->es=es;
  43   m->qun=qs/4;
  44   m->run=(qs-(m->qun*4));
  45   m->q=q;
  46   m->i=0;
  47   m->data= (void *) (((char *)m)+sizeof(mergedup_t)) ;
  48   m->freelist= (void *) (((char *)(m->data))+ (es*q) );
  49   m->last=(void *)(m->data);
  50   memset(m->freelist,0,m->flb);
  51   return m;
  52 }
  53
  54
  55 void mergedup_fill(mergedup_t *m, unsigned char *d, int index)
  56 {
  57   int i;
  58   sortlist_t *p;
  59   p= (sortlist_t *) ( (char *)m->data + (m->es*m->i) );
  60   for(i=0;i<m->qs;i++)
  61     p->sorted[i]=d[i];
  62
  63   p->index=index;
  64   m->i++;
  65   assert(m->i<=m->q);
  66 }
  67
  68 static int mergedup__qs=0;
  69
  70 static int comparesorted(const void *a, const void *b)
  71 {
  72   unsigned char *pa=((sortlist_t *)a)->sorted;
  73   unsigned char *pb=((sortlist_t *)b)->sorted;
  74   int i;
  75
  76   if(pa==pb)return 0;
  77   if(pa==NULL)return 1;
  78   if(pb==NULL)return -1;
  79
  80   for(i=0;i<mergedup__qs;i++)
  81     {
  82       if      (pa[i]<pb[i]) return 1;
  83       else if (pa[i]>pb[i]) return -1;
  84     }
  85   return 0;
  86 }
  87
  88
  89 void mergedup_sort(mergedup_t *m)
  90 {
  91   mergedup__qs=m->qs;
  92   comparesorted(NULL,NULL);
  93   qsort(m->data,m->q, m->es, comparesorted);
  94   m->i=0;
  95   m->last=NULL;
  96 }
  97
  98 void mergedup_setbit(mergedup_t *m, int index)
  99 {
 100   int byte,bit;
 101   byte=index>>3;
 102   bit=index-(byte<<3);
 103   assert(byte<m->flb);
 104   m->freelist[byte]|=(1<<bit);
 105 }
 106
 107 int mergedup_testbit(mergedup_t *m, int index)
 108 {
 109   int byte,bit;
 110   byte=index>>3;
 111   bit=index-(byte<<3);
 112   assert(byte<m->flb);
 113   if((m->freelist[byte]&(1<<bit))!=0)return 1;
 114   return 0;
 115 }
 116
 117 int mergedup_visit(mergedup_t *m, int w)
 118 {
 119   sortlist_t *p;
 120   int i;
 121   int v=-1;
 122
 123   if(m->i>=m->q)return -1;
 124
 125   /* get unsorted of current data[m->i] */
 126   p= (sortlist_t *) ( (char *)m->data + (m->es*m->i) );
 127   v=p->index;
 128
 129   if(w) /* w=1, get next item */
 130     {
 131       m->last=p;
 132       m->i++;
 133       return v;
 134     }
 135   else /* w=0, return next same item */
 136     {
 137      if(m->last==NULL)return -1;
 138      for(i=0;i<m->qs;i++)
 139        if(p->sorted[i]!=m->last->sorted[i])return -1;
 140
 141      m->i++;
 142      return v;
 143     }
 144   return -1;
 145 }
 146
 147
 148
 149 void mergedup_free(mergedup_t *m)
 150 {
 151   if(m!=NULL)free(m);
 152 }
 153