spiceparser/list.h

   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.h  list module, for array-type list operators
  22
  23    Conrad Ziesler
  24 */
  25
  26 #ifndef __LIST_H__
  27 #define __LIST_H__
  28
  29 #ifndef __BITLIST_H__
  30 #include "bitlist.h"
  31 #endif
  32
  33 typedef struct list_st
  34 {
  35   int q; /* qty or current index */
  36   int s; /* size of item */
  37   int m; /* max alloc */
  38   int mode; /* list access mode */
  39   void *d;
  40 }list_t;
  41
  42
  43 typedef struct listx_st
  44 {
  45   list_t list;
  46   bitlist_t *bitmap;
  47 }listx_t;
  48
  49
  50 #define LIST_INITDATA { 0, 0, 0, 0, NULL }
  51 #define LIST_MODECHUNK 0x000fff  /* mask for chunck bits */
  52 #define LIST_DEFMODE   0x000010  /* reallocate every 16 */
  53 #define LIST_EXPMODE   0x001fff  /* double size per allocation (for exponential growth lists) */
  54 #define LIST_FIXEDMODE 0x002000  /* flag error if we exceed hinted size */
  55 #define LIST_UNITMODE 0x01  /* reallocate every 1 */
  56 #define LIST_USERFLAG1 0x010000
  57 #define LIST_USERFLAG2 0x020000
  58 #define LIST_USERMASK  0xff0000
  59 #define list_getuser(l)    (((l)->mode&LIST_USERMASK)>>16)
  60 #define list_putuser(l,u)  (l)->mode=((u<<16)&LIST_USERMASK)
  61 #define list_setuser(l,u)  list_putuser((l),list_getuser((l))|(u))
  62 #define list_clearuser(l,u) list_putuser((l),list_getuser((l))&(~u))
  63 #define list_iterate(l,i,p) for((p)=list_data((l),(i)=0);(p)!=NULL;(p)=list_data((l),++(i)))
  64 #define list_iterate_(l,i)  for((i)=0;(i)<((l)->q);(i)++)
  65 #define list_iterate_backwards(l,i,p) for((p)=list_data((l),(i)=((l)->q-1));(p)!=NULL;(p)=list_data((l),--(i)))
  66 #define list_lastitem(l)  (list_data((l),(l)->q-1))
  67 #define list_firstitem(l) (list_data((l),0))
  68 #define list_qty(l)       ((l)->q)
  69 #define list_sizeof(l)    ((l)->s)
  70
  71 /* listx routines allow for allocating and freeing list elements */
  72 void listx_init(listx_t *l, int size, int mode);
  73 int listx_qty(listx_t *l);
  74 void *listx_data(listx_t *l, int cell);
  75 void listx_empty(listx_t *l);
  76 void listx_free(listx_t *l, int cell);
  77 int listx_alloc(listx_t *l);
  78 void *listx_vdata(listx_t *l, int cell);
  79
  80 #define listx_iterate(l,i,p) for((p)=list_data(&((l)->list),(i)=0);(p)!=NULL;(p)=list_data(&((l)->list),++(i))) if(bitlist_test((l)->bitmap,i))
  81
  82 /* #define list_data(l,i)   ((void *)( (((i)<((l)->q))&&((i)>=0))? (((char *)((l)->d))+((l)->s * (i))):NULL))
  83
  84 #define list_data(l,i) list_data_func(l,i)
  85  */
  86
  87 static inline void *list_data(const list_t *l, int i)
  88 {
  89   if((i<l->q)&&(i>=0))
  90     return ((char *)(l->d))+(l->s * i);
  91   return NULL;
  92 }
  93
  94 static inline void *list_vdata(const list_t *l, int i)
  95 {
  96   if((i<l->q)&&(i>=0))
  97     return ((char *)(l->d))+(l->s * i);
  98   assert(0&&"invalid index into list");
  99 }
 100
 101 int list_element_dup(list_t *l, int from, int to);
 102 int list_remove(list_t *l, int i, void *save);
 103 void list_empty(list_t *l);
 104 void list_init(list_t *l, int s, int mode);
 105 void list_hint(list_t *l, int max);
 106 void *list_next(list_t *l);
 107 void *list_prev(list_t *l);
 108 void *list_block_next(list_t *l, int qty);
 109 void inline *list_data_func(list_t *l, int i);
 110 int list_contains(list_t *l, void *d);
 111 int list_add(list_t *l, void *d);
 112 int list_index(list_t *l, void *p);
 113 void list_sort(list_t *l, int (*cmp)(const void *a, const void *b));
 114 void list_start(list_t *l);
 115 void list_copyfrom(list_t *newl, list_t *oldl);
 116 void list_shrink(list_t *l);
 117 int list_nextz(list_t *l);
 118 void list_dup(list_t *newl, list_t *oldl);
 119 void list_reset(list_t *l);
 120 void list_append(list_t *growing, list_t *copyfrom);
 121 int list_stdlib_bsearch(list_t *l, void *key, int (*cmp)(const void *a, const void *b));
 122
 123 typedef struct sort_func_st
 124 {
 125   list_t *tosort;
 126   int (*cmpf)(struct sort_func_st *s, void *a, void *b);
 127   int aiskey; /* if element a is a key and not a normal element */
 128   void *user;
 129 }sort_func_t;
 130
 131 int list_bsearch(sort_func_t *sf, void *key);
 132
 133 /* this is in sort.c */
 134 void list_qsort (sort_func_t *sf);
 135
 136
 137
 138 #endif