/* * Copyright (c) 1993 David I. Bell * Permission is granted to use, distribute, or modify this source, * provided that this copyright notice remains intact. * * List handling routines. * Lists can be composed of any types of values, mixed if desired. * Lists are doubly linked so that elements can be inserted or * deleted efficiently at any point in the list. A pointer is * kept to the most recently indexed element so that sequential * accesses are fast. */ #include "calc.h" static LISTELEM *elemalloc(); static LISTELEM *listelement(); static void elemfree(); static void removelistelement(); /* * Free lists for list headers and list elements. */ static FREELIST headerfreelist = { sizeof(LIST), /* size of list header */ 20 /* number of free headers to keep */ }; static FREELIST elementfreelist = { sizeof(LISTELEM), /* size of list element */ 1000 /* number of free list elements to keep */ }; /* * Insert an element before the first element of a list. */ void insertlistfirst(lp, vp) LIST *lp; /* list to put element onto */ VALUE *vp; /* value to be inserted */ { LISTELEM *ep; /* list element */ ep = elemalloc(); copyvalue(vp, &ep->e_value); if (lp->l_count == 0) lp->l_last = ep; else { lp->l_cacheindex++; lp->l_first->e_prev = ep; ep->e_next = lp->l_first; } lp->l_first = ep; lp->l_count++; } /* * Insert an element after the last element of a list. */ void insertlistlast(lp, vp) LIST *lp; /* list to put element onto */ VALUE *vp; /* value to be inserted */ { LISTELEM *ep; /* list element */ ep = elemalloc(); copyvalue(vp, &ep->e_value); if (lp->l_count == 0) lp->l_first = ep; else { lp->l_last->e_next = ep; ep->e_prev = lp->l_last; } lp->l_last = ep; lp->l_count++; } /* * Insert an element into the middle of list at the given index (zero based). * The specified index will select the new element, so existing elements * at or beyond the index will be shifted down one position. It is legal * to specify an index which is right at the end of the list, in which * case the element is appended to the list. */ void insertlistmiddle(lp, index, vp) LIST *lp; /* list to put element onto */ long index; /* element number to insert in front of */ VALUE *vp; /* value to be inserted */ { LISTELEM *ep; /* list element */ LISTELEM *oldep; /* old list element at desired index */ if (index == 0) { insertlistfirst(lp, vp); return; } if (index == lp->l_count) { insertlistlast(lp, vp); return; } oldep = NULL; if ((index >= 0) && (index < lp->l_count)) oldep = listelement(lp, index); if (oldep == NULL) error("Index out of bounds for list insertion"); ep = elemalloc(); copyvalue(vp, &ep->e_value); ep->e_next = oldep; ep->e_prev = oldep->e_prev; ep->e_prev->e_next = ep; oldep->e_prev = ep; lp->l_cache = ep; lp->l_cacheindex = index; lp->l_count++; } /* * Remove the first element from a list, returning its value. * Returns the null value if no more elements exist. */ void removelistfirst(lp, vp) LIST *lp; /* list to have element removed */ VALUE *vp; /* location of the value */ { if (lp->l_count == 0) { vp->v_type = V_NULL; return; } *vp = lp->l_first->e_value; lp->l_first->e_value.v_type = V_NULL; removelistelement(lp, lp->l_first); } /* * Remove the last element from a list, returning its value. * Returns the null value if no more elements exist. */ void removelistlast(lp, vp) LIST *lp; /* list to have element removed */ VALUE *vp; /* location of the value */ { if (lp->l_count == 0) { vp->v_type = V_NULL; return; } *vp = lp->l_last->e_value; lp->l_last->e_value.v_type = V_NULL; removelistelement(lp, lp->l_last); } /* * Remove the element with the given index from a list, returning its value. */ void removelistmiddle(lp, index, vp) LIST *lp; /* list to have element removed */ long index; /* list element to be removed */ VALUE *vp; /* location of the value */ { LISTELEM *ep; /* element being removed */ ep = NULL; if ((index >= 0) && (index < lp->l_count)) ep = listelement(lp, index); if (ep == NULL) error("Index out of bounds for list deletion"); *vp = ep->e_value; ep->e_value.v_type = V_NULL; removelistelement(lp, ep); } /* * Remove an arbitrary element from a list. * The value contained in the element is freed. */ static void removelistelement(lp, ep) register LIST *lp; /* list header */ register LISTELEM *ep; /* list element to remove */ { if ((ep == lp->l_cache) || ((ep != lp->l_first) && (ep != lp->l_last))) lp->l_cache = NULL; if (ep->e_next) ep->e_next->e_prev = ep->e_prev; if (ep->e_prev) ep->e_prev->e_next = ep->e_next; if (ep == lp->l_first) { lp->l_first = ep->e_next; lp->l_cacheindex--; } if (ep == lp->l_last) lp->l_last = ep->e_prev; lp->l_count--; elemfree(ep); } /* * Search a list for the specified value starting at the specified index. * Returns the element number (zero based) of the found value, or -1 if * the value was not found. */ long listsearch(lp, vp, index) LIST *lp; VALUE *vp; long index; { register LISTELEM *ep; if (index < 0) index = 0; ep = listelement(lp, index); while (ep) { if (!comparevalue(&ep->e_value, vp)) { lp->l_cache = ep; lp->l_cacheindex = index; return index; } ep = ep->e_next; index++; } return -1; } /* * Search a list backwards for the specified value starting at the * specified index. Returns the element number (zero based) of the * found value, or -1 if the value was not found. */ long listrsearch(lp, vp, index) LIST *lp; VALUE *vp; long index; { register LISTELEM *ep; if (index >= lp->l_count) index = lp->l_count - 1; ep = listelement(lp, index); while (ep) { if (!comparevalue(&ep->e_value, vp)) { lp->l_cache = ep; lp->l_cacheindex = index; return index; } ep = ep->e_prev; index--; } return -1; } /* * Index into a list and return the address for the value corresponding * to that index. Returns NULL if the element does not exist. */ VALUE * listindex(lp, index) LIST *lp; /* list to index into */ long index; /* index of desired element */ { LISTELEM *ep; ep = listelement(lp, index); if (ep == NULL) return NULL; return &ep->e_value; } /* * Return the element at a specified index number of a list. * The list is indexed starting at zero, and negative indices * indicate to index from the end of the list. This routine finds * the element by chaining through the list from the closest one * of the first, last, and cached elements. Returns NULL if the * element does not exist. */ static LISTELEM * listelement(lp, index) register LIST *lp; /* list to index into */ long index; /* index of desired element */ { register LISTELEM *ep; /* current list element */ long dist; /* distance to element */ long temp; /* temporary distance */ BOOL forward; /* TRUE if need to walk forwards */ if (index < 0) index += lp->l_count; if ((index < 0) || (index >= lp->l_count)) return NULL; /* * Check quick special cases first. */ if (index == 0) return lp->l_first; if (index == 1) return lp->l_first->e_next; if (index == lp->l_count - 1) return lp->l_last; if ((index == lp->l_cacheindex) && lp->l_cache) return lp->l_cache; /* * Calculate whether it is better to go forwards from * the first element or backwards from the last element. */ forward = ((index * 2) <= lp->l_count); if (forward) { dist = index; ep = lp->l_first; } else { dist = (lp->l_count - 1) - index; ep = lp->l_last; } /* * Now see if we have a cached element and if so, whether or * not the distance from it is better than the above distance. */ if (lp->l_cache) { temp = index - lp->l_cacheindex; if ((temp >= 0) && (temp < dist)) { dist = temp; ep = lp->l_cache; forward = TRUE; } if ((temp < 0) && (-temp < dist)) { dist = -temp; ep = lp->l_cache; forward = FALSE; } } /* * Now walk forwards or backwards from the selected element * until we reach the correct element. Cache the location of * the found element for future use. */ if (forward) { while (dist-- > 0) ep = ep->e_next; } else { while (dist-- > 0) ep = ep->e_prev; } lp->l_cache = ep; lp->l_cacheindex = index; return ep; } /* * Compare two lists to see if they are identical. * Returns TRUE if they are different. */ BOOL listcmp(lp1, lp2) LIST *lp1, *lp2; { LISTELEM *e1, *e2; long count; if (lp1 == lp2) return FALSE; if (lp1->l_count != lp2->l_count) return TRUE; e1 = lp1->l_first; e2 = lp2->l_first; count = lp1->l_count; while (count-- > 0) { if (comparevalue(&e1->e_value, &e2->e_value)) return TRUE; e1 = e1->e_next; e2 = e2->e_next; } return FALSE; } /* * Copy a list */ LIST * listcopy(oldlp) LIST *oldlp; { LIST *lp; LISTELEM *oldep; lp = listalloc(); oldep = oldlp->l_first; while (oldep) { insertlistlast(lp, &oldep->e_value); oldep = oldep->e_next; } return lp; } /* * Allocate an element for a list. */ static LISTELEM * elemalloc() { LISTELEM *ep; ep = (LISTELEM *) allocitem(&elementfreelist); if (ep == NULL) error("Cannot allocate list element"); ep->e_next = NULL; ep->e_prev = NULL; ep->e_value.v_type = V_NULL; return ep; } /* * Free a list element, along with any contained value. */ static void elemfree(ep) LISTELEM *ep; { if (ep->e_value.v_type != V_NULL) freevalue(&ep->e_value); freeitem(&elementfreelist, (FREEITEM *) ep); } /* * Allocate a new list header. */ LIST * listalloc() { register LIST *lp; lp = (LIST *) allocitem(&headerfreelist); if (lp == NULL) error("Cannot allocate list header"); lp->l_first = NULL; lp->l_last = NULL; lp->l_cache = NULL; lp->l_cacheindex = 0; lp->l_count = 0; return lp; } /* * Free a list header, along with all of its list elements. */ void listfree(lp) register LIST *lp; { register LISTELEM *ep; while (lp->l_count-- > 0) { ep = lp->l_first; lp->l_first = ep->e_next; elemfree(ep); } freeitem(&headerfreelist, (FREEITEM *) lp); } /* * Print out a list along with the specified number of its elements. * The elements are printed out in shortened form. */ void listprint(lp, max_print) LIST *lp; long max_print; { long count; long index; LISTELEM *ep; if (max_print > lp->l_count) max_print = lp->l_count; count = 0; ep = lp->l_first; index = lp->l_count; while (index-- > 0) { if ((ep->e_value.v_type != V_NUM) || (!qiszero(ep->e_value.v_num))) count++; ep = ep->e_next; } if (max_print > 0) math_str("\n"); math_fmt("list (%ld element%s, %ld nonzero)", lp->l_count, ((lp->l_count == 1) ? "" : "s"), count); if (max_print <= 0) return; /* * Walk through the first few list elements, printing their * value in short and unambiguous format. */ math_str(":\n"); ep = lp->l_first; for (index = 0; index < max_print; index++) { math_fmt(" [[%ld]] = ", index); printvalue(&ep->e_value, PRINT_SHORT | PRINT_UNAMBIG); math_str("\n"); ep = ep->e_next; } if (max_print < lp->l_count) math_str(" ...\n"); } /* END CODE */