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. Peter ------------------------------------------------------------------------------ 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 enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
