Doxygen Source Code Documentation
SUMA_Algorithms.c
Go to the documentation of this file.00001 /* Code in this file is taken from the book: 00002 "Mastering Algorithms with C" by Kyle Loudon, published by O'Reilly & Associates. This 00003 code is under copyright and cannot be included in any other book, publication, 00004 or educational product without permission from O'Reilly & Associates. No 00005 warranty is attached; we cannot take responsibility for errors or fitness for 00006 use. 00007 */ 00008 00009 #include <stdlib.h> 00010 #include <string.h> 00011 00012 #include "SUMA_Algorithms.h" 00013 00014 00015 /***************************************************************************** 00016 * * 00017 * -------------------------------- list.c -------------------------------- * 00018 * * 00019 *****************************************************************************/ 00020 00021 /***************************************************************************** 00022 * * 00023 * ------------------------------- list_init ------------------------------ * 00024 * * 00025 *****************************************************************************/ 00026 00027 void list_init(List *list, void (*destroy)(void *data)) { 00028 00029 /***************************************************************************** 00030 * * 00031 * Initialize the list. * 00032 * * 00033 *****************************************************************************/ 00034 00035 list->size = 0; 00036 list->destroy = destroy; 00037 list->head = NULL; 00038 list->tail = NULL; 00039 00040 return; 00041 00042 } 00043 00044 /***************************************************************************** 00045 * * 00046 * ----------------------------- list_destroy ----------------------------- * 00047 * * 00048 *****************************************************************************/ 00049 00050 void list_destroy(List *list) { 00051 00052 void *data; 00053 00054 /***************************************************************************** 00055 * * 00056 * Remove each element. * 00057 * * 00058 *****************************************************************************/ 00059 00060 while (list_size(list) > 0) { 00061 00062 if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != 00063 NULL) { 00064 00065 /*********************************************************************** 00066 * * 00067 * Call a user-defined function to free dynamically allocated data. * 00068 * * 00069 ***********************************************************************/ 00070 00071 list->destroy(data); 00072 00073 } 00074 00075 } 00076 00077 /***************************************************************************** 00078 * * 00079 * No operations are allowed now, but clear the structure as a precaution. * 00080 * * 00081 *****************************************************************************/ 00082 00083 memset(list, 0, sizeof(List)); 00084 00085 return; 00086 00087 } 00088 00089 /***************************************************************************** 00090 * * 00091 * ----------------------------- list_ins_next ---------------------------- * 00092 * * 00093 *****************************************************************************/ 00094 00095 int list_ins_next(List *list, ListElmt *element, const void *data) { 00096 00097 ListElmt *new_element; 00098 00099 /***************************************************************************** 00100 * * 00101 * Allocate storage for the element. * 00102 * * 00103 *****************************************************************************/ 00104 00105 if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL) 00106 return -1; 00107 00108 /***************************************************************************** 00109 * * 00110 * Insert the element into the list. * 00111 * * 00112 *****************************************************************************/ 00113 00114 new_element->data = (void *)data; 00115 00116 if (element == NULL) { 00117 00118 /************************************************************************** 00119 * * 00120 * Handle insertion at the head of the list. * 00121 * * 00122 **************************************************************************/ 00123 00124 if (list_size(list) == 0) 00125 list->tail = new_element; 00126 00127 new_element->next = list->head; 00128 list->head = new_element; 00129 00130 } 00131 00132 else { 00133 00134 /************************************************************************** 00135 * * 00136 * Handle insertion somewhere other than at the head. * 00137 * * 00138 **************************************************************************/ 00139 00140 if (element->next == NULL) 00141 list->tail = new_element; 00142 00143 new_element->next = element->next; 00144 element->next = new_element; 00145 00146 } 00147 00148 /***************************************************************************** 00149 * * 00150 * Adjust the size of the list to account for the inserted element. * 00151 * * 00152 *****************************************************************************/ 00153 00154 list->size++; 00155 00156 return 0; 00157 00158 } 00159 00160 /***************************************************************************** 00161 * * 00162 * ----------------------------- list_rem_next ---------------------------- * 00163 * * 00164 *****************************************************************************/ 00165 00166 int list_rem_next(List *list, ListElmt *element, void **data) { 00167 00168 ListElmt *old_element; 00169 00170 /***************************************************************************** 00171 * * 00172 * Do not allow removal from an empty list. * 00173 * * 00174 *****************************************************************************/ 00175 00176 if (list_size(list) == 0) 00177 return -1; 00178 00179 /***************************************************************************** 00180 * * 00181 * Remove the element from the list. * 00182 * * 00183 *****************************************************************************/ 00184 00185 if (element == NULL) { 00186 00187 /************************************************************************** 00188 * * 00189 * Handle removal from the head of the list. * 00190 * * 00191 **************************************************************************/ 00192 00193 *data = list->head->data; 00194 old_element = list->head; 00195 list->head = list->head->next; 00196 00197 if (list_size(list) == 1) 00198 list->tail = NULL; 00199 00200 } 00201 00202 else { 00203 00204 /************************************************************************** 00205 * * 00206 * Handle removal from somewhere other than the head. * 00207 * * 00208 **************************************************************************/ 00209 00210 if (element->next == NULL) 00211 return -1; 00212 00213 *data = element->next->data; 00214 old_element = element->next; 00215 element->next = element->next->next; 00216 00217 if (element->next == NULL) 00218 list->tail = element; 00219 00220 } 00221 00222 /***************************************************************************** 00223 * * 00224 * Free the storage allocated by the abstract data type. * 00225 * * 00226 *****************************************************************************/ 00227 00228 free(old_element); 00229 00230 /***************************************************************************** 00231 * * 00232 * Adjust the size of the list to account for the removed element. * 00233 * * 00234 *****************************************************************************/ 00235 00236 list->size--; 00237 00238 return 0; 00239 00240 } 00241 00242 /***************************************************************************** 00243 * * 00244 * ------------------------------- clist.c -------------------------------- * 00245 * * 00246 *****************************************************************************/ 00247 00248 00249 /***************************************************************************** 00250 * * 00251 * ------------------------------ clist_init ------------------------------ * 00252 * * 00253 *****************************************************************************/ 00254 00255 void clist_init(CList *list, void (*destroy)(void *data)) { 00256 00257 /***************************************************************************** 00258 * * 00259 * Initialize the list. * 00260 * * 00261 *****************************************************************************/ 00262 00263 list->size = 0; 00264 list->destroy = destroy; 00265 list->head = NULL; 00266 00267 return; 00268 00269 } 00270 00271 /***************************************************************************** 00272 * * 00273 * ---------------------------- clist_destroy ----------------------------- * 00274 * * 00275 *****************************************************************************/ 00276 00277 void clist_destroy(CList *list) { 00278 00279 void *data; 00280 00281 /***************************************************************************** 00282 * * 00283 * Remove each element. * 00284 * * 00285 *****************************************************************************/ 00286 00287 while (clist_size(list) > 0) { 00288 00289 if (clist_rem_next(list, list->head, (void **)&data) == 0 && list->destroy 00290 != NULL) { 00291 00292 /*********************************************************************** 00293 * * 00294 * Call a user-defined function to free dynamically allocated data. * 00295 * * 00296 ***********************************************************************/ 00297 00298 list->destroy(data); 00299 00300 } 00301 00302 } 00303 00304 /***************************************************************************** 00305 * * 00306 * No operations are allowed now, but clear the structure as a precaution. * 00307 * * 00308 *****************************************************************************/ 00309 00310 memset(list, 0, sizeof(CList)); 00311 00312 return; 00313 00314 } 00315 00316 /***************************************************************************** 00317 * * 00318 * ---------------------------- clist_ins_next ---------------------------- * 00319 * * 00320 *****************************************************************************/ 00321 00322 int clist_ins_next(CList *list, CListElmt *element, const void *data) { 00323 00324 CListElmt *new_element; 00325 00326 /***************************************************************************** 00327 * * 00328 * Allocate storage for the element. * 00329 * * 00330 *****************************************************************************/ 00331 00332 if ((new_element = (CListElmt *)malloc(sizeof(CListElmt))) == NULL) 00333 return -1; 00334 00335 /***************************************************************************** 00336 * * 00337 * Insert the element into the list. * 00338 * * 00339 *****************************************************************************/ 00340 00341 new_element->data = (void *)data; 00342 00343 if (clist_size(list) == 0) { 00344 00345 /************************************************************************** 00346 * * 00347 * Handle insertion when the list is empty. * 00348 * * 00349 **************************************************************************/ 00350 00351 new_element->next = new_element; 00352 list->head = new_element; 00353 00354 } 00355 00356 else { 00357 00358 /************************************************************************** 00359 * * 00360 * Handle insertion when the list is not empty. * 00361 * * 00362 **************************************************************************/ 00363 00364 new_element->next = element->next; 00365 element->next = new_element; 00366 00367 } 00368 00369 /***************************************************************************** 00370 * * 00371 * Adjust the size of the list to account for the inserted element. * 00372 * * 00373 *****************************************************************************/ 00374 00375 list->size++; 00376 00377 return 0; 00378 00379 } 00380 00381 /***************************************************************************** 00382 * * 00383 * ---------------------------- clist_rem_next ---------------------------- * 00384 * * 00385 *****************************************************************************/ 00386 00387 int clist_rem_next(CList *list, CListElmt *element, void **data) { 00388 00389 CListElmt *old_element; 00390 00391 /***************************************************************************** 00392 * * 00393 * Do not allow removal from an empty list. * 00394 * * 00395 *****************************************************************************/ 00396 00397 if (clist_size(list) == 0) 00398 return -1; 00399 00400 /***************************************************************************** 00401 * * 00402 * Remove the element from the list. * 00403 * * 00404 *****************************************************************************/ 00405 00406 *data = element->next->data; 00407 00408 if (element->next == element) { 00409 00410 /************************************************************************** 00411 * * 00412 * Handle removing the last element. * 00413 * * 00414 **************************************************************************/ 00415 00416 old_element = element->next; 00417 list->head = NULL; 00418 00419 } 00420 00421 else { 00422 00423 /************************************************************************** 00424 * * 00425 * Handle removing other than the last element. * 00426 * * 00427 **************************************************************************/ 00428 00429 old_element = element->next; 00430 element->next = element->next->next; 00431 00432 } 00433 00434 /***************************************************************************** 00435 * * 00436 * Free the storage allocated by the abstract data type. * 00437 * * 00438 *****************************************************************************/ 00439 00440 free(old_element); 00441 00442 /***************************************************************************** 00443 * * 00444 * Adjust the size of the list to account for the removed element. * 00445 * * 00446 *****************************************************************************/ 00447 00448 list->size--; 00449 00450 return 0; 00451 00452 } 00453 /***************************************************************************** 00454 * * 00455 * ------------------------------- dlist.c -------------------------------- * 00456 * * 00457 *****************************************************************************/ 00458 00459 /***************************************************************************** 00460 * * 00461 * ------------------------------ dlist_init ------------------------------ * 00462 * * 00463 *****************************************************************************/ 00464 00465 void dlist_init(DList *list, void (*destroy)(void *data)) { 00466 00467 /***************************************************************************** 00468 * * 00469 * Initialize the list. * 00470 * * 00471 *****************************************************************************/ 00472 00473 list->size = 0; 00474 list->destroy = destroy; 00475 list->head = NULL; 00476 list->tail = NULL; 00477 00478 return; 00479 00480 } 00481 00482 /***************************************************************************** 00483 * * 00484 * ---------------------------- dlist_destroy ----------------------------- * 00485 * * 00486 *****************************************************************************/ 00487 00488 void dlist_destroy(DList *list) { 00489 00490 void *data; 00491 00492 /***************************************************************************** 00493 * * 00494 * Remove each element. * 00495 * * 00496 *****************************************************************************/ 00497 00498 while (dlist_size(list) > 0) { 00499 00500 if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list-> 00501 destroy != NULL) { 00502 00503 /*********************************************************************** 00504 * * 00505 * Call a user-defined function to free dynamically allocated data. * 00506 * * 00507 ***********************************************************************/ 00508 00509 list->destroy(data); 00510 00511 } 00512 00513 } 00514 00515 /***************************************************************************** 00516 * * 00517 * No operations are allowed now, but clear the structure as a precaution. * 00518 * * 00519 *****************************************************************************/ 00520 00521 memset(list, 0, sizeof(DList)); 00522 00523 return; 00524 00525 } 00526 00527 /***************************************************************************** 00528 * * 00529 * ---------------------------- dlist_ins_next ---------------------------- * 00530 * * 00531 *****************************************************************************/ 00532 00533 int dlist_ins_next(DList *list, DListElmt *element, const void *data) { 00534 00535 DListElmt *new_element; 00536 00537 /***************************************************************************** 00538 * * 00539 * Do not allow a NULL element unless the list is empty. * 00540 * * 00541 *****************************************************************************/ 00542 00543 if (element == NULL && dlist_size(list) != 0) 00544 return -1; 00545 00546 /***************************************************************************** 00547 * * 00548 * Allocate storage for the element. * 00549 * * 00550 *****************************************************************************/ 00551 00552 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL) 00553 return -1; 00554 00555 /***************************************************************************** 00556 * * 00557 * Insert the new element into the list. * 00558 * * 00559 *****************************************************************************/ 00560 00561 new_element->data = (void *)data; 00562 00563 if (dlist_size(list) == 0) { 00564 00565 /************************************************************************** 00566 * * 00567 * Handle insertion when the list is empty. * 00568 * * 00569 **************************************************************************/ 00570 00571 list->head = new_element; 00572 list->head->prev = NULL; 00573 list->head->next = NULL; 00574 list->tail = new_element; 00575 00576 } 00577 00578 else { 00579 00580 /************************************************************************** 00581 * * 00582 * Handle insertion when the list is not empty. * 00583 * * 00584 **************************************************************************/ 00585 00586 new_element->next = element->next; 00587 new_element->prev = element; 00588 00589 if (element->next == NULL) 00590 list->tail = new_element; 00591 else 00592 element->next->prev = new_element; 00593 00594 element->next = new_element; 00595 00596 } 00597 00598 /***************************************************************************** 00599 * * 00600 * Adjust the size of the list to account for the inserted element. * 00601 * * 00602 *****************************************************************************/ 00603 00604 list->size++; 00605 00606 return 0; 00607 00608 } 00609 00610 /***************************************************************************** 00611 * * 00612 * ---------------------------- dlist_ins_prev ---------------------------- * 00613 * * 00614 *****************************************************************************/ 00615 00616 00617 int dlist_ins_prev(DList *list, DListElmt *element, const void *data) { 00618 00619 DListElmt *new_element; 00620 00621 /***************************************************************************** 00622 * * 00623 * Do not allow a NULL element unless the list is empty. * 00624 * * 00625 *****************************************************************************/ 00626 00627 if (element == NULL && dlist_size(list) != 0) 00628 return -1; 00629 00630 /***************************************************************************** 00631 * * 00632 * Allocate storage to be managed by the abstract data type. * 00633 * * 00634 *****************************************************************************/ 00635 00636 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL) 00637 return -1; 00638 00639 /***************************************************************************** 00640 * * 00641 * Insert the new element into the list. * 00642 * * 00643 *****************************************************************************/ 00644 00645 new_element->data = (void *)data; 00646 00647 if (dlist_size(list) == 0) { 00648 00649 /************************************************************************** 00650 * * 00651 * Handle insertion when the list is empty. * 00652 * * 00653 **************************************************************************/ 00654 00655 list->head = new_element; 00656 list->head->prev = NULL; 00657 list->head->next = NULL; 00658 list->tail = new_element; 00659 00660 } 00661 00662 00663 else { 00664 00665 /************************************************************************** 00666 * * 00667 * Handle insertion when the list is not empty. * 00668 * * 00669 **************************************************************************/ 00670 00671 new_element->next = element; 00672 new_element->prev = element->prev; 00673 00674 if (element->prev == NULL) 00675 list->head = new_element; 00676 else 00677 element->prev->next = new_element; 00678 00679 element->prev = new_element; 00680 00681 } 00682 00683 00684 /***************************************************************************** 00685 * * 00686 * Adjust the size of the list to account for the new element. * 00687 * * 00688 *****************************************************************************/ 00689 00690 list->size++; 00691 00692 return 0; 00693 00694 } 00695 00696 /***************************************************************************** 00697 * * 00698 * ----------------------------- dlist_remove ----------------------------- * 00699 * * 00700 *****************************************************************************/ 00701 00702 int dlist_remove(DList *list, DListElmt *element, void **data) { 00703 00704 /***************************************************************************** 00705 * * 00706 * Do not allow a NULL element or removal from an empty list. * 00707 * * 00708 *****************************************************************************/ 00709 00710 if (element == NULL || dlist_size(list) == 0) 00711 return -1; 00712 00713 /***************************************************************************** 00714 * * 00715 * Remove the element from the list. * 00716 * * 00717 *****************************************************************************/ 00718 00719 *data = element->data; 00720 00721 if (element == list->head) { 00722 00723 /************************************************************************** 00724 * * 00725 * Handle removal from the head of the list. * 00726 * * 00727 **************************************************************************/ 00728 00729 list->head = element->next; 00730 00731 if (list->head == NULL) 00732 list->tail = NULL; 00733 else 00734 element->next->prev = NULL; 00735 00736 } 00737 00738 else { 00739 00740 /************************************************************************** 00741 * * 00742 * Handle removal from other than the head of the list. * 00743 * * 00744 **************************************************************************/ 00745 00746 element->prev->next = element->next; 00747 00748 if (element->next == NULL) 00749 list->tail = element->prev; 00750 else 00751 element->next->prev = element->prev; 00752 00753 } 00754 00755 /***************************************************************************** 00756 * * 00757 * Free the storage allocated by the abstract data type. * 00758 * * 00759 *****************************************************************************/ 00760 00761 free(element); 00762 00763 /***************************************************************************** 00764 * * 00765 * Adjust the size of the list to account for the removed element. * 00766 * * 00767 *****************************************************************************/ 00768 00769 list->size--; 00770 00771 return 0; 00772 00773 } 00774