asg/list.h

   1 /************************************************************
   2 **
   3 **       COPYRIGHT (C) 1993 UNIVERSITY OF PITTSBURGH
   4 **       COPYRIGHT (C) 1996 GANNON UNIVERSITY
   5 **                  ALL RIGHTS RESERVED
   6 **
   7 **        This software is distributed on an as-is basis
   8 **        with no warranty implied or intended.  No author
   9 **        or distributor takes responsibility to anyone
  10 **        regarding its use of or suitability.
  11 **
  12 **        The software may be distributed and modified
  13 **        freely for academic and other non-commercial
  14 **        use but may NOT be utilized or included in whole
  15 **        or part within any commercial product.
  16 **
  17 **        This copyright notice must remain on all copies
  18 **        and modified versions of this software.
  19 **
  20 ************************************************************/
  21
  22
  23 /* file list.h */
  24 /* ------------------------------------------------------------------------
  25  * List processing facilities based on spl place & route routines (1/90 stf)
  26  * ------------------------------------------------------------------------
  27  */
  28 #include <stdio.h>
  29 #include <string.h>
  30
  31 #ifndef TRUE
  32 #define TRUE 1
  33 #endif
  34 #ifndef FALSE
  35 #define FALSE 0
  36 #endif
  37
  38 /*---- --- for use with these definitions of TRUE and FALSE -------------- */
  39 #define NOT(x) (((x) == FALSE) ? TRUE : FALSE)
  40
  41 #ifdef TCL_WRAPPER
  42   #define malloc Tcl_Alloc
  43   #define calloc(a,b) my_calloc(a, b)                   /* see utility.c */
  44   #define free(a) Tcl_Free((char *)(a))
  45   #define realloc(a,b) Tcl_Realloc((char *)(a), b)
  46
  47   #define fprintf tcl_printf                    /* defined by xcircuit */
  48   #define fflush tcl_stdflush
  49 #endif
  50
  51 /*------------------------------------------------------------------------
  52  * These list processing functions are based on the following two
  53  * data structures:
  54  *------------------------------------------------------------------------*/
  55 typedef struct list_struct list;
  56 typedef struct indexed_list ilist;
  57
  58 struct list_struct
  59 {
  60     int *this;
  61     list *next;
  62 };
  63
  64 struct indexed_list
  65 {
  66     int index;
  67     int *this;
  68     ilist *next;
  69 };
  70
  71 /*------------------------------------------------------------------------ */
  72 /* NOTE:  It is highly advisable to initialize ALL list pointers to NULL,
  73  *        Otherwise, 'random' values that point off into undesirable sections
  74  *        of memory may be become "->next" pointers.  THIS IS A BAD THING. */
  75 /*------------------------------------------------------------------------ */
  76
  77
  78 /* ------------------------------------------------------------------------
  79  * concat_list: append a generic thing to the head of a list.
  80  * works for null lists.
  81  * ------------------------------------------------------------------------
  82  */
  83
  84 extern list *concat_list();
  85 /*    int *e;
  86  *    list *l;   */
  87
  88 /* ------------------------------------------------------------------------
  89  * append_list: append two generic lists together. (<l2> is attached to the
  90  * end of <l1>.  If both lists are null, it returns null.
  91  * ------------------------------------------------------------------------
  92  */
  93
  94 extern list *append_list();
  95 /*    list *l1, *l2;  */
  96
  97 /*---------------------------------------------------------------
  98  * remove_list_element
  99  * cut out a generic list element from the middle of a list
 100  * note the parameter must be the address of the real thing, not
 101  * a copy. so this should be called with the address of a
 102  * subfield ie remove_list_element(&(thing->next))
 103  * both remove_list_element(thing->next)
 104  * and remove_list_element(&thing) (unless thing is global) will not work.
 105  *---------------------------------------------------------------
 106  */
 107 extern void remove_list_element();
 108 /*    list **lptr; */
 109
 110 /*--------------------------------------------------------------------------
 111  * delete_if
 112  * Clip all of the elements of the given list who's ->this field return TRUE
 113  * to the given <testFn>. (Recursive)
 114  *--------------------------------------------------------------------------
 115  */
 116 extern list *delete_if();
 117 /*    list **lptr;       List to work on. */
 118 /*    int (*testFn)();   Should take a single *int as its arg, return TRUE/FALSE */
 119
 120 /* ------------------------------------------------------------------------
 121  * pushnew - add a unique element to the front of a linked list
 122  * ------------------------------------------------------------------------
 123  */
 124 extern void pushnew();
 125 /*    int *what;
 126  *    list **l; */
 127
 128 /* ------------------------------------------------------------------------
 129  * push - add to the front of a linked list
 130  * ------------------------------------------------------------------------
 131  */
 132 extern void push();
 133 /*    int *what;
 134  *    list **l; */
 135
 136 /* ------------------------------------------------------------------------
 137  * pop - (FILO) pop from the front of a linked list
 138  * ------------------------------------------------------------------------
 139  */
 140 extern int *pop();
 141 /*     list **l; */
 142
 143 /* ------------------------------------------------------------------------
 144  * queue - add to the back of a linked list
 145  * ------------------------------------------------------------------------
 146  */
 147 extern void queue();
 148 /*    int *what;
 149  *    list **l; */
 150
 151 /* ------------------------------------------------------------------------
 152  * trans_item - pull from an unknown position within the first list, push
 153  *              onto second list
 154  * ------------------------------------------------------------------------
 155  */
 156 extern int *trans_item();
 157 /*    int *what;
 158  *    list **sList;
 159  *    list **dList; */
 160
 161 /* ------------------------------------------------------------------------
 162  * rem_item - pull from an unknown position within the list
 163  * ------------------------------------------------------------------------
 164  */
 165 extern int *rem_item();
 166 /*    int *what;
 167  *    list **l; */
 168
 169 /* ------------------------------------------------------------------------
 170  * repl_item - pull from an unknown position within the list, replace with
 171  *             given element.
 172  * ------------------------------------------------------------------------
 173  */
 174 extern int *repl_item();
 175 /*    int *what, *new;
 176  *    list *l; */
 177
 178 /* ------------------------------------------------------------------------
 179  * find_item - see if the item is in the list
 180  * ------------------------------------------------------------------------
 181  */
 182 extern list *find_item();
 183 /*    int *what;
 184  *    list *l; */
 185
 186 /* ------------------------------------------------------------------------
 187  * nth - Return the Nth element of the list <l> given that there are at
 188  *       least <n> elements on <l>.
 189  * ------------------------------------------------------------------------
 190  */
 191 extern int *nth();
 192 /*    list *l;  */
 193 /*    int n;    */
 194
 195 /* ------------------------------------------------------------------------
 196  * nth_cdr - Return the list pointer containing the Nth element of the
 197  *       list <l> given that there are at least <n> elements on <l>.
 198  * ------------------------------------------------------------------------
 199  */
 200 extern list *nth_cdr();
 201 /*    list *l;  */
 202 /*    int n;    */
 203
 204 /* ------------------------------------------------------------------------
 205  * list_length
 206  * ------------------------------------------------------------------------
 207  */
 208 extern int list_length();
 209 /*    list *l; */
 210
 211 /* ------------------------------------------------------------------------
 212  * member_p - returns TRUE iff the given pointer returns TRUE when compared
 213  *            with the ->this slot of some list element.
 214  * ------------------------------------------------------------------------
 215  */
 216 extern int member_p();
 217 /*    int *e;           The element to look for */
 218 /*    list *l;          The list to look in  */
 219 /*    int (*testFn)();  The function to test by - <e> is the first arg,
 220                         l-this second (expected to take two *int's as args,
 221                         return TRUE/FALSE */
 222 /* ------------------------------------------------------------------------
 223  * member - returns list pointer to the first item that returns TRUE to
 224  *          the testFn(e, ll->this) query.  Returns NULL otherwise.
 225  * ------------------------------------------------------------------------
 226  */
 227 extern list *member();
 228 /*    int *e;           The element to look for */
 229 /*    list *l;          The list to look in  */
 230 /*    int (*testFn)();  The function to test by - <e> is the first arg,
 231                         l-this second (expected to take two *int's as args,
 232                         return TRUE/FALSE */
 233
 234 /* ------------------------------------------------------------------------
 235  * rcopy_list: make a copy of a list, reversing it for speed/convience
 236  * ------------------------------------------------------------------------
 237  */
 238 extern list *rcopy_list();
 239 /*    list *l;  */
 240
 241 /* ------------------------------------------------------------------------
 242  * copy_list: make a copy of a list, preserving order
 243  * ------------------------------------------------------------------------
 244  */
 245 extern list *copy_list();
 246 /*    list *l; */
 247
 248 /* ------------------------------------------------------------------------
 249  * delete_duplicates  Modify the given list by deleting duplicate elements:
 250  * ------------------------------------------------------------------------
 251  */
 252 extern list *delete_duplicates();
 253 /*    list **l;         */
 254 /*    int (*testFn)();  Should take two *int's as args, return TRUE/FALSE */
 255
 256 /* ------------------------------------------------------------------------
 257  * my_free      wipe this pointer from  memory.
 258  * ------------------------------------------------------------------------
 259  */
 260 extern int *my_free();
 261 /* int *p;  */
 262
 263 /* ------------------------------------------------------------------------
 264  * free_list    wipe this list from memory.  Do not disturb any list elements.
 265  * ------------------------------------------------------------------------
 266  */
 267 extern list *free_list();
 268 /*    list *l; */
 269
 270 /* ------------------------------------------------------------------------
 271  * sort_list (destructive) sort the given list via orderFn.
 272  * ------------------------------------------------------------------------
 273  */
 274 list *sort_list();
 275 /*    list *l;                  */
 276 /*    int (*orderFn)();    Should take two *int's as args, return TRUE/FALSE */
 277                         /* TRUE implies the first element belongs in front of the second */
 278
 279 /* ------------------------------------------------------------------------
 280  * merge_sort_list (destructive) merge sort the given list via orderFn.
 281  * ------------------------------------------------------------------------
 282  */
 283 list *merge_sort_list();
 284 /*    list **l;                 */
 285 /*    int (*orderFn)();    Should take two *int's as args, return TRUE/FALSE */
 286                         /* TRUE implies the first element belongs in front of the second */
 287
 288 /* ------------------------------------------------------------------------
 289  * slow_sort_list (destructive) sort the given list via orderFn.
 290  * ------------------------------------------------------------------------
 291  */
 292 list *slow_sort_list();
 293 /*    list *l;                  */
 294 /*    int (*orderFn)();    Should take two *int's as args, return TRUE/FALSE */
 295                         /* TRUE implies the first element belongs in front of the second */
 296
 297
 298
 299 /*====================================================================================
 300                        INDEXED LIST (ilist) FUNCTIONS:
 301  *====================================================================================*/
 302 /* ------------------------------------------------------------------------
 303  * reverse_copy_ilist: make a copy of an indexed list, inverting the order
 304  *                     while maintaining the original indexing
 305  * ------------------------------------------------------------------------
 306  */
 307 extern ilist *reverse_copy_ilist();
 308 /*    ilist *l; */
 309 /* ------------------------------------------------------------------------
 310  * rcopy_ilist: make a copy of an indexed list, inverting order
 311  * ------------------------------------------------------------------------
 312  */
 313 extern ilist *rcopy_ilist();
 314 /*    ilist *l; */
 315 /* ------------------------------------------------------------------------
 316  * copy_ilist: make a copy of an indexed list, preserving order
 317  * ------------------------------------------------------------------------
 318  */
 319 extern ilist *copy_ilist();
 320 /*    ilist *l; */
 321 /* ------------------------------------------------------------------------
 322  * remove_indexed_element remove (by index) an element from a list structure
 323  * NOTE:  This renumbers the elements following the discovery.
 324  * ------------------------------------------------------------------------
 325  */
 326 extern int *remove_indexed_element();
 327 /*    int indx;
 328  *    ilist **lptr;  */
 329
 330 /* ------------------------------------------------------------------------
 331  * irem_item - pull from an unknown position within an indexed list
 332  *             (no renumbering).  This search is limited by non-NULL <howFar>.
 333  * ------------------------------------------------------------------------
 334  */
 335 extern int *irem_item();
 336 /*  int *what;
 337  *  ilist **l;
 338  *  int howFar;         If != NULL, places a limit on the search */
 339
 340 /* ------------------------------------------------------------------------
 341  * find_indexed_element finds (by index) an element from a list structure
 342  * NOTE:  This returns the list pointer to the requested element.
 343  * ------------------------------------------------------------------------
 344  */
 345 extern ilist *find_indexed_element();
 346 /*    int indx;
 347  *    ilist *lst;  */
 348
 349 /* ------------------------------------------------------------------------
 350  * indexed_list_insert  an element to an indexed list structure.
 351  * ------------------------------------------------------------------------
 352  */
 353 extern int indexed_list_insert();
 354 /*    int *element;
 355  *    int indx;
 356  *    ilist **lptr;  */
 357
 358 /* ------------------------------------------------------------------------
 359  * ordered_ilist_insert  an element to an indexed list structure.
 360  * Quite similar to "indexed_list_insert, saving that whenever an element having
 361  * the same index value is encountered, rather than replacing the entry (as in
 362  * the aforementioned function) a new list element is created, and placed in front
 363  * of the first such entry encountered.
 364  * ------------------------------------------------------------------------
 365  */
 366 extern int ordered_ilist_insert();
 367 /*    int *element;
 368  *    int indx;
 369  *    ilist **lptr;  */
 370
 371 /* ------------------------------------------------------------------------
 372  * ilist_length
 373  * ------------------------------------------------------------------------
 374  */
 375 extern int ilist_length();
 376 /*    ilist *l;  */
 377
 378 /* ------------------------------------------------------------------------
 379  * ipop
 380  * ------------------------------------------------------------------------
 381  */
 382 extern int *ipop();
 383 /*    ilist **l;  */
 384
 385 /* ------------------------------------------------------------------------
 386  * ipush
 387  * ------------------------------------------------------------------------
 388  */
 389 extern void ipush();
 390 /* int *what;  */
 391 /* ilist **l;  */
 392
 393 /* ------------------------------------------------------------------------
 394  * append_ilist: append two generic indexed lists together.
 395  * Works for either list null.
 396  * If both lists are null, it returns null.
 397  * ------------------------------------------------------------------------
 398  */
 399 extern ilist *append_ilist();
 400 /*    ilist *l1, *l2;*/
 401
 402 /* ------------------------------------------------------------------------
 403  * free_ilist   wipe this list from memory.  Do not disturb any list elements.
 404  * ------------------------------------------------------------------------
 405  */
 406 extern ilist *free_ilist();
 407 /*      ilist *l;   */
 408
 409
 410
 411 /* ------------------------------------------------------------------------
 412  * END OF FILE
 413  * ------------------------------------------------------------------------
 414  */
 415