libalpm
Arch Linux Package Manager Library
|
00001 /* 00002 * alpm_list.c 00003 * 00004 * Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org> 00005 * Copyright (c) 2002-2006 by Judd Vinet <jvinet@zeroflux.org> 00006 * 00007 * This program is free software; you can redistribute it and/or modify 00008 * it under the terms of the GNU General Public License as published by 00009 * the Free Software Foundation; either version 2 of the License, or 00010 * (at your option) any later version. 00011 * 00012 * This program is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00019 */ 00020 00021 #include <stdlib.h> 00022 #include <string.h> 00023 00024 /* libalpm */ 00025 #include "alpm_list.h" 00026 00027 /* check exported library symbols with: nm -C -D <lib> */ 00028 #define SYMEXPORT __attribute__((visibility("default"))) 00029 #define SYMHIDDEN __attribute__((visibility("internal"))) 00030 00031 /** 00032 * @addtogroup alpm_list List Functions 00033 * @brief Functions to manipulate alpm_list_t lists. 00034 * 00035 * These functions are designed to create, destroy, and modify lists of 00036 * type alpm_list_t. This is an internal list type used by libalpm that is 00037 * publicly exposed for use by frontends if desired. 00038 * 00039 * @{ */ 00040 00041 /* Allocation */ 00042 00043 /** 00044 * @brief Free a list, but not the contained data. 00045 * 00046 * @param list the list to free 00047 */ 00048 void SYMEXPORT alpm_list_free(alpm_list_t *list) 00049 { 00050 alpm_list_t *it = list; 00051 00052 while(it) { 00053 alpm_list_t *tmp = it->next; 00054 free(it); 00055 it = tmp; 00056 } 00057 } 00058 00059 /** 00060 * @brief Free the internal data of a list structure. 00061 * 00062 * @param list the list to free 00063 * @param fn a free function for the internal data 00064 */ 00065 void SYMEXPORT alpm_list_free_inner(alpm_list_t *list, alpm_list_fn_free fn) 00066 { 00067 alpm_list_t *it = list; 00068 00069 while(it) { 00070 if(fn && it->data) { 00071 fn(it->data); 00072 } 00073 it = it->next; 00074 } 00075 } 00076 00077 00078 /* Mutators */ 00079 00080 /** 00081 * @brief Add a new item to the end of the list. 00082 * 00083 * @param list the list to add to 00084 * @param data the new item to be added to the list 00085 * 00086 * @return the resultant list 00087 */ 00088 alpm_list_t SYMEXPORT *alpm_list_add(alpm_list_t *list, void *data) 00089 { 00090 alpm_list_t *ptr, *lp; 00091 00092 ptr = malloc(sizeof(alpm_list_t)); 00093 if(ptr == NULL) { 00094 return list; 00095 } 00096 00097 ptr->data = data; 00098 ptr->next = NULL; 00099 00100 /* Special case: the input list is empty */ 00101 if(list == NULL) { 00102 ptr->prev = ptr; 00103 return ptr; 00104 } 00105 00106 lp = alpm_list_last(list); 00107 lp->next = ptr; 00108 ptr->prev = lp; 00109 list->prev = ptr; 00110 00111 return list; 00112 } 00113 00114 /** 00115 * @brief Add items to a list in sorted order. 00116 * 00117 * @param list the list to add to 00118 * @param data the new item to be added to the list 00119 * @param fn the comparison function to use to determine order 00120 * 00121 * @return the resultant list 00122 */ 00123 alpm_list_t SYMEXPORT *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cmp fn) 00124 { 00125 if(!fn || !list) { 00126 return alpm_list_add(list, data); 00127 } else { 00128 alpm_list_t *add = NULL, *prev = NULL, *next = list; 00129 00130 add = malloc(sizeof(alpm_list_t)); 00131 if(add == NULL) { 00132 return list; 00133 } 00134 add->data = data; 00135 00136 /* Find insertion point. */ 00137 while(next) { 00138 if(fn(add->data, next->data) <= 0) break; 00139 prev = next; 00140 next = next->next; 00141 } 00142 00143 /* Insert the add node to the list */ 00144 if(prev == NULL) { /* special case: we insert add as the first element */ 00145 add->prev = list->prev; /* list != NULL */ 00146 add->next = list; 00147 list->prev = add; 00148 return add; 00149 } else if(next == NULL) { /* another special case: add last element */ 00150 add->prev = prev; 00151 add->next = NULL; 00152 prev->next = add; 00153 list->prev = add; 00154 return list; 00155 } else { 00156 add->prev = prev; 00157 add->next = next; 00158 next->prev = add; 00159 prev->next = add; 00160 return list; 00161 } 00162 } 00163 } 00164 00165 /** 00166 * @brief Join two lists. 00167 * The two lists must be independent. Do not free the original lists after 00168 * calling this function, as this is not a copy operation. The list pointers 00169 * passed in should be considered invalid after calling this function. 00170 * 00171 * @param first the first list 00172 * @param second the second list 00173 * 00174 * @return the resultant joined list 00175 */ 00176 alpm_list_t SYMEXPORT *alpm_list_join(alpm_list_t *first, alpm_list_t *second) 00177 { 00178 alpm_list_t *tmp; 00179 00180 if(first == NULL) { 00181 return second; 00182 } 00183 if(second == NULL) { 00184 return first; 00185 } 00186 /* tmp is the last element of the first list */ 00187 tmp = first->prev; 00188 /* link the first list to the second */ 00189 tmp->next = second; 00190 /* link the second list to the first */ 00191 first->prev = second->prev; 00192 /* set the back reference to the tail */ 00193 second->prev = tmp; 00194 00195 return first; 00196 } 00197 00198 /** 00199 * @brief Merge the two sorted sublists into one sorted list. 00200 * 00201 * @param left the first list 00202 * @param right the second list 00203 * @param fn comparison function for determining merge order 00204 * 00205 * @return the resultant list 00206 */ 00207 alpm_list_t SYMEXPORT *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, 00208 alpm_list_fn_cmp fn) 00209 { 00210 alpm_list_t *newlist, *lp, *tail_ptr, *left_tail_ptr, *right_tail_ptr; 00211 00212 if(left == NULL) { 00213 return right; 00214 } 00215 if(right == NULL) { 00216 return left; 00217 } 00218 00219 /* Save tail node pointers for future use */ 00220 left_tail_ptr = left->prev; 00221 right_tail_ptr = right->prev; 00222 00223 if(fn(left->data, right->data) <= 0) { 00224 newlist = left; 00225 left = left->next; 00226 } 00227 else { 00228 newlist = right; 00229 right = right->next; 00230 } 00231 newlist->prev = NULL; 00232 newlist->next = NULL; 00233 lp = newlist; 00234 00235 while((left != NULL) && (right != NULL)) { 00236 if(fn(left->data, right->data) <= 0) { 00237 lp->next = left; 00238 left->prev = lp; 00239 left = left->next; 00240 } 00241 else { 00242 lp->next = right; 00243 right->prev = lp; 00244 right = right->next; 00245 } 00246 lp = lp->next; 00247 lp->next = NULL; 00248 } 00249 if(left != NULL) { 00250 lp->next = left; 00251 left->prev = lp; 00252 tail_ptr = left_tail_ptr; 00253 } 00254 else if(right != NULL) { 00255 lp->next = right; 00256 right->prev = lp; 00257 tail_ptr = right_tail_ptr; 00258 } 00259 else { 00260 tail_ptr = lp; 00261 } 00262 00263 newlist->prev = tail_ptr; 00264 00265 return newlist; 00266 } 00267 00268 /** 00269 * @brief Sort a list of size `n` using mergesort algorithm. 00270 * 00271 * @param list the list to sort 00272 * @param n the size of the list 00273 * @param fn the comparison function for determining order 00274 * 00275 * @return the resultant list 00276 */ 00277 alpm_list_t SYMEXPORT *alpm_list_msort(alpm_list_t *list, size_t n, 00278 alpm_list_fn_cmp fn) 00279 { 00280 if(n > 1) { 00281 size_t half = n / 2; 00282 size_t i = half - 1; 00283 alpm_list_t *left = list, *lastleft = list, *right; 00284 00285 while(i--) { 00286 lastleft = lastleft->next; 00287 } 00288 right = lastleft->next; 00289 /* terminate first list */ 00290 lastleft->next = NULL; 00291 00292 left = alpm_list_msort(left, half, fn); 00293 right = alpm_list_msort(right, n - half, fn); 00294 list = alpm_list_mmerge(left, right, fn); 00295 } 00296 return list; 00297 } 00298 00299 /** 00300 * @brief Remove an item from the list. 00301 * item is not freed; this is the responsibility of the caller. 00302 * 00303 * @param haystack the list to remove the item from 00304 * @param item the item to remove from the list 00305 * 00306 * @return the resultant list 00307 */ 00308 alpm_list_t SYMEXPORT *alpm_list_remove_item(alpm_list_t *haystack, 00309 alpm_list_t *item) 00310 { 00311 if(haystack == NULL || item == NULL) { 00312 return haystack; 00313 } 00314 00315 if(item == haystack) { 00316 /* Special case: removing the head node which has a back reference to 00317 * the tail node */ 00318 haystack = item->next; 00319 if(haystack) { 00320 haystack->prev = item->prev; 00321 } 00322 item->prev = NULL; 00323 } else if(item == haystack->prev) { 00324 /* Special case: removing the tail node, so we need to fix the back 00325 * reference on the head node. We also know tail != head. */ 00326 if(item->prev) { 00327 /* i->next should always be null */ 00328 item->prev->next = item->next; 00329 haystack->prev = item->prev; 00330 item->prev = NULL; 00331 } 00332 } else { 00333 /* Normal case, non-head and non-tail node */ 00334 if(item->next) { 00335 item->next->prev = item->prev; 00336 } 00337 if(item->prev) { 00338 item->prev->next = item->next; 00339 } 00340 } 00341 00342 return haystack; 00343 } 00344 00345 00346 /** 00347 * @brief Remove an item from the list. 00348 * 00349 * @param haystack the list to remove the item from 00350 * @param needle the data member of the item we're removing 00351 * @param fn the comparison function for searching 00352 * @param data output parameter containing data of the removed item 00353 * 00354 * @return the resultant list 00355 */ 00356 alpm_list_t SYMEXPORT *alpm_list_remove(alpm_list_t *haystack, 00357 const void *needle, alpm_list_fn_cmp fn, void **data) 00358 { 00359 alpm_list_t *i = haystack; 00360 00361 if(data) { 00362 *data = NULL; 00363 } 00364 00365 if(needle == NULL) { 00366 return haystack; 00367 } 00368 00369 while(i) { 00370 if(i->data == NULL) { 00371 i = i->next; 00372 continue; 00373 } 00374 if(fn(i->data, needle) == 0) { 00375 haystack = alpm_list_remove_item(haystack, i); 00376 00377 if(data) { 00378 *data = i->data; 00379 } 00380 free(i); 00381 break; 00382 } else { 00383 i = i->next; 00384 } 00385 } 00386 00387 return haystack; 00388 } 00389 00390 /** 00391 * @brief Remove a string from a list. 00392 * 00393 * @param haystack the list to remove the item from 00394 * @param needle the data member of the item we're removing 00395 * @param data output parameter containing data of the removed item 00396 * 00397 * @return the resultant list 00398 */ 00399 alpm_list_t SYMEXPORT *alpm_list_remove_str(alpm_list_t *haystack, 00400 const char *needle, char **data) 00401 { 00402 return alpm_list_remove(haystack, (const void *)needle, 00403 (alpm_list_fn_cmp)strcmp, (void **)data); 00404 } 00405 00406 /** 00407 * @brief Create a new list without any duplicates. 00408 * 00409 * This does NOT copy data members. 00410 * 00411 * @param list the list to copy 00412 * 00413 * @return a new list containing non-duplicate items 00414 */ 00415 alpm_list_t SYMEXPORT *alpm_list_remove_dupes(const alpm_list_t *list) 00416 { 00417 const alpm_list_t *lp = list; 00418 alpm_list_t *newlist = NULL; 00419 while(lp) { 00420 if(!alpm_list_find_ptr(newlist, lp->data)) { 00421 newlist = alpm_list_add(newlist, lp->data); 00422 } 00423 lp = lp->next; 00424 } 00425 return newlist; 00426 } 00427 00428 /** 00429 * @brief Copy a string list, including data. 00430 * 00431 * @param list the list to copy 00432 * 00433 * @return a copy of the original list 00434 */ 00435 alpm_list_t SYMEXPORT *alpm_list_strdup(const alpm_list_t *list) 00436 { 00437 const alpm_list_t *lp = list; 00438 alpm_list_t *newlist = NULL; 00439 while(lp) { 00440 newlist = alpm_list_add(newlist, strdup(lp->data)); 00441 lp = lp->next; 00442 } 00443 return newlist; 00444 } 00445 00446 /** 00447 * @brief Copy a list, without copying data. 00448 * 00449 * @param list the list to copy 00450 * 00451 * @return a copy of the original list 00452 */ 00453 alpm_list_t SYMEXPORT *alpm_list_copy(const alpm_list_t *list) 00454 { 00455 const alpm_list_t *lp = list; 00456 alpm_list_t *newlist = NULL; 00457 while(lp) { 00458 newlist = alpm_list_add(newlist, lp->data); 00459 lp = lp->next; 00460 } 00461 return newlist; 00462 } 00463 00464 /** 00465 * @brief Copy a list and copy the data. 00466 * Note that the data elements to be copied should not contain pointers 00467 * and should also be of constant size. 00468 * 00469 * @param list the list to copy 00470 * @param size the size of each data element 00471 * 00472 * @return a copy of the original list, data copied as well 00473 */ 00474 alpm_list_t SYMEXPORT *alpm_list_copy_data(const alpm_list_t *list, 00475 size_t size) 00476 { 00477 const alpm_list_t *lp = list; 00478 alpm_list_t *newlist = NULL; 00479 while(lp) { 00480 void *newdata = malloc(size); 00481 if(newdata) { 00482 memcpy(newdata, lp->data, size); 00483 newlist = alpm_list_add(newlist, newdata); 00484 lp = lp->next; 00485 } 00486 } 00487 return newlist; 00488 } 00489 00490 /** 00491 * @brief Create a new list in reverse order. 00492 * 00493 * @param list the list to copy 00494 * 00495 * @return a new list in reverse order 00496 */ 00497 alpm_list_t SYMEXPORT *alpm_list_reverse(alpm_list_t *list) 00498 { 00499 const alpm_list_t *lp; 00500 alpm_list_t *newlist = NULL, *backup; 00501 00502 if(list == NULL) { 00503 return NULL; 00504 } 00505 00506 lp = alpm_list_last(list); 00507 /* break our reverse circular list */ 00508 backup = list->prev; 00509 list->prev = NULL; 00510 00511 while(lp) { 00512 newlist = alpm_list_add(newlist, lp->data); 00513 lp = lp->prev; 00514 } 00515 list->prev = backup; /* restore tail pointer */ 00516 return newlist; 00517 } 00518 00519 /* Accessors */ 00520 00521 /** 00522 * @brief Return nth element from list (starting from 0). 00523 * 00524 * @param list the list 00525 * @param n the index of the item to find (n < alpm_list_count(list) IS needed) 00526 * 00527 * @return an alpm_list_t node for index `n` 00528 */ 00529 alpm_list_t SYMEXPORT *alpm_list_nth(const alpm_list_t *list, size_t n) 00530 { 00531 const alpm_list_t *i = list; 00532 while(n--) { 00533 i = i->next; 00534 } 00535 return (alpm_list_t *)i; 00536 } 00537 00538 /** 00539 * @brief Get the next element of a list. 00540 * 00541 * @param node the list node 00542 * 00543 * @return the next element, or NULL when no more elements exist 00544 */ 00545 inline alpm_list_t SYMEXPORT *alpm_list_next(const alpm_list_t *node) 00546 { 00547 if(node) { 00548 return node->next; 00549 } else { 00550 return NULL; 00551 } 00552 } 00553 00554 /** 00555 * @brief Get the previous element of a list. 00556 * 00557 * @param list the list head 00558 * 00559 * @return the previous element, or NULL when no previous element exist 00560 */ 00561 inline alpm_list_t SYMEXPORT *alpm_list_previous(const alpm_list_t *list) 00562 { 00563 if(list && list->prev->next) { 00564 return list->prev; 00565 } else { 00566 return NULL; 00567 } 00568 } 00569 00570 /** 00571 * @brief Get the last item in the list. 00572 * 00573 * @param list the list 00574 * 00575 * @return the last element in the list 00576 */ 00577 alpm_list_t SYMEXPORT *alpm_list_last(const alpm_list_t *list) 00578 { 00579 if(list) { 00580 return list->prev; 00581 } else { 00582 return NULL; 00583 } 00584 } 00585 00586 /* Misc */ 00587 00588 /** 00589 * @brief Get the number of items in a list. 00590 * 00591 * @param list the list 00592 * 00593 * @return the number of list items 00594 */ 00595 size_t SYMEXPORT alpm_list_count(const alpm_list_t *list) 00596 { 00597 size_t i = 0; 00598 const alpm_list_t *lp = list; 00599 while(lp) { 00600 ++i; 00601 lp = lp->next; 00602 } 00603 return i; 00604 } 00605 00606 /** 00607 * @brief Find an item in a list. 00608 * 00609 * @param needle the item to search 00610 * @param haystack the list 00611 * @param fn the comparison function for searching (!= NULL) 00612 * 00613 * @return `needle` if found, NULL otherwise 00614 */ 00615 void SYMEXPORT *alpm_list_find(const alpm_list_t *haystack, const void *needle, 00616 alpm_list_fn_cmp fn) 00617 { 00618 const alpm_list_t *lp = haystack; 00619 while(lp) { 00620 if(lp->data && fn(lp->data, needle) == 0) { 00621 return lp->data; 00622 } 00623 lp = lp->next; 00624 } 00625 return NULL; 00626 } 00627 00628 /* trivial helper function for alpm_list_find_ptr */ 00629 static int ptr_cmp(const void *p, const void *q) 00630 { 00631 return (p != q); 00632 } 00633 00634 /** 00635 * @brief Find an item in a list. 00636 * 00637 * Search for the item whose data matches that of the `needle`. 00638 * 00639 * @param needle the data to search for (== comparison) 00640 * @param haystack the list 00641 * 00642 * @return `needle` if found, NULL otherwise 00643 */ 00644 void SYMEXPORT *alpm_list_find_ptr(const alpm_list_t *haystack, 00645 const void *needle) 00646 { 00647 return alpm_list_find(haystack, needle, ptr_cmp); 00648 } 00649 00650 /** 00651 * @brief Find a string in a list. 00652 * 00653 * @param needle the string to search for 00654 * @param haystack the list 00655 * 00656 * @return `needle` if found, NULL otherwise 00657 */ 00658 char SYMEXPORT *alpm_list_find_str(const alpm_list_t *haystack, 00659 const char *needle) 00660 { 00661 return (char *)alpm_list_find(haystack, (const void *)needle, 00662 (alpm_list_fn_cmp)strcmp); 00663 } 00664 00665 /** 00666 * @brief Find the differences between list `left` and list `right` 00667 * 00668 * The two lists must be sorted. Items only in list `left` are added to the 00669 * `onlyleft` list. Items only in list `right` are added to the `onlyright` 00670 * list. 00671 * 00672 * @param left the first list 00673 * @param right the second list 00674 * @param fn the comparison function 00675 * @param onlyleft pointer to the first result list 00676 * @param onlyright pointer to the second result list 00677 * 00678 */ 00679 void SYMEXPORT alpm_list_diff_sorted(const alpm_list_t *left, 00680 const alpm_list_t *right, alpm_list_fn_cmp fn, 00681 alpm_list_t **onlyleft, alpm_list_t **onlyright) 00682 { 00683 const alpm_list_t *l = left; 00684 const alpm_list_t *r = right; 00685 00686 if(!onlyleft && !onlyright) { 00687 return; 00688 } 00689 00690 while(l != NULL && r != NULL) { 00691 int cmp = fn(l->data, r->data); 00692 if(cmp < 0) { 00693 if(onlyleft) { 00694 *onlyleft = alpm_list_add(*onlyleft, l->data); 00695 } 00696 l = l->next; 00697 } 00698 else if(cmp > 0) { 00699 if(onlyright) { 00700 *onlyright = alpm_list_add(*onlyright, r->data); 00701 } 00702 r = r->next; 00703 } else { 00704 l = l->next; 00705 r = r->next; 00706 } 00707 } 00708 while(l != NULL) { 00709 if(onlyleft) { 00710 *onlyleft = alpm_list_add(*onlyleft, l->data); 00711 } 00712 l = l->next; 00713 } 00714 while(r != NULL) { 00715 if(onlyright) { 00716 *onlyright = alpm_list_add(*onlyright, r->data); 00717 } 00718 r = r->next; 00719 } 00720 } 00721 00722 00723 /** 00724 * @brief Find the items in list `lhs` that are not present in list `rhs`. 00725 * 00726 * @param lhs the first list 00727 * @param rhs the second list 00728 * @param fn the comparison function 00729 * 00730 * @return a list containing all items in `lhs` not present in `rhs` 00731 */ 00732 alpm_list_t SYMEXPORT *alpm_list_diff(const alpm_list_t *lhs, 00733 const alpm_list_t *rhs, alpm_list_fn_cmp fn) 00734 { 00735 alpm_list_t *left, *right; 00736 alpm_list_t *ret = NULL; 00737 00738 left = alpm_list_copy(lhs); 00739 left = alpm_list_msort(left, alpm_list_count(left), fn); 00740 right = alpm_list_copy(rhs); 00741 right = alpm_list_msort(right, alpm_list_count(right), fn); 00742 00743 alpm_list_diff_sorted(left, right, fn, &ret, NULL); 00744 00745 alpm_list_free(left); 00746 alpm_list_free(right); 00747 return ret; 00748 } 00749 00750 /** 00751 * @brief Copy a list and data into a standard C array of fixed length. 00752 * Note that the data elements are shallow copied so any contained pointers 00753 * will point to the original data. 00754 * 00755 * @param list the list to copy 00756 * @param n the size of the list 00757 * @param size the size of each data element 00758 * 00759 * @return an array version of the original list, data copied as well 00760 */ 00761 void SYMEXPORT *alpm_list_to_array(const alpm_list_t *list, size_t n, 00762 size_t size) 00763 { 00764 size_t i; 00765 const alpm_list_t *item; 00766 char *array; 00767 00768 if(n == 0) { 00769 return NULL; 00770 } 00771 00772 array = malloc(n * size); 00773 if(array == NULL) { 00774 return NULL; 00775 } 00776 for(i = 0, item = list; i < n && item; i++, item = item->next) { 00777 memcpy(array + i * size, item->data, size); 00778 } 00779 return array; 00780 } 00781 00782 /** @} */ 00783 00784 /* vim: set ts=2 sw=2 noet: */