00001
00020 #include "mfcpch.h"
00021 #include <stdlib.h>
00022 #include "clst.h"
00023
00024
00025
00026
00027
00028
00039 void
00040 CLIST::internal_deep_clear (
00041 void (*zapper) (void *)) {
00042 CLIST_LINK *ptr;
00043 CLIST_LINK *next;
00044
00045 #ifdef _DEBUG
00046 if (!this)
00047 NULL_OBJECT.error ("CLIST::internal_deep_clear", ABORT, NULL);
00048 #endif
00049
00050 if (!empty ()) {
00051 ptr = last->next;
00052 last->next = NULL;
00053 last = NULL;
00054 while (ptr) {
00055 next = ptr->next;
00056 zapper (ptr->data);
00057 delete(ptr);
00058 ptr = next;
00059 }
00060 }
00061 }
00062
00063
00072 void CLIST::shallow_clear() {
00073 CLIST_LINK *ptr;
00074 CLIST_LINK *next;
00075
00076 #ifdef _DEBUG
00077 if (!this)
00078 NULL_OBJECT.error ("CLIST::shallow_clear", ABORT, NULL);
00079 #endif
00080
00081 if (!empty ()) {
00082 ptr = last->next;
00083 last->next = NULL;
00084 last = NULL;
00085 while (ptr) {
00086 next = ptr->next;
00087 delete(ptr);
00088 ptr = next;
00089 }
00090 }
00091 }
00092
00093
00102 void CLIST::internal_deep_copy (
00103 void *(*copier) (void *),
00104 const CLIST * list) {
00105 CLIST_ITERATOR from_it ((CLIST *) list);
00106 CLIST_ITERATOR to_it(this);
00107
00108 #ifdef _DEBUG
00109 if (!this)
00110 NULL_OBJECT.error ("CLIST::internal_deep_copy", ABORT, NULL);
00111 if (!list)
00112 BAD_PARAMETER.error ("CLIST::internal_deep_copy", ABORT,
00113 "source list is NULL");
00114 #endif
00115
00116 for (from_it.mark_cycle_pt (); !from_it.cycled_list (); from_it.forward ())
00117 to_it.add_after_then_move (copier (from_it.data ()));
00118 }
00119
00120
00136 void CLIST::assign_to_sublist(
00137 CLIST_ITERATOR *start_it,
00138 CLIST_ITERATOR *end_it) {
00139 const ERRCODE LIST_NOT_EMPTY =
00140 "Destination list must be empty before extracting a sublist";
00141
00142 #ifdef _DEBUG
00143 if (!this)
00144 NULL_OBJECT.error ("CLIST::assign_to_sublist", ABORT, NULL);
00145 #endif
00146
00147 if (!empty ())
00148 LIST_NOT_EMPTY.error ("CLIST.assign_to_sublist", ABORT, NULL);
00149
00150 last = start_it->extract_sublist (end_it);
00151 }
00152
00153
00157 INT32 CLIST::length() {
00158 CLIST_ITERATOR it(this);
00159 INT32 count = 0;
00160
00161 #ifdef _DEBUG
00162 if (!this)
00163 NULL_OBJECT.error ("CLIST::length", ABORT, NULL);
00164 #endif
00165
00166 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
00167 count++;
00168 return count;
00169 }
00170
00171
00175 void
00176 CLIST::sort (
00177 int comparator (
00178 const void *, const void *)) {
00179 CLIST_ITERATOR it(this);
00180 INT32 count;
00181 void **base;
00182 void **current;
00183 INT32 i;
00184
00185 #ifdef _DEBUG
00186 if (!this)
00187 NULL_OBJECT.error ("CLIST::sort", ABORT, NULL);
00188 #endif
00189
00190
00191 count = length ();
00192 base = (void **) malloc (count * sizeof (void *));
00193
00194
00195 current = base;
00196 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
00197 *current = it.extract ();
00198 current++;
00199 }
00200
00201
00202 qsort ((char *) base, count, sizeof (*base), comparator);
00203
00204
00205 current = base;
00206 for (i = 0; i < count; i++) {
00207 it.add_to_end (*current);
00208 current++;
00209 }
00210 free(base);
00211 }
00212
00213
00221 void CLIST::prep_serialise() {
00222 CLIST_ITERATOR this_it(this);
00223 INT32 count = 0;
00224
00225 #ifdef _DEBUG
00226 if (!this)
00227 NULL_OBJECT.error ("CLIST::prep_serialise", ABORT, NULL);
00228 #endif
00229
00230 count = 0;
00231 if (!empty ())
00232 for (this_it.mark_cycle_pt ();
00233 !this_it.cycled_list (); this_it.forward ())
00234 count++;
00235 last = (CLIST_LINK *) count;
00236 }
00237
00238
00248 void
00249 CLIST::internal_dump (FILE * f, void element_serialiser (FILE *, void *)) {
00250 CLIST_ITERATOR this_it(this);
00251
00252 #ifdef _DEBUG
00253 if (!this)
00254 NULL_OBJECT.error ("CLIST::internal_dump", ABORT, NULL);
00255 #endif
00256
00257 if (!empty ())
00258 for (this_it.mark_cycle_pt ();
00259 !this_it.cycled_list (); this_it.forward ())
00260 element_serialiser (f, this_it.data ());
00261 }
00262
00263
00270 void
00271 CLIST::internal_de_dump (FILE * f, void *element_de_serialiser (FILE *)) {
00272 INT32 count = (ptrdiff_t) last;
00273 CLIST_ITERATOR this_it;
00274
00275 #ifdef _DEBUG
00276 if (!this)
00277 NULL_OBJECT.error ("CLIST::internal_de_dump", ABORT, NULL);
00278 #endif
00279
00280 last = NULL;
00281 this_it.set_to_list (this);
00282 for (; count > 0; count--)
00283 this_it.add_to_end (element_de_serialiser (f));
00284 }
00285
00286
00287
00288
00289
00290
00291
00297 void *CLIST_ITERATOR::forward() {
00298 #ifdef _DEBUG
00299 if (!this)
00300 NULL_OBJECT.error ("CLIST_ITERATOR::forward", ABORT, NULL);
00301 if (!list)
00302 NO_LIST.error ("CLIST_ITERATOR::forward", ABORT, NULL);
00303 #endif
00304 if (list->empty ())
00305 return NULL;
00306
00307 if (current) {
00308
00309 prev = current;
00310 started_cycling = TRUE;
00311 }
00312 else {
00313 if (ex_current_was_cycle_pt)
00314 cycle_pt = next;
00315 }
00316 current = next;
00317 next = current->next;
00318
00319 #ifdef _DEBUG
00320 if (!current)
00321 NULL_DATA.error ("CLIST_ITERATOR::forward", ABORT, NULL);
00322 if (!next)
00323 NULL_NEXT.error ("CLIST_ITERATOR::forward", ABORT,
00324 "This is: %i Current is: %i",
00325 (int) this, (int) current);
00326 #endif
00327 return current->data;
00328 }
00329
00330
00337 void *CLIST_ITERATOR::data_relative(
00338 INT8 offset) {
00339 CLIST_LINK *ptr;
00340
00341 #ifdef _DEBUG
00342 if (!this)
00343 NULL_OBJECT.error ("CLIST_ITERATOR::data_relative", ABORT, NULL);
00344 if (!list)
00345 NO_LIST.error ("CLIST_ITERATOR::data_relative", ABORT, NULL);
00346 if (list->empty ())
00347 EMPTY_LIST.error ("CLIST_ITERATOR::data_relative", ABORT, NULL);
00348 if (offset < -1)
00349 BAD_PARAMETER.error ("CLIST_ITERATOR::data_relative", ABORT,
00350 "offset < -l");
00351 #endif
00352
00353 if (offset == -1)
00354 ptr = prev;
00355 else
00356 for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next);
00357
00358 #ifdef _DEBUG
00359 if (!ptr)
00360 NULL_DATA.error ("CLIST_ITERATOR::data_relative", ABORT, NULL);
00361 #endif
00362
00363 return ptr->data;
00364 }
00365
00366
00373 void *CLIST_ITERATOR::move_to_last() {
00374 #ifdef _DEBUG
00375 if (!this)
00376 NULL_OBJECT.error ("CLIST_ITERATOR::move_to_last", ABORT, NULL);
00377 if (!list)
00378 NO_LIST.error ("CLIST_ITERATOR::move_to_last", ABORT, NULL);
00379 #endif
00380
00381 while (current != list->last)
00382 forward();
00383
00384 if (current == NULL)
00385 return NULL;
00386 else
00387 return current->data;
00388 }
00389
00390
00402 void CLIST_ITERATOR::exchange(
00403 CLIST_ITERATOR *other_it) {
00404 const ERRCODE DONT_EXCHANGE_DELETED =
00405 "Can't exchange deleted elements of lists";
00406
00407 CLIST_LINK *old_current;
00408
00409 #ifdef _DEBUG
00410 if (!this)
00411 NULL_OBJECT.error ("CLIST_ITERATOR::exchange", ABORT, NULL);
00412 if (!list)
00413 NO_LIST.error ("CLIST_ITERATOR::exchange", ABORT, NULL);
00414 if (!other_it)
00415 BAD_PARAMETER.error ("CLIST_ITERATOR::exchange", ABORT, "other_it NULL");
00416 if (!(other_it->list))
00417 NO_LIST.error ("CLIST_ITERATOR::exchange", ABORT, "other_it");
00418 #endif
00419
00420
00421
00422 if ((list->empty ()) ||
00423 (other_it->list->empty ()) || (current == other_it->current))
00424 return;
00425
00426
00427
00428 if (!current || !other_it->current)
00429 DONT_EXCHANGE_DELETED.error ("CLIST_ITERATOR.exchange", ABORT, NULL);
00430
00431
00432
00433
00434
00435
00436
00437
00438
00439 if ((next == other_it->current) ||
00440 (other_it->next == current)) {
00441
00442 if ((next == other_it->current) &&
00443 (other_it->next == current)) {
00444 prev = next = current;
00445 other_it->prev = other_it->next = other_it->current;
00446 }
00447 else {
00448
00449
00450 if (other_it->next == current) {
00451 other_it->prev->next = current;
00452 other_it->current->next = next;
00453 current->next = other_it->current;
00454 other_it->next = other_it->current;
00455 prev = current;
00456 }
00457 else {
00458 prev->next = other_it->current;
00459 current->next = other_it->next;
00460 other_it->current->next = current;
00461 next = current;
00462 other_it->prev = other_it->current;
00463 }
00464 }
00465 }
00466 else {
00467 prev->next = other_it->current;
00468 current->next = other_it->next;
00469 other_it->prev->next = current;
00470 other_it->current->next = next;
00471 }
00472
00473
00474
00475
00476 if (list->last == current)
00477 list->last = other_it->current;
00478 if (other_it->list->last == other_it->current)
00479 other_it->list->last = current;
00480
00481 if (current == cycle_pt)
00482 cycle_pt = other_it->cycle_pt;
00483 if (other_it->current == other_it->cycle_pt)
00484 other_it->cycle_pt = cycle_pt;
00485
00486
00487
00488 old_current = current;
00489 current = other_it->current;
00490 other_it->current = old_current;
00491 }
00492
00493
00505 CLIST_LINK *CLIST_ITERATOR::extract_sublist(
00506 CLIST_ITERATOR *other_it) {
00507 CLIST_ITERATOR temp_it = *this;
00508 CLIST_LINK *end_of_new_list;
00509
00510 const ERRCODE BAD_SUBLIST = "Can't find sublist end point in original list";
00511 #ifdef _DEBUG
00512 const ERRCODE BAD_EXTRACTION_PTS =
00513 "Can't extract sublist from points on different lists";
00514 const ERRCODE DONT_EXTRACT_DELETED =
00515 "Can't extract a sublist marked by deleted points";
00516
00517 if (!this)
00518 NULL_OBJECT.error ("CLIST_ITERATOR::extract_sublist", ABORT, NULL);
00519 if (!other_it)
00520 BAD_PARAMETER.error ("CLIST_ITERATOR::extract_sublist", ABORT,
00521 "other_it NULL");
00522 if (!list)
00523 NO_LIST.error ("CLIST_ITERATOR::extract_sublist", ABORT, NULL);
00524 if (list != other_it->list)
00525 BAD_EXTRACTION_PTS.error ("CLIST_ITERATOR.extract_sublist", ABORT, NULL);
00526 if (list->empty ())
00527 EMPTY_LIST.error ("CLIST_ITERATOR::extract_sublist", ABORT, NULL);
00528
00529 if (!current || !other_it->current)
00530 DONT_EXTRACT_DELETED.error ("CLIST_ITERATOR.extract_sublist", ABORT,
00531 NULL);
00532 #endif
00533
00534 ex_current_was_last = other_it->ex_current_was_last = FALSE;
00535 ex_current_was_cycle_pt = FALSE;
00536 other_it->ex_current_was_cycle_pt = FALSE;
00537
00538 temp_it.mark_cycle_pt ();
00539 do {
00540 if (temp_it.cycled_list ())
00541 BAD_SUBLIST.error ("CLIST_ITERATOR.extract_sublist", ABORT, NULL);
00542
00543 if (temp_it.at_last ()) {
00544 list->last = prev;
00545 ex_current_was_last = other_it->ex_current_was_last = TRUE;
00546 }
00547
00548 if (temp_it.current == cycle_pt)
00549 ex_current_was_cycle_pt = TRUE;
00550
00551 if (temp_it.current == other_it->cycle_pt)
00552 other_it->ex_current_was_cycle_pt = TRUE;
00553
00554 temp_it.forward ();
00555 }
00556 while (temp_it.prev != other_it->current);
00557
00558
00559 other_it->current->next = current;
00560 end_of_new_list = other_it->current;
00561
00562
00563 if (prev == other_it->current) {
00564 list->last = NULL;
00565 prev = current = next = NULL;
00566 other_it->prev = other_it->current = other_it->next = NULL;
00567 }
00568 else {
00569 prev->next = other_it->next;
00570 current = other_it->current = NULL;
00571 next = other_it->next;
00572 other_it->prev = prev;
00573 }
00574 return end_of_new_list;
00575 }