1 /* -*-C-*- 2 ******************************************************************************** 3 * 4 * File: list.h (Formerly list.h) 5 * Description: List processing procedures declarations. 6 * Author: Mark Seaman, SW Productivity 7 * Created: Fri Oct 16 14:37:00 1987 8 * Modified: Wed Dec 5 15:43:17 1990 (Mark Seaman) marks@hpgrlt 9 * Language: C 10 * Package: N/A 11 * Status: Reusable Software Component 12 * 13 * (c) Copyright 1987, Hewlett-Packard Company. 14 ** Licensed under the Apache License, Version 2.0 (the "License"); 15 ** you may not use this file except in compliance with the License. 16 ** You may obtain a copy of the License at 17 ** http://www.apache.org/licenses/LICENSE-2.0 18 ** Unless required by applicable law or agreed to in writing, software 19 ** distributed under the License is distributed on an "AS IS" BASIS, 20 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 21 ** See the License for the specific language governing permissions and 22 ** limitations under the License. 23 * 24 ******************************************************************************** 25 * 26 * This file contains the interface for a set of general purpose list 27 * manipulation routines. For the implementation of these routines see 28 * the file "list.c". 29 * 30 ******************************************************************************** 31 * 32 * INDEX 33 * ======= 34 * 35 * BASICS: 36 * ------- 37 * first_node - Macro to return the first list node (not the cell). 38 * rest - Macro the return the second list cell 39 * pop - Destroy one list cell 40 * push - Create one list cell and set the node and next fields 41 * 42 * ITERATION: 43 * ----------------- 44 * iterate - Macro to create a for loop to visit each cell. 45 * iterate_list - Macro to visit each cell using a local variable. 46 * for_each - Applies a function to each node. 47 * 48 * LIST CELL COUNTS: 49 * ----------------- 50 * count - Returns the number of list cells in the list. 51 * second_node - Returns the second node. 52 * third - Returns the third node. 53 * fourth - Returns the fourth node. 54 * fifth - Returns the fifth node. 55 * last - Returns the last list cell. 56 * pair - Creates a list of two elements. 57 * 58 * COPYING: 59 * ----------------- 60 * copy_first - Pushes the first element from list 1 onto list 2. 61 * copy - Create a copy of a list. 62 * concat - Creates a new list that is a copy of both input lists. 63 * delete_n - Creates a new list without the chosen elements. 64 * reverse - Creates a backwards copy of the input list. 65 * sort - Use quick sort to construct a new list. 66 * transform - Creates a new list by transforming each of the nodes. 67 * 68 * TRANFORMS: (Note: These functions all modify the input list.) 69 * ---------- 70 * join - Concatenates list 1 and list 2. 71 * delete_d - Removes the requested elements from the list. 72 * transform_d - Modifies the list by applying a function to each node. 73 * insert - Add a new element into this spot in a list. (not NIL) 74 * push_last - Add a new element onto the end of a list. 75 * reverse_d - Reverse a list and destroy the old one. 76 * 77 * ASSOCIATED LISTS: 78 * ----------------- 79 * adelete - Remove a particular entry from an associated list. 80 * assoc - Find an entry in an associated list that matches a key. 81 * match - Return the data element of an a-list entry. 82 * 83 * DISPLAY: 84 * ----------------- 85 * print_cell - Print a hex dump of a list cell. 86 * show - Displays a string and a list (using lprint). 87 * 88 * SETS: 89 * ----- 90 * adjoin - Add a new element to list if it does not exist already. 91 * intersection - Create a new list that is the set intersection. 92 * set_union - Create a new list that is the set intersection. 93 * set_difference - Create a new list that is the set difference. 94 * s_adjoin - Add an element to a sort list if it is not there. 95 * s_intersection - Set intersection on a sorted list. Modifies old list. 96 * s_union - Set intersection on a sorted list. Modifies old list. 97 * search - Return the pointer to the list cell whose node matches. 98 * 99 * COMPARISONS: 100 * ----------------- 101 * is_same - Compares each node to the key. 102 * is_not_same - Compares each node to the key. 103 * is_key - Compares first of each node to the key. 104 * is_not_key - Compares first of each node to the key. 105 * 106 * CELL OPERATIONS: 107 * ----------------- 108 * new_cell - Obtain a new list cell from the free list. Allocate. 109 * free_cell - Return a list cell to the free list. 110 * destroy - Return all list cells in a list. 111 * destroy_nodes - Apply a function to each list cell and destroy the list. 112 * set_node - Assign the node field in a list cell. 113 * set_rest - Assign the next field in a list cell. 114 * 115 ***********************************************************************/ 116 117 #ifndef LIST_H 118 #define LIST_H 119 120 #include "cutil.h" 121 #include "callback.h" 122 123 /*---------------------------------------------------------------------- 124 T y p e s 125 ----------------------------------------------------------------------*/ 126 #define NIL (LIST) 0 127 struct list_rec 128 { 129 struct list_rec *node; 130 struct list_rec *next; 131 }; 132 typedef list_rec *LIST; 133 134 /*---------------------------------------------------------------------- 135 M a c r o s 136 ----------------------------------------------------------------------*/ 137 /* Predefinitions */ 138 #define rest(l) ((l) ? (l)->next : NIL) 139 #define first_node(l) ((l) ? (l)->node : NIL) 140 141 /********************************************************************** 142 * c o p y f i r s t 143 * 144 * Do the appropriate kind a push operation to copy the first node from 145 * one list to another. 146 * 147 **********************************************************************/ 148 149 #define copy_first(l1,l2) \ 150 (l2=push(l2, first_node(l1))) 151 152 /********************************************************************** 153 * i t e r a t e 154 * 155 * Visit each node in the list. Replace the old list with the list 156 * minus the head. Continue until the list is NIL. 157 **********************************************************************/ 158 159 #define iterate(l) \ 160 for (; (l) != NIL; (l) = rest (l)) 161 162 /********************************************************************** 163 * i t e r a t e l i s t 164 * 165 * Visit each node in the list (l). Use a local variable (x) to iterate 166 * through all of the list cells. This macro is identical to iterate 167 * except that it does not lose the original list. 168 **********************************************************************/ 169 170 #define iterate_list(x,l) \ 171 for ((x)=(l); (x)!=0; (x)=rest(x)) 172 173 /********************************************************************** 174 * j o i n o n 175 * 176 * Add another list onto the tail of this one. The list given as an input 177 * parameter is modified. 178 **********************************************************************/ 179 180 #define JOIN_ON(list1,list2) \ 181 ((list1) = join ((list1), (list2))) 182 183 /********************************************************************** 184 * p o p o f f 185 * 186 * Add a cell onto the front of a list. The list given as an input 187 * parameter is modified. 188 **********************************************************************/ 189 190 #define pop_off(list) \ 191 ((list) = pop (list)) 192 193 /********************************************************************** 194 * p u s h o n 195 * 196 * Add a cell onto the front of a list. The list given as an input 197 * parameter is modified. 198 **********************************************************************/ 199 200 #define push_on(list,thing) \ 201 ((list) = push (list, (LIST) (thing))) 202 203 /********************************************************************** 204 * s e c o n d 205 * 206 * Return the contents of the second list element. 207 * 208 * #define second_node(l) first_node (rest (l)) 209 **********************************************************************/ 210 211 #define second_node(l) \ 212 first_node (rest (l)) 213 214 /********************************************************************** 215 * s e t r e s t 216 * 217 * Change the "next" field of a list element to point to a desired place. 218 * 219 * #define set_rest(l,node) l->next = node; 220 **********************************************************************/ 221 222 #define set_rest(l,cell)\ 223 ((l)->next = (cell)) 224 225 /********************************************************************** 226 * t h i r d 227 * 228 * Return the contents of the third list element. 229 * 230 * #define third(l) first_node (rest (rest (l))) 231 **********************************************************************/ 232 233 #define third(l) \ 234 first_node (rest (rest (l))) 235 236 /*---------------------------------------------------------------------- 237 Public Funtion Prototypes 238 ----------------------------------------------------------------------*/ 239 int count(LIST var_list); 240 241 LIST delete_d(LIST list, void *key, int_compare is_equal); 242 243 LIST delete_d(LIST list, void *key, 244 ResultCallback2<int, void*, void*>* is_equal); 245 246 LIST destroy(LIST list); 247 248 void destroy_nodes(LIST list, void_dest destructor); 249 250 void insert(LIST list, void *node); 251 252 int is_same_node(void *item1, void *item2); 253 254 int is_same(void *item1, void *item2); 255 256 LIST join(LIST list1, LIST list2); 257 258 LIST last(LIST var_list); 259 260 void *nth_cell(LIST var_list, int item_num); 261 262 LIST pop(LIST list); 263 264 LIST push(LIST list, void *element); 265 266 LIST push_last(LIST list, void *item); 267 268 LIST reverse(LIST list); 269 270 LIST reverse_d(LIST list); 271 272 LIST s_adjoin(LIST var_list, void *variable, int_compare compare); 273 274 LIST search(LIST list, void *key, int_compare is_equal); 275 276 LIST search(LIST list, void *key, ResultCallback2<int, void*, void*>*); 277 278 /* 279 #if defined(__STDC__) || defined(__cplusplus) 280 # define _ARGS(s) s 281 #else 282 # define _ARGS(s) () 283 #endif 284 285 typedef void (*destructor) _ARGS((LIST l)); 286 287 typedef LIST (*list_proc) _ARGS((LIST a)); 288 289 int count 290 _ARGS((LIST var_list)); 291 292 LIST delete_d 293 _ARGS((LIST list, 294 LIST key, 295 int_compare is_equal)); 296 297 LIST destroy 298 _ARGS((LIST list)); 299 300 LIST destroy_nodes 301 _ARGS((LIST list, 302 void_dest destructor)); 303 304 void insert 305 _ARGS((LIST list, 306 LIST node)); 307 308 int is_same_node 309 _ARGS((LIST s1, 310 LIST s2)); 311 312 int is_same 313 _ARGS((LIST s1, 314 LIST s2)); 315 316 LIST join 317 _ARGS((LIST list1, 318 LIST list2)); 319 320 LIST last 321 _ARGS((LIST var_list)); 322 323 LIST nth_cell 324 _ARGS((LIST var_list, 325 int item_num)); 326 327 LIST pop 328 _ARGS((LIST list)); 329 330 LIST push 331 _ARGS((LIST list, 332 LIST element)); 333 334 LIST push_last 335 _ARGS((LIST list, 336 LIST item)); 337 338 LIST reverse 339 _ARGS((LIST list)); 340 341 LIST reverse_d 342 _ARGS((LIST list)); 343 344 LIST s_adjoin 345 _ARGS((LIST var_list, 346 LIST variable, 347 int_compare compare)); 348 349 LIST search 350 _ARGS((LIST list, 351 LIST key, 352 int_compare is_equal)); 353 354 #undef _ARGS 355 */ 356 #endif 357