1 /**********************************************************************
2 * File: elst.c (Formerly elist.c)
3 * Description: Embedded list handling code which is not in the include file.
4 * Author: Phil Cheatle
5 * Created: Fri Jan 04 13:55:49 GMT 1991
6 *
7 * (C) Copyright 1991, Hewlett-Packard Ltd.
8 ** Licensed under the Apache License, Version 2.0 (the "License");
9 ** you may not use this file except in compliance with the License.
10 ** You may obtain a copy of the License at
11 ** http://www.apache.org/licenses/LICENSE-2.0
12 ** Unless required by applicable law or agreed to in writing, software
13 ** distributed under the License is distributed on an "AS IS" BASIS,
14 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 ** See the License for the specific language governing permissions and
16 ** limitations under the License.
17 *
18 **********************************************************************/
19
20 #include "mfcpch.h" //precompiled headers
21 #include <stdlib.h>
22 #include "elst.h"
23
24 /***********************************************************************
25 * MEMBER FUNCTIONS OF CLASS: ELIST_LINK
26 * =====================================
27 **********************************************************************/
28
29 /***********************************************************************
30 * ELIST_LINK::serialise_asc
31 *
32 * Generates an error as it should never be called.
33 **********************************************************************/
34
serialise_asc(FILE * f)35 void ELIST_LINK::serialise_asc( //default serialise
36 FILE *f) {
37 SERIALISE_LINKS.error ("ELIST_LINK::serialise_asc", ABORT,
38 "Don't call this, override!");
39 }
40
41
de_serialise_asc(FILE * f)42 void ELIST_LINK::de_serialise_asc( //default de_serialise
43 FILE *f) {
44 SERIALISE_LINKS.error ("ELIST_LINK::de_serialise_asc", ABORT,
45 "Don't call this, override!");
46 }
47
48
49 /***********************************************************************
50 * MEMBER FUNCTIONS OF CLASS: ELIST
51 * ================================
52 **********************************************************************/
53
54 /***********************************************************************
55 * ELIST::internal_clear
56 *
57 * Used by the destructor and the "clear" member function of derived list
58 * classes to destroy all the elements on the list.
59 * The calling function passes a "zapper" function which can be called to
60 * delete each element of the list, regardless of its derived type. This
61 * technique permits a generic clear function to destroy elements of
62 * different derived types correctly, without requiring virtual functions and
63 * the consequential memory overhead.
64 **********************************************************************/
65
66 void
internal_clear(void (* zapper)(ELIST_LINK *))67 ELIST::internal_clear ( //destroy all links
68 void (*zapper) (ELIST_LINK *)) {
69 //ptr to zapper functn
70 ELIST_LINK *ptr;
71 ELIST_LINK *next;
72
73 #ifndef NDEBUG
74 if (!this)
75 NULL_OBJECT.error ("ELIST::internal_clear", ABORT, NULL);
76 #endif
77
78 if (!empty ()) {
79 ptr = last->next; //set to first
80 last->next = NULL; //break circle
81 last = NULL; //set list empty
82 while (ptr) {
83 next = ptr->next;
84 zapper(ptr);
85 ptr = next;
86 }
87 }
88 }
89
90 /***********************************************************************
91 * ELIST::assign_to_sublist
92 *
93 * The list is set to a sublist of another list. "This" list must be empty
94 * before this function is invoked. The two iterators passed must refer to
95 * the same list, different from "this" one. The sublist removed is the
96 * inclusive list from start_it's current position to end_it's current
97 * position. If this range passes over the end of the source list then the
98 * source list has its end set to the previous element of start_it. The
99 * extracted sublist is unaffected by the end point of the source list, its
100 * end point is always the end_it position.
101 **********************************************************************/
102
assign_to_sublist(ELIST_ITERATOR * start_it,ELIST_ITERATOR * end_it)103 void ELIST::assign_to_sublist( //to this list
104 ELIST_ITERATOR *start_it, //from list start
105 ELIST_ITERATOR *end_it) { //from list end
106 const ERRCODE LIST_NOT_EMPTY =
107 "Destination list must be empty before extracting a sublist";
108
109 #ifndef NDEBUG
110 if (!this)
111 NULL_OBJECT.error ("ELIST::assign_to_sublist", ABORT, NULL);
112 #endif
113
114 if (!empty ())
115 LIST_NOT_EMPTY.error ("ELIST.assign_to_sublist", ABORT, NULL);
116
117 last = start_it->extract_sublist (end_it);
118 }
119
120
121 /***********************************************************************
122 * ELIST::length
123 *
124 * Return count of elements on list
125 **********************************************************************/
126
length()127 inT32 ELIST::length() { //count elements
128 ELIST_ITERATOR it(this);
129 inT32 count = 0;
130
131 #ifndef NDEBUG
132 if (!this)
133 NULL_OBJECT.error ("ELIST::length", ABORT, NULL);
134 #endif
135
136 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
137 count++;
138 return count;
139 }
140
141
142 /***********************************************************************
143 * ELIST::sort
144 *
145 * Sort elements on list
146 * NB If you dont like the const declarations in the comparator, coerce yours:
147 * ( int (*)(const void *, const void *)
148 **********************************************************************/
149
150 void
sort(int comparator (const void *,const void *))151 ELIST::sort ( //sort elements
152 int comparator ( //comparison routine
153 const void *, const void *)) {
154 ELIST_ITERATOR it(this);
155 inT32 count;
156 ELIST_LINK **base; //ptr array to sort
157 ELIST_LINK **current;
158 inT32 i;
159
160 #ifndef NDEBUG
161 if (!this)
162 NULL_OBJECT.error ("ELIST::sort", ABORT, NULL);
163 #endif
164
165 /* Allocate an array of pointers, one per list element */
166 count = length ();
167 base = (ELIST_LINK **) malloc (count * sizeof (ELIST_LINK *));
168
169 /* Extract all elements, putting the pointers in the array */
170 current = base;
171 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
172 *current = it.extract ();
173 current++;
174 }
175
176 /* Sort the pointer array */
177 qsort ((char *) base, count, sizeof (*base), comparator);
178
179 /* Rebuild the list from the sorted pointers */
180 current = base;
181 for (i = 0; i < count; i++) {
182 it.add_to_end (*current);
183 current++;
184 }
185 free(base);
186 }
187
188 // Assuming list has been sorted already, insert new_link to
189 // keep the list sorted according to the same comparison function.
190 // Comparision function is the same as used by sort, i.e. uses double
191 // indirection. Time is O(1) to add to beginning or end.
192 // Time is linear to add pre-sorted items to an empty list.
add_sorted(int comparator (const void *,const void *),ELIST_LINK * new_link)193 void ELIST::add_sorted(int comparator(const void*, const void*),
194 ELIST_LINK* new_link) {
195 // Check for adding at the end.
196 if (last == NULL || comparator(&last, &new_link) < 0) {
197 if (last == NULL) {
198 new_link->next = new_link;
199 } else {
200 new_link->next = last->next;
201 last->next = new_link;
202 }
203 last = new_link;
204 } else {
205 // Need to use an iterator.
206 ELIST_ITERATOR it(this);
207 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
208 ELIST_LINK* link = it.data();
209 if (comparator(&link, &new_link) > 0)
210 break;
211 }
212 if (it.cycled_list())
213 it.add_to_end(new_link);
214 else
215 it.add_before_then_move(new_link);
216 }
217 }
218
219 /***********************************************************************
220 * ELIST::prep_serialise
221 *
222 * Replace the last member with a count of elements for serialisation.
223 * This is used on list objects which are members of objects being
224 * serialised. The containing object has been shallow copied and this member
225 * function is invoked on the COPY.
226 **********************************************************************/
227
prep_serialise()228 void ELIST::prep_serialise() {
229 ELIST_ITERATOR this_it(this);
230 inT32 count = 0;
231
232 #ifndef NDEBUG
233 if (!this)
234 NULL_OBJECT.error ("ELIST::prep_serialise", ABORT, NULL);
235 #endif
236
237 count = 0;
238 if (!empty ())
239 for (this_it.mark_cycle_pt ();
240 !this_it.cycled_list (); this_it.forward ())
241 count++;
242 last = (ELIST_LINK *) count;
243 }
244
245
246 /***********************************************************************
247 * ELIST::internal_dump
248 *
249 * Cause each element on the list to be serialised by walking the list and
250 * calling the element_serialiser function for each element. The
251 * element_serialiser simply does the appropriate coercion of the element to
252 * its real type and then invokes the elements serialise function
253 **********************************************************************/
254
255 void
internal_dump(FILE * f,void element_serialiser (FILE *,ELIST_LINK *))256 ELIST::internal_dump (FILE * f,
257 void element_serialiser (FILE *, ELIST_LINK *)) {
258 ELIST_ITERATOR this_it(this);
259
260 #ifndef NDEBUG
261 if (!this)
262 NULL_OBJECT.error ("ELIST::internal_dump", ABORT, NULL);
263 #endif
264
265 if (!empty ())
266 for (this_it.mark_cycle_pt ();
267 !this_it.cycled_list (); this_it.forward ())
268 element_serialiser (f, this_it.data ());
269 }
270
271
272 /***********************************************************************
273 * ELIST::internal_de_dump
274 *
275 * Cause each element on the list to be de_serialised by extracting the count
276 * of elements on the list, (held in the last member of the dumped version of
277 * the list object), and then de-serialising that number of list elements,
278 * adding each to the end of the reconstructed list.
279 **********************************************************************/
280
281 void
internal_de_dump(FILE * f,ELIST_LINK * element_de_serialiser (FILE *))282 ELIST::internal_de_dump (FILE * f,
283 ELIST_LINK * element_de_serialiser (FILE *)) {
284 inT32 count = (ptrdiff_t) last;
285 ELIST_ITERATOR this_it;
286 ELIST_LINK *de_serialised_element;
287
288 #ifndef NDEBUG
289 if (!this)
290 NULL_OBJECT.error ("ELIST::internal_de_dump", ABORT, NULL);
291 #endif
292
293 last = NULL;
294 this_it.set_to_list (this);
295 for (; count > 0; count--) {
296 de_serialised_element = element_de_serialiser (f);
297 //ignore old ptr
298 de_serialised_element->next = NULL;
299 this_it.add_to_end (de_serialised_element);
300 }
301 }
302
303
304 /***********************************************************************
305 * MEMBER FUNCTIONS OF CLASS: ELIST_ITERATOR
306 * =========================================
307 **********************************************************************/
308
309 /***********************************************************************
310 * ELIST_ITERATOR::forward
311 *
312 * Move the iterator to the next element of the list.
313 * REMEMBER: ALL LISTS ARE CIRCULAR.
314 **********************************************************************/
315
forward()316 ELIST_LINK *ELIST_ITERATOR::forward() {
317 #ifndef NDEBUG
318 if (!this)
319 NULL_OBJECT.error ("ELIST_ITERATOR::forward", ABORT, NULL);
320 if (!list)
321 NO_LIST.error ("ELIST_ITERATOR::forward", ABORT, NULL);
322 #endif
323 if (list->empty ())
324 return NULL;
325
326 if (current) { //not removed so
327 //set previous
328 prev = current;
329 started_cycling = TRUE;
330 // In case next is deleted by another iterator, get next from current.
331 current = current->next;
332 } else {
333 if (ex_current_was_cycle_pt)
334 cycle_pt = next;
335 current = next;
336 }
337 next = current->next;
338
339 #ifndef NDEBUG
340 if (!current)
341 NULL_DATA.error ("ELIST_ITERATOR::forward", ABORT, NULL);
342 if (!next)
343 NULL_NEXT.error ("ELIST_ITERATOR::forward", ABORT,
344 "This is: %p Current is: %p", this, current);
345 #endif
346 return current;
347 }
348
349
350 /***********************************************************************
351 * ELIST_ITERATOR::data_relative
352 *
353 * Return the data pointer to the element "offset" elements from current.
354 * "offset" must not be less than -1.
355 * (This function can't be INLINEd because it contains a loop)
356 **********************************************************************/
357
data_relative(inT8 offset)358 ELIST_LINK *ELIST_ITERATOR::data_relative( //get data + or - ...
359 inT8 offset) { //offset from current
360 ELIST_LINK *ptr;
361
362 #ifndef NDEBUG
363 if (!this)
364 NULL_OBJECT.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
365 if (!list)
366 NO_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
367 if (list->empty ())
368 EMPTY_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
369 if (offset < -1)
370 BAD_PARAMETER.error ("ELIST_ITERATOR::data_relative", ABORT,
371 "offset < -l");
372 #endif
373
374 if (offset == -1)
375 ptr = prev;
376 else
377 for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next);
378
379 #ifndef NDEBUG
380 if (!ptr)
381 NULL_DATA.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
382 #endif
383
384 return ptr;
385 }
386
387
388 /***********************************************************************
389 * ELIST_ITERATOR::move_to_last()
390 *
391 * Move current so that it is set to the end of the list.
392 * Return data just in case anyone wants it.
393 * (This function can't be INLINEd because it contains a loop)
394 **********************************************************************/
395
move_to_last()396 ELIST_LINK *ELIST_ITERATOR::move_to_last() {
397 #ifndef NDEBUG
398 if (!this)
399 NULL_OBJECT.error ("ELIST_ITERATOR::move_to_last", ABORT, NULL);
400 if (!list)
401 NO_LIST.error ("ELIST_ITERATOR::move_to_last", ABORT, NULL);
402 #endif
403
404 while (current != list->last)
405 forward();
406
407 return current;
408 }
409
410
411 /***********************************************************************
412 * ELIST_ITERATOR::exchange()
413 *
414 * Given another iterator, whose current element is a different element on
415 * the same list list OR an element of another list, exchange the two current
416 * elements. On return, each iterator points to the element which was the
417 * other iterators current on entry.
418 * (This function hasn't been in-lined because its a bit big!)
419 **********************************************************************/
420
exchange(ELIST_ITERATOR * other_it)421 void ELIST_ITERATOR::exchange( //positions of 2 links
422 ELIST_ITERATOR *other_it) { //other iterator
423 const ERRCODE DONT_EXCHANGE_DELETED =
424 "Can't exchange deleted elements of lists";
425
426 ELIST_LINK *old_current;
427
428 #ifndef NDEBUG
429 if (!this)
430 NULL_OBJECT.error ("ELIST_ITERATOR::exchange", ABORT, NULL);
431 if (!list)
432 NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, NULL);
433 if (!other_it)
434 BAD_PARAMETER.error ("ELIST_ITERATOR::exchange", ABORT, "other_it NULL");
435 if (!(other_it->list))
436 NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, "other_it");
437 #endif
438
439 /* Do nothing if either list is empty or if both iterators reference the same
440 link */
441
442 if ((list->empty ()) ||
443 (other_it->list->empty ()) || (current == other_it->current))
444 return;
445
446 /* Error if either current element is deleted */
447
448 if (!current || !other_it->current)
449 DONT_EXCHANGE_DELETED.error ("ELIST_ITERATOR.exchange", ABORT, NULL);
450
451 /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
452 (other before this); non-doubleton adjacent elements (this before other);
453 non-adjacent elements. */
454
455 //adjacent links
456 if ((next == other_it->current) ||
457 (other_it->next == current)) {
458 //doubleton list
459 if ((next == other_it->current) &&
460 (other_it->next == current)) {
461 prev = next = current;
462 other_it->prev = other_it->next = other_it->current;
463 }
464 else { //non-doubleton with
465 //adjacent links
466 //other before this
467 if (other_it->next == current) {
468 other_it->prev->next = current;
469 other_it->current->next = next;
470 current->next = other_it->current;
471 other_it->next = other_it->current;
472 prev = current;
473 }
474 else { //this before other
475 prev->next = other_it->current;
476 current->next = other_it->next;
477 other_it->current->next = current;
478 next = current;
479 other_it->prev = other_it->current;
480 }
481 }
482 }
483 else { //no overlap
484 prev->next = other_it->current;
485 current->next = other_it->next;
486 other_it->prev->next = current;
487 other_it->current->next = next;
488 }
489
490 /* update end of list pointer when necessary (remember that the 2 iterators
491 may iterate over different lists!) */
492
493 if (list->last == current)
494 list->last = other_it->current;
495 if (other_it->list->last == other_it->current)
496 other_it->list->last = current;
497
498 if (current == cycle_pt)
499 cycle_pt = other_it->cycle_pt;
500 if (other_it->current == other_it->cycle_pt)
501 other_it->cycle_pt = cycle_pt;
502
503 /* The actual exchange - in all cases*/
504
505 old_current = current;
506 current = other_it->current;
507 other_it->current = old_current;
508 }
509
510
511 /***********************************************************************
512 * ELIST_ITERATOR::extract_sublist()
513 *
514 * This is a private member, used only by ELIST::assign_to_sublist.
515 * Given another iterator for the same list, extract the links from THIS to
516 * OTHER inclusive, link them into a new circular list, and return a
517 * pointer to the last element.
518 * (Can't inline this function because it contains a loop)
519 **********************************************************************/
520
extract_sublist(ELIST_ITERATOR * other_it)521 ELIST_LINK *ELIST_ITERATOR::extract_sublist( //from this current
522 ELIST_ITERATOR *other_it) { //to other current
523 #ifndef NDEBUG
524 const ERRCODE BAD_EXTRACTION_PTS =
525 "Can't extract sublist from points on different lists";
526 const ERRCODE DONT_EXTRACT_DELETED =
527 "Can't extract a sublist marked by deleted points";
528 #endif
529 const ERRCODE BAD_SUBLIST = "Can't find sublist end point in original list";
530
531 ELIST_ITERATOR temp_it = *this;
532 ELIST_LINK *end_of_new_list;
533
534 #ifndef NDEBUG
535 if (!this)
536 NULL_OBJECT.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL);
537 if (!other_it)
538 BAD_PARAMETER.error ("ELIST_ITERATOR::extract_sublist", ABORT,
539 "other_it NULL");
540 if (!list)
541 NO_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL);
542 if (list != other_it->list)
543 BAD_EXTRACTION_PTS.error ("ELIST_ITERATOR.extract_sublist", ABORT, NULL);
544 if (list->empty ())
545 EMPTY_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL);
546
547 if (!current || !other_it->current)
548 DONT_EXTRACT_DELETED.error ("ELIST_ITERATOR.extract_sublist", ABORT,
549 NULL);
550 #endif
551
552 ex_current_was_last = other_it->ex_current_was_last = FALSE;
553 ex_current_was_cycle_pt = FALSE;
554 other_it->ex_current_was_cycle_pt = FALSE;
555
556 temp_it.mark_cycle_pt ();
557 do { //walk sublist
558 if (temp_it.cycled_list ()) //cant find end pt
559 BAD_SUBLIST.error ("ELIST_ITERATOR.extract_sublist", ABORT, NULL);
560
561 if (temp_it.at_last ()) {
562 list->last = prev;
563 ex_current_was_last = other_it->ex_current_was_last = TRUE;
564 }
565
566 if (temp_it.current == cycle_pt)
567 ex_current_was_cycle_pt = TRUE;
568
569 if (temp_it.current == other_it->cycle_pt)
570 other_it->ex_current_was_cycle_pt = TRUE;
571
572 temp_it.forward ();
573 }
574 while (temp_it.prev != other_it->current);
575
576 //circularise sublist
577 other_it->current->next = current;
578 end_of_new_list = other_it->current;
579
580 //sublist = whole list
581 if (prev == other_it->current) {
582 list->last = NULL;
583 prev = current = next = NULL;
584 other_it->prev = other_it->current = other_it->next = NULL;
585 }
586 else {
587 prev->next = other_it->next;
588 current = other_it->current = NULL;
589 next = other_it->next;
590 other_it->prev = prev;
591 }
592 return end_of_new_list;
593 }
594