spiceparser/list_search.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_search.c,  container supporting mulitple sorted searches
  22    Conrad Ziesler
  23 */
  24
  25 #include "debug.h"
  26 #include "list_search.h"
  27
  28 void list_search_init(list_search_t *lp, int size, int mode)
  29 {
  30   list_init(&(lp->list),size,mode);
  31   list_init(&(lp->psearch),sizeof(list_psearch_t),LIST_DEFMODE);
  32 }
  33
  34
  35 void list_search_empty(list_search_t *lp)
  36 {
  37   int i;
  38   list_psearch_t *p;
  39   list_empty(&(lp->list));
  40   list_iterate(&(lp->psearch),i,p)
  41     {
  42       if(p->isearchdata!=NULL)free(p->isearchdata);
  43     }
  44   list_empty(&(lp->list));
  45 }
  46
  47
  48
  49 int list_search_addrule(list_search_t *lp, int (*cmpf)(const void *user, const void *a, const void *b),void *user)
  50 {
  51   list_psearch_t t;
  52   t.isearchdata=NULL;
  53   t.is_sorted=0;
  54   t.user=user;
  55   t.cmpf=cmpf;
  56   t.len=0;
  57   return list_add(&(lp->psearch),&t);
  58 }
  59
  60 int list_search_findnext(list_search_iterator_t *sip)
  61 {
  62   list_psearch_t *psp;
  63   int id;
  64   void *pa,*pb;
  65
  66   id=sip->last_id+1;
  67   if(sip->sp==NULL)return -1;
  68   if(sip->last_id<0)return -1;
  69   if(id>=sip->sp->list.q)return -1; /* last one, can't be any more */
  70   psp=list_data(&(sip->sp->psearch),sip->which);
  71   if(psp==NULL)return -1;
  72   if(!psp->is_sorted)return -1;
  73   if(psp->len!=sip->sp->list.q) return -1;
  74
  75   pa=list_data(&(sip->sp->list),psp->isearchdata[sip->last_id]);
  76   pb=list_data(&(sip->sp->list),psp->isearchdata[id]);
  77   if((pa!=NULL) && (pb!=NULL))
  78     if( psp->cmpf(psp->user,pa,pb)==0) /* yes we match previous */
  79       {
  80         sip->last_id=id;
  81         return psp->isearchdata[id];
  82       }
  83   return -1;
  84 }
  85
  86
  87
  88
  89 static list_t *debug_cmpf_list=NULL;
  90 static  int (*debug_psp_cmpf)(const void *user ,const void *a, const void *b);
  91 static void *debug_user;
  92
  93 int debug_cmpf(const void *a, const void *b)
  94 {
  95   const int *ap=a,*bp=b;
  96   return debug_psp_cmpf(debug_user,list_vdata(debug_cmpf_list,ap[0]),list_vdata(debug_cmpf_list,bp[0]));
  97 }
  98
  99 void list_search_qsort_debug (list_search_t *lsp, list_psearch_t *psp)
 100 {
 101   debug_cmpf_list=&(lsp->list);
 102   debug_psp_cmpf=psp->cmpf;
 103   debug_user=psp->user;
 104   qsort(psp->isearchdata,psp->len,sizeof(int),debug_cmpf);
 105 }
 106
 107
 108 int list_search_find(list_search_t *lp, int which, void *key, list_search_iterator_t *sip)
 109 {
 110   list_psearch_t *psp;
 111   int i,l,u,idx, res;
 112   char *list_base=lp->list.d;
 113   int base_size=lp->list.s;
 114   int base_qty=lp->list.q;
 115   int *base;
 116
 117   if(sip!=NULL)
 118     {
 119       sip->sp=lp;
 120       sip->which=which;
 121       sip->last_id=-1;
 122     }
 123
 124   if(base_size==0)return -1;
 125   if(base_qty<=0)return -1;
 126
 127
 128   psp=list_data(&(lp->psearch),which);
 129   assert(psp!=NULL);
 130
 131   if(psp->len!=base_qty)psp->is_sorted=0; /* guard against changes */
 132
 133   if(!psp->is_sorted)
 134     {
 135       if(psp->isearchdata!=NULL)free(psp->isearchdata);
 136       psp->isearchdata=malloc(sizeof(int)*base_qty);
 137       assert(psp->isearchdata!=NULL);
 138       psp->len=base_qty;
 139       for(i=0;i<base_qty;i++) psp->isearchdata[i]=i;
 140       list_search_qsort_debug(lp,psp);
 141       psp->is_sorted=1;
 142
 143     }
 144
 145   base=psp->isearchdata;
 146   l =0;
 147   u = base_qty;
 148
 149   if(base==NULL)return -1;
 150
 151   while (l < u)
 152     {
 153       idx = (l + u) >> 1;
 154       res= psp->cmpf(psp->user, key, (void *)(list_base+ (base_size*base[idx])));
 155       if (res <= 0)
 156         u = idx;
 157       else if (res > 0)
 158         l = idx + 1;
 159      }
 160   if(l>=base_qty) return -1;
 161   if(l<0)return -1;
 162   res= psp->cmpf(psp->user, key, (void *)(list_base+ (base_size*base[l])));
 163   if(res==0)
 164     { if(sip!=NULL)sip->last_id=l;  return base[l]; }
 165   return -1;
 166 }
 167
 168
 169
 170 void list_search_resort(list_search_t *lp)
 171 {
 172   int i;
 173   list_psearch_t *ps;
 174   list_iterate(&(lp->psearch),i,ps)
 175     {
 176       ps->is_sorted=0;
 177       ps->len=0;
 178       if(ps->isearchdata!=NULL)free(ps->isearchdata);
 179     }
 180 }
 181
 182