summaryrefslogtreecommitdiff
path: root/src/llist.c
AgeCommit message (Collapse)Author
2012-06-30src/llist.c: Compare data pointers if callback is NULLLukas Fleischer
If a NULL callback is passed to llist_find_*(), fall back to comparing data pointers. The check for a NULL callback pointer is done outside the main loop with an eye towards performance. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2012-06-30Allow passing more complex data to list callbacksLukas Fleischer
Change the data type of the "data" parameter from "long" to "void *" in llist_find_*() signatures to allow for passing more complex objects. Change all llist_find_*() invocations and callbacks accordingly. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2012-05-21Switch to Linux kernel coding styleLukas Fleischer
Convert our code base to adhere to Linux kernel coding style using Lindent, with the following exceptions: * Use spaces, instead of tabs, for indentation. * Use 2-character indentations (instead of 8 characters). Rationale: We currently have too much levels of indentation. Using 8-character tabs would make huge code parts unreadable. These need to be cleaned up before we can switch to 8 characters. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2012-03-26Update copyright rangesLukas Fleischer
Add 2012 to the copyright range for all source and documentation files. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2012-02-16src/llist.c: Bail out early on negative indexesLukas Fleischer
Make sure we don't return bogus list elements if negative indexes are used in llist_{,find_}nth(). Bail out early and return NULL instead. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-10-05src/llist.c: Add llist_next_filter()Lukas Fleischer
This convenience function can be used to return the successor of a list item if it is matched by a filter callback and return NULL otherwise. We will use this for an improved version of the LLIST_FIND_FOREACH macro that can be used whenever results are known to be continuous. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-10-05src/llist.c: Add a tail pointerLukas Fleischer
Adding a tail pointer to each list increases memory footprint by four bytes, while reducing the runtime of llist_add() from O(n) to O(1). In testing, the time required to append 100000 elements to a linked list was reduced from 29.245s to 0.009s. Our second main concern is to reduce the runtime of llist_add_sorted() when inserting elements from a presorted list (this is reduced from O(n) to O(1) as well), since the data files contain appointments in sorted order and are always processed front to back. Some local numbers show how this speeds up calcurse startup (test set with 50000 appointments): 0.22user 0.12system 0:00.35elapsed 99%CPU (0avgtext+0avgdata 5396maxresident)k 0inputs+8outputs (0major+1398minor)pagefaults 0swaps As opposed to the unpatched binary: 21.97user 0.25system 0:22.23elapsed 99%CPU (0avgtext+0avgdata 5388maxresident)k 0inputs+48outputs (0major+1396minor)pagefaults 0swaps This is a ~10000% increase in speed. Timings for reading random input files generated by a script stay the same (32.391s vs. 31.776s). Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-06-20src/llist.c: Use stable insertion algorithmLukas Fleischer
Ensure the relative order of elements with equal keys is maintained when inserting into a sorted list. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-06-09Fix whitespace issuesLukas Fleischer
Strip trailing whitespaces in all source files. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-04-22Update copyright notices in source files, documentation and "COPYING".Lukas Fleischer
* Update copyright dates (use 2004-2011 as date range everywhere). * Change copyright holder from "Frederic Culot" to "calcurse Development Team". Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-04-22Add comments to linked list functions.Lukas Fleischer
Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-04-22llist.c: Nullify pointers after free()'ing.Lukas Fleischer
* Set all data members to "NULL" in llist_free_inner() after freeing them. Altough we normally shouldn't continue working with a list that already went through llist_free_inner(), this will protect against dangling pointer bugs in case anyone will ever come up with the idea of doing so. * Set list head to "NULL" in llist_free(), basically to put the list into an initialized state. Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
2011-04-19Add linked lists implementation.Lukas Fleischer
As discussed on the mailing lists, the various linked list implementations we currently use at a dozen of different places in the calcurse source tree are inconvenient and should be replaced by a single generic solution. This is a first approach to introduce such a generic implemetation. It provides following functions: * llist_init(): Initialize a list. * llist_free_inner(): Loop through a list and free all items. * llist_free(): Free the list itself (but not the individual items). * llist_first(): Get the first item of a list. * llist_nth(): Get the nth item of a list. * llist_next(): Get the successor of a list item. * llist_find_first(): Find an item using a callback function. * llist_find_next(): Find the next match using a callback function. * llist_find_nth(): Find the nth item in a list (using a callback). * llist_get_data(): Get a pointer to the actual data of a list item. * llist_add(): Add an item at the end of a list. * llist_add_sorted(): Add an item to a sorted list (using a comparison callback function). * llist_remove(): Remove an item from a list. Linked lists are stored in "llist_t" structures, list items are to be stored in "llist_item_t" structs. All of the llist_*() functions either expect a pointer to a llist_t structure (in case the function operates on the list itself) or a pointer to a llist_item_t (llist_*_next() and llist_get_data()). Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>