spiceparser/list.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 /* list.c  list module, for array-type list operators
  22
  23    Conrad Ziesler
  24 */
  25
  26 #include "debug.h"
  27 #include "list.h"
  28
  29 /* listx, supports allocation and freeing of list elements */
  30
  31 void listx_init(listx_t *l, int size, int mode)
  32 {
  33   list_init(&(l->list),size,mode);
  34   l->bitmap=NULL;
  35 }
  36
  37 int listx_alloc(listx_t *l)
  38 {
  39   int cell;
  40   if(l->bitmap==NULL)
  41     {
  42       cell=list_nextz(&(l->list));
  43       l->bitmap=bitlist_new(l->list.m);
  44       assert(l->bitmap!=NULL);
  45       bitlist_set(l->bitmap,cell);
  46       return cell;
  47     }
  48   else
  49     {
  50       cell=bitlist_scan(l->bitmap,SCAN_FORWARD|SCAN_CLEAR);
  51       if((cell<0)||(cell>=l->list.q))
  52         cell=list_nextz(&(l->list));
  53
  54       if(l->list.m != l->bitmap->qty )
  55         l->bitmap=bitlist_resize(l->bitmap,l->list.m);
  56
  57       bitlist_set(l->bitmap,cell);
  58       return cell;
  59     }
  60   return -1;
  61 }
  62
  63 void listx_free(listx_t *l, int cell)
  64 {
  65   bitlist_clear(l->bitmap,cell);
  66   memset(list_data(&(l->list),cell),0,l->list.s);
  67 }
  68 void listx_empty(listx_t *l)
  69 {
  70   list_empty(&(l->list));
  71   if(l->bitmap!=NULL)bitlist_free(l->bitmap);
  72   l->bitmap=NULL;
  73 }
  74
  75 void *listx_vdata(listx_t *l, int cell)
  76 {
  77   if(bitlist_test(l->bitmap,cell))
  78     return list_data(&(l->list),cell);
  79   return NULL;
  80 }
  81
  82 void *listx_data(listx_t *l, int cell)
  83 {
  84   return list_data(&(l->list),cell);
  85 }
  86
  87 int listx_qty(listx_t *l)
  88 {
  89   return list_qty(&(l->list));
  90 }
  91
  92
  93 void list_shrink(list_t *l)
  94 {
  95   list_hint(l,l->q);
  96 }
  97
  98
  99 void list_empty(list_t *l)
 100 {
 101   if(l->d!=NULL)
 102     free(l->d);
 103   l->q=0;
 104   l->m=0;
 105   l->d=NULL;
 106 }
 107
 108 void list_init(list_t *l, int s, int mode)
 109 {
 110   static const list_t id=LIST_INITDATA;
 111   if(l!=NULL)
 112     { *l=id; l->s=s; l->mode=mode; l->q=0; l->m=0; }
 113 }
 114
 115 void list_hint(list_t *l, int max)
 116 {
 117
 118   if(max==0)
 119     {
 120       if(l->d!=NULL)
 121         free(l->d);
 122       l->d=NULL;
 123       l->m=0;
 124       l->q=0;
 125     }
 126   else
 127   {
 128     if(l->s!=0)
 129       l->d=realloc(l->d,(l->m=max)*l->s);
 130
 131     assert(l->d!=NULL);
 132   }
 133 }
 134
 135
 136 void list_hint_grow(list_t *l, int add_q)
 137 {
 138   int qm=l->q+add_q;
 139   if(l->m < qm )
 140     l->d=realloc(l->d,(l->m=qm)*l->s);
 141 }
 142
 143 void inline *list_data_func(list_t *l, int i)
 144 {
 145   if((i<l->q)&&(i>=0))
 146     return ((char *)(l->d))+(l->s * i);
 147   return NULL;
 148 }
 149
 150 void *list_next(list_t *l)
 151 {
 152   int v;
 153
 154   if(l->q>=l->m)
 155     {
 156       if( (l->mode & LIST_FIXEDMODE)!=0)
 157         { assert(0); return NULL; }
 158
 159       if( (l->mode & LIST_EXPMODE)!=0)
 160         {
 161           if(l->s<(1024*1024))
 162             {
 163               if((l->m*l->s)>(1024*1024*16))
 164                 list_hint(l,l->m+((1024*1024*16)/l->s));
 165               else
 166                 list_hint(l,2*( (l->m==0)?16:l->m) );
 167             }
 168           else list_hint(l,l->m+1);
 169         }
 170       else
 171         {
 172           v=l->m+(l->mode&LIST_MODECHUNK);
 173           if(v<l->m)v=l->m+1;
 174           list_hint(l, v);
 175         }
 176     }
 177   return ((char *)(l->d))+(l->s * l->q++);
 178 }
 179
 180 void *list_prev(list_t *l)
 181 {
 182   if(l->q>0)
 183     {
 184       return ((char *)(l->d))+(l->s * --(l->q));
 185     }
 186   return NULL;
 187 }
 188
 189 void *list_block_next(list_t *l, int qty)
 190 {
 191   void *r;
 192   if((l->q+qty)>=l->m)
 193     list_hint(l, l->q+qty);
 194
 195   r=((char*)l->d)+(l->s*l->q);
 196   l->q+=qty;
 197   return r;
 198 }
 199
 200
 201
 202
 203 int list_contains(list_t *l, void *d)
 204 {
 205   int i;
 206   for(i=0;i<l->q;i++)
 207     if(memcmp(d,list_data(l,i),l->s)==0)
 208       return i;
 209   return -1;
 210 }
 211
 212 int list_add(list_t *l, void *d)
 213 {
 214   void *p; int i;
 215   i=l->q;
 216   p=list_next(l);
 217   memcpy(p,d,l->s);
 218   return i;
 219 }
 220
 221 int list_nextz(list_t *l)
 222 {
 223   int i;
 224   void *p;
 225   i=l->q;
 226   p=list_next(l);
 227   memset(p,0,l->s);
 228   return i;
 229 }
 230
 231 int list_index(list_t *l, void *p)
 232 {
 233   if( p >= (void *) ((((char *)(l->d))+(l->s*l->q)))) return -1;
 234   if( p <  l->d) return -1;
 235   return  (((char *)p)-((char *)(l->d)))/l->s;
 236 }
 237
 238 int list_stdlib_bsearch(list_t *l, void *key, int (*cmp)(const void *a, const void *b))
 239 {
 240   void *p= bsearch(key,l->d, l->q,l->s,cmp);
 241   if(p==NULL)return -1;
 242   return list_index(l,p);
 243 }
 244
 245 void list_sort(list_t *l, int (*cmp)(const void *a, const void *b))
 246 {
 247   qsort(l->d,l->q,l->s,cmp);
 248 }
 249
 250 void list_start(list_t *l)
 251 {
 252   l->q=0;
 253 }
 254
 255
 256 int list_remove(list_t *l, int i, void *save)
 257 {
 258   void *p;
 259   if(i>=l->q)return 1;
 260   if(i<0)return 1;
 261   p=list_data(l,i);
 262   if(save!=NULL)memcpy(save,p,l->s);
 263   l->q--;
 264   if(l->q>i)
 265     memmove(p,((char *)p)+l->s,(l->q-i)*l->s);
 266
 267   return 0;
 268 }
 269
 270 void list_copyfrom(list_t *newl, list_t *oldl)
 271 {
 272
 273   list_t id=LIST_INITDATA;
 274   if(newl!=NULL)
 275     { *newl=id; newl->s=oldl->s; newl->mode=oldl->mode; newl->q=0; newl->m=0; }
 276 }
 277
 278 void list_dup(list_t *newl, list_t *oldl)
 279 {
 280   void *d;
 281   list_copyfrom(newl,oldl);
 282   list_hint(newl,oldl->q);
 283   d=list_block_next(newl,oldl->q);
 284   memcpy(d,oldl->d,oldl->s*oldl->q);
 285 }
 286
 287 void list_append(list_t *growing, list_t *copyfrom)
 288 {
 289   void *d;
 290   if(copyfrom==NULL)return;
 291   assert(growing->s==copyfrom->s);
 292   if(copyfrom->q==0)return;
 293   list_hint(growing,growing->q+copyfrom->q);
 294   d=list_block_next(growing,copyfrom->q);
 295   memcpy(d,copyfrom->d,copyfrom->s*copyfrom->q);
 296 }
 297
 298
 299 int list_element_dup(list_t *l, int from, int to)
 300 {
 301   void *a,*b;
 302   if( (to>l->q) || (to<0) || (from>=l->q) || (from<0) )return 1;
 303   if(to==l->q) list_next(l);
 304   a=list_data(l,to);
 305   b=list_data(l,from);
 306   assert((a!=NULL)&&(b!=NULL));
 307   memcpy(a,b,l->s);
 308   return 0;
 309 }
 310
 311 void list_reset(list_t *l)
 312 {
 313   l->q=0;
 314 }
 315
 316
 317 #include <stdio.h>
 318
 319 int list_bsearch(sort_func_t *sf, void *key)
 320 {
 321   int l,u,idx, res;
 322   char *base=sf->tosort->d;
 323   void *p;
 324   int size=sf->tosort->s;
 325
 326   if(size==0)return -1;
 327   if(sf->tosort->q==0)return -1;
 328   if(base==NULL)return -1;
 329
 330   sf->aiskey=1;
 331   l =0;
 332   u = sf->tosort->q -1 ;
 333
 334   res= sf->cmpf(sf,key,base);
 335   idx= sf->cmpf(sf,key,(void *)(((const char *)base)+((u-1)*size)));
 336   if(0)fprintf(stderr,"list_bsearch, cmpf(e 0)=%i cmpf(e %i)=%i  ",res,u-1,idx);
 337
 338   while (l < u)
 339     {
 340       idx = (l + u) / 2;
 341       p = (void *) (((const char *) base) + (idx * size));
 342       res = sf->cmpf (sf, key, p);
 343       if (res <= 0) /* if we happen to hit the element, pretend we overshot, we want the first element of key */
 344         u = idx;
 345       else if (res > 0)
 346         l = idx + 1;
 347      }
 348   res=-1;
 349   if(sf->tosort->q>0)
 350     {
 351       p = (void *) (((const char *) base) + (l * size));
 352       res = sf->cmpf (sf,key, p);
 353       if(0)fprintf(stderr," l=%i u=%i res=%i\n",l,u,res);
 354       if(res==0)
 355         return l;
 356       return -1;
 357     }
 358   if(0)fprintf(stderr,"no elements\n");
 359   return -1;
 360 }
 361