| /********************************************************************** |
| * File: elst.c (Formerly elist.c) |
| * Description: Embedded list handling code which is not in the include file. |
| * Author: Phil Cheatle |
| * Created: Fri Jan 04 13:55:49 GMT 1991 |
| * |
| * (C) Copyright 1991, Hewlett-Packard Ltd. |
| ** Licensed under the Apache License, Version 2.0 (the "License"); |
| ** you may not use this file except in compliance with the License. |
| ** You may obtain a copy of the License at |
| ** http://www.apache.org/licenses/LICENSE-2.0 |
| ** Unless required by applicable law or agreed to in writing, software |
| ** distributed under the License is distributed on an "AS IS" BASIS, |
| ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| ** See the License for the specific language governing permissions and |
| ** limitations under the License. |
| * |
| **********************************************************************/ |
| |
| #include "mfcpch.h" //precompiled headers |
| #include <stdlib.h> |
| #include "elst.h" |
| |
| /*********************************************************************** |
| * MEMBER FUNCTIONS OF CLASS: ELIST_LINK |
| * ===================================== |
| **********************************************************************/ |
| |
| /*********************************************************************** |
| * ELIST_LINK::serialise_asc |
| * |
| * Generates an error as it should never be called. |
| **********************************************************************/ |
| |
| void ELIST_LINK::serialise_asc( //default serialise |
| FILE *f) { |
| SERIALISE_LINKS.error ("ELIST_LINK::serialise_asc", ABORT, |
| "Don't call this, override!"); |
| } |
| |
| |
| void ELIST_LINK::de_serialise_asc( //default de_serialise |
| FILE *f) { |
| SERIALISE_LINKS.error ("ELIST_LINK::de_serialise_asc", ABORT, |
| "Don't call this, override!"); |
| } |
| |
| |
| /*********************************************************************** |
| * MEMBER FUNCTIONS OF CLASS: ELIST |
| * ================================ |
| **********************************************************************/ |
| |
| /*********************************************************************** |
| * ELIST::internal_clear |
| * |
| * Used by the destructor and the "clear" member function of derived list |
| * classes to destroy all the elements on the list. |
| * The calling function passes a "zapper" function which can be called to |
| * delete each element of the list, regardless of its derived type. This |
| * technique permits a generic clear function to destroy elements of |
| * different derived types correctly, without requiring virtual functions and |
| * the consequential memory overhead. |
| **********************************************************************/ |
| |
| void |
| ELIST::internal_clear ( //destroy all links |
| void (*zapper) (ELIST_LINK *)) { |
| //ptr to zapper functn |
| ELIST_LINK *ptr; |
| ELIST_LINK *next; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST::internal_clear", ABORT, NULL); |
| #endif |
| |
| if (!empty ()) { |
| ptr = last->next; //set to first |
| last->next = NULL; //break circle |
| last = NULL; //set list empty |
| while (ptr) { |
| next = ptr->next; |
| zapper(ptr); |
| ptr = next; |
| } |
| } |
| } |
| |
| /*********************************************************************** |
| * ELIST::assign_to_sublist |
| * |
| * The list is set to a sublist of another list. "This" list must be empty |
| * before this function is invoked. The two iterators passed must refer to |
| * the same list, different from "this" one. The sublist removed is the |
| * inclusive list from start_it's current position to end_it's current |
| * position. If this range passes over the end of the source list then the |
| * source list has its end set to the previous element of start_it. The |
| * extracted sublist is unaffected by the end point of the source list, its |
| * end point is always the end_it position. |
| **********************************************************************/ |
| |
| void ELIST::assign_to_sublist( //to this list |
| ELIST_ITERATOR *start_it, //from list start |
| ELIST_ITERATOR *end_it) { //from list end |
| const ERRCODE LIST_NOT_EMPTY = |
| "Destination list must be empty before extracting a sublist"; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST::assign_to_sublist", ABORT, NULL); |
| #endif |
| |
| if (!empty ()) |
| LIST_NOT_EMPTY.error ("ELIST.assign_to_sublist", ABORT, NULL); |
| |
| last = start_it->extract_sublist (end_it); |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST::length |
| * |
| * Return count of elements on list |
| **********************************************************************/ |
| |
| inT32 ELIST::length() { //count elements |
| ELIST_ITERATOR it(this); |
| inT32 count = 0; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST::length", ABORT, NULL); |
| #endif |
| |
| for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) |
| count++; |
| return count; |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST::sort |
| * |
| * Sort elements on list |
| * NB If you dont like the const declarations in the comparator, coerce yours: |
| * ( int (*)(const void *, const void *) |
| **********************************************************************/ |
| |
| void |
| ELIST::sort ( //sort elements |
| int comparator ( //comparison routine |
| const void *, const void *)) { |
| ELIST_ITERATOR it(this); |
| inT32 count; |
| ELIST_LINK **base; //ptr array to sort |
| ELIST_LINK **current; |
| inT32 i; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST::sort", ABORT, NULL); |
| #endif |
| |
| /* Allocate an array of pointers, one per list element */ |
| count = length (); |
| base = (ELIST_LINK **) malloc (count * sizeof (ELIST_LINK *)); |
| |
| /* Extract all elements, putting the pointers in the array */ |
| current = base; |
| for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) { |
| *current = it.extract (); |
| current++; |
| } |
| |
| /* Sort the pointer array */ |
| qsort ((char *) base, count, sizeof (*base), comparator); |
| |
| /* Rebuild the list from the sorted pointers */ |
| current = base; |
| for (i = 0; i < count; i++) { |
| it.add_to_end (*current); |
| current++; |
| } |
| free(base); |
| } |
| |
| // Assuming list has been sorted already, insert new_link to |
| // keep the list sorted according to the same comparison function. |
| // Comparision function is the same as used by sort, i.e. uses double |
| // indirection. Time is O(1) to add to beginning or end. |
| // Time is linear to add pre-sorted items to an empty list. |
| void ELIST::add_sorted(int comparator(const void*, const void*), |
| ELIST_LINK* new_link) { |
| // Check for adding at the end. |
| if (last == NULL || comparator(&last, &new_link) < 0) { |
| if (last == NULL) { |
| new_link->next = new_link; |
| } else { |
| new_link->next = last->next; |
| last->next = new_link; |
| } |
| last = new_link; |
| } else { |
| // Need to use an iterator. |
| ELIST_ITERATOR it(this); |
| for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { |
| ELIST_LINK* link = it.data(); |
| if (comparator(&link, &new_link) > 0) |
| break; |
| } |
| if (it.cycled_list()) |
| it.add_to_end(new_link); |
| else |
| it.add_before_then_move(new_link); |
| } |
| } |
| |
| /*********************************************************************** |
| * ELIST::prep_serialise |
| * |
| * Replace the last member with a count of elements for serialisation. |
| * This is used on list objects which are members of objects being |
| * serialised. The containing object has been shallow copied and this member |
| * function is invoked on the COPY. |
| **********************************************************************/ |
| |
| void ELIST::prep_serialise() { |
| ELIST_ITERATOR this_it(this); |
| inT32 count = 0; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST::prep_serialise", ABORT, NULL); |
| #endif |
| |
| count = 0; |
| if (!empty ()) |
| for (this_it.mark_cycle_pt (); |
| !this_it.cycled_list (); this_it.forward ()) |
| count++; |
| last = (ELIST_LINK *) count; |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST::internal_dump |
| * |
| * Cause each element on the list to be serialised by walking the list and |
| * calling the element_serialiser function for each element. The |
| * element_serialiser simply does the appropriate coercion of the element to |
| * its real type and then invokes the elements serialise function |
| **********************************************************************/ |
| |
| void |
| ELIST::internal_dump (FILE * f, |
| void element_serialiser (FILE *, ELIST_LINK *)) { |
| ELIST_ITERATOR this_it(this); |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST::internal_dump", ABORT, NULL); |
| #endif |
| |
| if (!empty ()) |
| for (this_it.mark_cycle_pt (); |
| !this_it.cycled_list (); this_it.forward ()) |
| element_serialiser (f, this_it.data ()); |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST::internal_de_dump |
| * |
| * Cause each element on the list to be de_serialised by extracting the count |
| * of elements on the list, (held in the last member of the dumped version of |
| * the list object), and then de-serialising that number of list elements, |
| * adding each to the end of the reconstructed list. |
| **********************************************************************/ |
| |
| void |
| ELIST::internal_de_dump (FILE * f, |
| ELIST_LINK * element_de_serialiser (FILE *)) { |
| inT32 count = (ptrdiff_t) last; |
| ELIST_ITERATOR this_it; |
| ELIST_LINK *de_serialised_element; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST::internal_de_dump", ABORT, NULL); |
| #endif |
| |
| last = NULL; |
| this_it.set_to_list (this); |
| for (; count > 0; count--) { |
| de_serialised_element = element_de_serialiser (f); |
| //ignore old ptr |
| de_serialised_element->next = NULL; |
| this_it.add_to_end (de_serialised_element); |
| } |
| } |
| |
| |
| /*********************************************************************** |
| * MEMBER FUNCTIONS OF CLASS: ELIST_ITERATOR |
| * ========================================= |
| **********************************************************************/ |
| |
| /*********************************************************************** |
| * ELIST_ITERATOR::forward |
| * |
| * Move the iterator to the next element of the list. |
| * REMEMBER: ALL LISTS ARE CIRCULAR. |
| **********************************************************************/ |
| |
| ELIST_LINK *ELIST_ITERATOR::forward() { |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST_ITERATOR::forward", ABORT, NULL); |
| if (!list) |
| NO_LIST.error ("ELIST_ITERATOR::forward", ABORT, NULL); |
| #endif |
| if (list->empty ()) |
| return NULL; |
| |
| if (current) { //not removed so |
| //set previous |
| prev = current; |
| started_cycling = TRUE; |
| // In case next is deleted by another iterator, get next from current. |
| current = current->next; |
| } else { |
| if (ex_current_was_cycle_pt) |
| cycle_pt = next; |
| current = next; |
| } |
| next = current->next; |
| |
| #ifndef NDEBUG |
| if (!current) |
| NULL_DATA.error ("ELIST_ITERATOR::forward", ABORT, NULL); |
| if (!next) |
| NULL_NEXT.error ("ELIST_ITERATOR::forward", ABORT, |
| "This is: %p Current is: %p", this, current); |
| #endif |
| return current; |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST_ITERATOR::data_relative |
| * |
| * Return the data pointer to the element "offset" elements from current. |
| * "offset" must not be less than -1. |
| * (This function can't be INLINEd because it contains a loop) |
| **********************************************************************/ |
| |
| ELIST_LINK *ELIST_ITERATOR::data_relative( //get data + or - ... |
| inT8 offset) { //offset from current |
| ELIST_LINK *ptr; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST_ITERATOR::data_relative", ABORT, NULL); |
| if (!list) |
| NO_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, NULL); |
| if (list->empty ()) |
| EMPTY_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, NULL); |
| if (offset < -1) |
| BAD_PARAMETER.error ("ELIST_ITERATOR::data_relative", ABORT, |
| "offset < -l"); |
| #endif |
| |
| if (offset == -1) |
| ptr = prev; |
| else |
| for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next); |
| |
| #ifndef NDEBUG |
| if (!ptr) |
| NULL_DATA.error ("ELIST_ITERATOR::data_relative", ABORT, NULL); |
| #endif |
| |
| return ptr; |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST_ITERATOR::move_to_last() |
| * |
| * Move current so that it is set to the end of the list. |
| * Return data just in case anyone wants it. |
| * (This function can't be INLINEd because it contains a loop) |
| **********************************************************************/ |
| |
| ELIST_LINK *ELIST_ITERATOR::move_to_last() { |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST_ITERATOR::move_to_last", ABORT, NULL); |
| if (!list) |
| NO_LIST.error ("ELIST_ITERATOR::move_to_last", ABORT, NULL); |
| #endif |
| |
| while (current != list->last) |
| forward(); |
| |
| return current; |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST_ITERATOR::exchange() |
| * |
| * Given another iterator, whose current element is a different element on |
| * the same list list OR an element of another list, exchange the two current |
| * elements. On return, each iterator points to the element which was the |
| * other iterators current on entry. |
| * (This function hasn't been in-lined because its a bit big!) |
| **********************************************************************/ |
| |
| void ELIST_ITERATOR::exchange( //positions of 2 links |
| ELIST_ITERATOR *other_it) { //other iterator |
| const ERRCODE DONT_EXCHANGE_DELETED = |
| "Can't exchange deleted elements of lists"; |
| |
| ELIST_LINK *old_current; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST_ITERATOR::exchange", ABORT, NULL); |
| if (!list) |
| NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, NULL); |
| if (!other_it) |
| BAD_PARAMETER.error ("ELIST_ITERATOR::exchange", ABORT, "other_it NULL"); |
| if (!(other_it->list)) |
| NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, "other_it"); |
| #endif |
| |
| /* Do nothing if either list is empty or if both iterators reference the same |
| link */ |
| |
| if ((list->empty ()) || |
| (other_it->list->empty ()) || (current == other_it->current)) |
| return; |
| |
| /* Error if either current element is deleted */ |
| |
| if (!current || !other_it->current) |
| DONT_EXCHANGE_DELETED.error ("ELIST_ITERATOR.exchange", ABORT, NULL); |
| |
| /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements |
| (other before this); non-doubleton adjacent elements (this before other); |
| non-adjacent elements. */ |
| |
| //adjacent links |
| if ((next == other_it->current) || |
| (other_it->next == current)) { |
| //doubleton list |
| if ((next == other_it->current) && |
| (other_it->next == current)) { |
| prev = next = current; |
| other_it->prev = other_it->next = other_it->current; |
| } |
| else { //non-doubleton with |
| //adjacent links |
| //other before this |
| if (other_it->next == current) { |
| other_it->prev->next = current; |
| other_it->current->next = next; |
| current->next = other_it->current; |
| other_it->next = other_it->current; |
| prev = current; |
| } |
| else { //this before other |
| prev->next = other_it->current; |
| current->next = other_it->next; |
| other_it->current->next = current; |
| next = current; |
| other_it->prev = other_it->current; |
| } |
| } |
| } |
| else { //no overlap |
| prev->next = other_it->current; |
| current->next = other_it->next; |
| other_it->prev->next = current; |
| other_it->current->next = next; |
| } |
| |
| /* update end of list pointer when necessary (remember that the 2 iterators |
| may iterate over different lists!) */ |
| |
| if (list->last == current) |
| list->last = other_it->current; |
| if (other_it->list->last == other_it->current) |
| other_it->list->last = current; |
| |
| if (current == cycle_pt) |
| cycle_pt = other_it->cycle_pt; |
| if (other_it->current == other_it->cycle_pt) |
| other_it->cycle_pt = cycle_pt; |
| |
| /* The actual exchange - in all cases*/ |
| |
| old_current = current; |
| current = other_it->current; |
| other_it->current = old_current; |
| } |
| |
| |
| /*********************************************************************** |
| * ELIST_ITERATOR::extract_sublist() |
| * |
| * This is a private member, used only by ELIST::assign_to_sublist. |
| * Given another iterator for the same list, extract the links from THIS to |
| * OTHER inclusive, link them into a new circular list, and return a |
| * pointer to the last element. |
| * (Can't inline this function because it contains a loop) |
| **********************************************************************/ |
| |
| ELIST_LINK *ELIST_ITERATOR::extract_sublist( //from this current |
| ELIST_ITERATOR *other_it) { //to other current |
| #ifndef NDEBUG |
| const ERRCODE BAD_EXTRACTION_PTS = |
| "Can't extract sublist from points on different lists"; |
| const ERRCODE DONT_EXTRACT_DELETED = |
| "Can't extract a sublist marked by deleted points"; |
| #endif |
| const ERRCODE BAD_SUBLIST = "Can't find sublist end point in original list"; |
| |
| ELIST_ITERATOR temp_it = *this; |
| ELIST_LINK *end_of_new_list; |
| |
| #ifndef NDEBUG |
| if (!this) |
| NULL_OBJECT.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL); |
| if (!other_it) |
| BAD_PARAMETER.error ("ELIST_ITERATOR::extract_sublist", ABORT, |
| "other_it NULL"); |
| if (!list) |
| NO_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL); |
| if (list != other_it->list) |
| BAD_EXTRACTION_PTS.error ("ELIST_ITERATOR.extract_sublist", ABORT, NULL); |
| if (list->empty ()) |
| EMPTY_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL); |
| |
| if (!current || !other_it->current) |
| DONT_EXTRACT_DELETED.error ("ELIST_ITERATOR.extract_sublist", ABORT, |
| NULL); |
| #endif |
| |
| ex_current_was_last = other_it->ex_current_was_last = FALSE; |
| ex_current_was_cycle_pt = FALSE; |
| other_it->ex_current_was_cycle_pt = FALSE; |
| |
| temp_it.mark_cycle_pt (); |
| do { //walk sublist |
| if (temp_it.cycled_list ()) //cant find end pt |
| BAD_SUBLIST.error ("ELIST_ITERATOR.extract_sublist", ABORT, NULL); |
| |
| if (temp_it.at_last ()) { |
| list->last = prev; |
| ex_current_was_last = other_it->ex_current_was_last = TRUE; |
| } |
| |
| if (temp_it.current == cycle_pt) |
| ex_current_was_cycle_pt = TRUE; |
| |
| if (temp_it.current == other_it->cycle_pt) |
| other_it->ex_current_was_cycle_pt = TRUE; |
| |
| temp_it.forward (); |
| } |
| while (temp_it.prev != other_it->current); |
| |
| //circularise sublist |
| other_it->current->next = current; |
| end_of_new_list = other_it->current; |
| |
| //sublist = whole list |
| if (prev == other_it->current) { |
| list->last = NULL; |
| prev = current = next = NULL; |
| other_it->prev = other_it->current = other_it->next = NULL; |
| } |
| else { |
| prev->next = other_it->next; |
| current = other_it->current = NULL; |
| next = other_it->next; |
| other_it->prev = prev; |
| } |
| return end_of_new_list; |
| } |