On Thu, Aug 6, 2009 at 8:18 PM, Peter Wehrfritz<[email protected]> wrote: > Enlightenment SVN wrote: >> Log: >> eina list docs. >> >> * document undocumented functions. >> * note order of magnitude of each function, try to avoid users >> falling into traps. >> >> >> Author: barbieri >> Date: 2009-08-06 08:50:19 -0700 (Thu, 06 Aug 2009) >> New Revision: 41619 >> >> Modified: >> trunk/eina/src/lib/eina_list.c >> >> Modified: trunk/eina/src/lib/eina_list.c >> =================================================================== >> --- trunk/eina/src/lib/eina_list.c 2009-08-06 12:42:38 UTC (rev 41618) >> +++ trunk/eina/src/lib/eina_list.c 2009-08-06 15:50:19 UTC (rev 41619) >> @@ -1412,6 +1412,10 @@ >> * @note @b in-place: this will change the given list, so you should >> * now point to the new list head that is returned by this function. >> * >> + * @note worst case is O(n * log2(n)), O(n) average case. That means >> + * that for 1,000,000 list elements, sort will usually do 1,000,000 >> + * comparisons, but may do up to 20,000,000. >> + * >> * Example: >> * @code >> * int >> @@ -1641,6 +1645,34 @@ >> return ret; >> } >> >> +/** >> + * @brief Returns node nearest to data is in the sorted list. >> + * >> + * @param list The list to search for data, @b must be sorted. >> + * @param func A function pointer that can handle comparing the list data >> nodes. >> + * @param data reference value to search. >> + * @return the nearest node, NULL if not found. >> + * >> + * This can be used to check if some value is inside the list and get >> + * the nearest container node in this case. It should be used when list is >> + * known to be sorted as it will do binary search for results. >> + * >> + * Example: imagine user gives a string, you check if it's in the list >> + * before duplicating its contents, otherwise you want to insert it >> + * sorted. In this case you get the result of this function and either >> + * append or prepend the value. >> + * >> + * @note O(log2(n)) average/worst case performance, for 1,000,000 >> + * elements it will do a maximum of 20 comparisons. This is much >> + * faster than the 1,000,000 comparisons made naively walking the list >> + * from head to tail, so depending on the number of searches and >> + * insertions, it may be worth to eina_list_sort() the list and do he >> + * searches later > > True, you have log2(n) comparisons, but since you do not have random > access to a link list, the time complexity remains O(n). Maybe you > should mention this as well to not accidentally > fool some inexperienced users.
Yes, this is assuming list walks have no cost, but it surely do :-) Will note it there, thanks. -- Gustavo Sverzut Barbieri http://profusion.mobi embedded systems -------------------------------------- MSN: [email protected] Skype: gsbarbieri Mobile: +55 (19) 9225-2202 ------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ enlightenment-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
