| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
| |
|
|
|
|
|
|
|
| |
* 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>
|
| |
|
|
|
|
|
|
|
|
|
| |
Mostly in preparation to the pending thread-safe list macros. This way,
we have a similar interface to thead-safe and non-thread-safe lists.
This also adds LLIST_FOREACH and LLIST_FIND_FOREACH macros which can be
used as shortcuts when iterating over all list items or a subset of list
items that is accepted by a callback function.
Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>
|
|
|
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>
|
