The column sorting code in question is for gtk1 only and found in search_gui.c. Take a look at the "search_gui_perform_sort" function which is documented fairly extensively (thanks to some help from richard). This function is called when a user tries to sort a column and all the related sorting utility functions appear directly above it.
Basically, it became apparent when we switched to CTrees from CLists (when we added grouped searches) that the GTK sorting algorithm was unacceptable. My solution was to create a custom algorithm that would be faster than theirs. The quicksort alg. I made worked ok but wasn't as snappy as I would have liked so I ended up recognizing a bunch of cases (sorting by #, reversing an already sorted column) where a specialized sort would be better (in these cases a type of insertion sort). I tried to set up an extendible framework for searches. It's easy to modify the function that anaylizes the tree if you have a case other than those I've identified. It's also easy to add a different type of sort algorithm or to replace an existing on. We were having trouble because the functions GTK provided to manipulate the tree we're O(n*n) themselves. I hacked a couple of them though so this isn't a problem anymore. (These functions will be apparent if you look at the sorting code in place). If you think we should try a new algorithm, take a look at the code and I think you'll see it's not too hard to adapt a generic C sorting algorithm to work for gtk-gnutella if you follow the code I wrote and read the comments. If it works better, great! If you need help with it or want me to implement some algorithm let me know (hopefully you'll provid a good (ie commented and not just cut 'n' paste from the net) generic c implementation and will have some reason for thinking it'll work better). I do have to say that I have my doubts we're going to speed it up by much. In particular, the cases where we're using insertion sort aren't much more than O(n). The difference between passive searches and active searches will hopefully be addressed soon outside of the sorting algorithms so I wouldn't worry about this. Emile On Wed, 2004-01-28 at 01:22, Carl Erhorn wrote: > Hi, Emile. > > I have a question, and depending on the answer, > perhaps > I can help a little with some of the sorting problems. > > > I did a lot of research some years back on sorting > algols, because I was sorting database results sets, > which often were in an almost-sorted condition, or > were in two completely sorted chunks that were being > joined into one, and needed to be resorted so the > entire group were in sorted order. > > I don't know what kind of sort we are using in GTKG, > but I found that quicksort returned almost the very > worst case in these conditions, of all the possible > sorting routines, because of the extreme high > recursion > used in this condidition. For every element that is > already sorted, quicksort calls itself, pushing a huge > amount of data on the stack. The memory use also adds > to the slow times. > > We found that in this case, a standard shell sort > would > return in a very small fraction of the time used by > quicksort. If we are using quicksort, I'd suggest that > we change to shell, and would be glad to provide the > source for this, with whatever interface we need to > use. > > Generally, the interface should look exactly like > quicksort, so that it can be used interchangeably with > the qsort call. So it needs to be passed the same > parameters. > > There is no reason in this day and age that a sort of > less than 10,000 items should take more than a > fraction > of a second, assuming that no one is still running a > 486 or pentium 1 anymore. Most people are running > P-III > or P-4 chips, at speeds of at least 1GHZ or more. If > you can see a sort taking perceptable time, something > is wrong with what we are doing. > > Can you provide details on the type of sort routine, > and the files involved? I have been doing this type of > programming for almost 20 years in C and assembler, so > I think I can be of some help here. > > However, I don't know much about the GTK calls we use, > or why they seem to be so problematic. Because of the > data structures used by GTK, perhaps this causes > problems when sorting. I'd like to know of any special > considerations that have to be taken because of the > GTK data being sorted. For instance, I could not > understand the reason why passive searches needed to > be handled differently from active searches. Normally, > it would not matter what kind of search was being > sorted, but apparently GTK requires some special > handleing of the data that made the two types of data > act differently. > > This is exactly the type of issue I have trouble > getting a handle on, because of my lack of knowledge > in GTK programming. But it might even make sense to > do a little coding to abstract the data from the GTK > display structures, so that both types of searches > could be handled identically. Certainly, the display > of > both types of searches should be almost identical. > > If you could shed a little light, so that I understand > the issues better, I'd be glad to help in any way I > can. > > If you want the information on the sorting routines > for yourself, get your hands on the book called "The > Art of Computer Programming" by D. Knuth. This is the > real programmers bible, and goes into the math behind > all the common sorting and searching routines in great > detail, including the worst case for each one. You > need > volume III of the book, and most libraries have one in > their reference section. They are very expensive, > around $60.00 per volume, as I recall, and they used > to > be much more expensive, about $150 per volume only > about 10 years ago. And although they are a great > reference, they are not a book you would use every > day, > unless you are designing a large commercial program. > > These days, I've found the Richard Stevens books on > TCP/IP programming to be much more useful, as I do a > lot of three-tier client/server interprocess > communication. It's a shame Stevens passed away a year > or so ago, as there will be no more updates from him. > But his books were the best TCP references I have ever > found. > > Anyway, if you have time, and can shed some light for > me on the issues, I'd be glad to help. > > Regards, > --Carl > > ps: is anyone keeping the GTK-2 interface in sync with > GTK-1? I use the GTK-2 libs, and sometimes miss the > new improvements that have been added, because the > GTK-2 interface is not really being supported. > > --- Emile le Vivre <[EMAIL PROTECTED]> wrote: > > This patch addresses some of the column sorting bugs > > in the recent > > flurry of grouped searches updates, mostly to do > > with passive searches. > > Namely, it does: > > > > [GTK1] Count value is now consistently updated for > > all child nodes > > [GTK1] A passive search won't mess up count values > > for other searches > > [GTK1] Sorting by count works as expected in a > > passive search after > > results have maxed out > > > > Richard: It's possible this will fix those weird > > sorting results you > > were getting but I'm not holding my breath. > > > > > > Some gory details: I had to do something messy that > > I'm not that excited > > about but couldn't see another way around. > > Basically I had to make a > > special case in the sorting algorithms for sorting > > by "#" in a passive > > search. This is because once a passive search maxes > > out we are no > > longer adding nodes to that tree but if the other > > searches aren't maxed > > the count values can continue to be increased for > > the search results > > (but the # column is not updated in the passive > > results tree). Then > > when we sort by count in the passive search, it > > sorts by the real count > > value for the regular search tree. The solution I > > chose was to just use > > the text displayed in the column for passive > > searches instead of the > > count value stored in the search result record. > > This is what the user > > expects but involves a bunch of checks and ctree > > retrievals. Sorting is > > slow enough as is so I didn't want to use this for > > all sorts by count, > > only for passive searches. Hopefully there's not > > too many more "special > > cases". > > > > So, sorting by count in a passive search will be a > > little slower than > > sorting by count in a regular search, but it should > > behave correctly. > > > > Also, this raised an interesting question. Now that > > we've added child > > nodes, should they count towards the "max search > > results" value? > > Imagine someone has max search results set to 100, > > they search and they > > get only 5 different results (with 20 sources each). > > Is this expected? > > Or should it refer to 100 parent nodes instead? > > > > Emile > > > > > > -- > > Computer Troubleshooting, New Computer Advice, Virus > > Clean-up, > > Hardware/Software Installs, Web Design, Linux > > Installations: Attune > > Consulting can help. > > http://www.attuneconsulting.com > > [EMAIL PROTECTED] > > > ? gtk-gnutella-current/src/Makefile > > ? gtk-gnutella-current/src/getdate.c > > ? gtk-gnutella-current/src/gtk-gnutella > > Index: gtk-gnutella-current/src/search_gui.c > > > =================================================================== > > RCS file: > > > /cvsroot/gtk-gnutella/gtk-gnutella-current/src/search_gui.c,v > > retrieving revision 1.85 > > diff -u -r1.85 search_gui.c > > --- gtk-gnutella-current/src/search_gui.c 18 Jan > > 2004 19:16:17 -0000 1.85 > > +++ gtk-gnutella-current/src/search_gui.c 26 Jan > > 2004 05:42:41 -0000 > > @@ -513,7 +513,51 @@ > > } > > > > > > -/* Searches results */ > > +/* Search results */ > > + > > + > > +/* > > + * search_gui_compare_passive_count > > + * > > + * If the count column for n1 is greater than that > > for n2, return +1 > > + * 0 if they're equal, and -1 if less than n2 > > + */ > > +gint search_gui_compare_passive_count(GtkCTree > > *ctree, GtkCTreeNode *n1, > > + GtkCTreeNode *n2) > > +{ > > + gchar *temp_str = NULL; > > + gint count1 = 0; > > + gint count2 = 0; > > + gint result = 0; > > + > > + if ((NULL == n1) || (NULL == n2)) > > + return result; > > + > > + if (gtk_ctree_node_get_text(ctree, n1, c_sr_count, > > &temp_str)) { > > + > > + if (0 == strcmp(temp_str, "")) > > + count1 = 1; > > + else > > + count1 = atoi(temp_str); > > + } > > + > > + if (gtk_ctree_node_get_text(ctree, n2, c_sr_count, > > &temp_str)){ > > + > > + if (0 == strcmp(temp_str, "")) > > + count2 = 1; > > + else > > + count2 = atoi(temp_str); > > + } > > + > > + if ((0 != count1) && (0 != count2)) { > > + if (count1 == count2) > > + result = 0; > > + else > > + result = (count1 > count2) ? +1 : -1; > > + } > > + > > + return result; > > +} > > > > > > /* > > @@ -628,7 +672,7 @@ > > * time critical code, some code duplication is > > intentional. > > */ > > GList *search_gui_insert_with_sort(GList *list, > > GtkCTreeNode *node, > > - GtkCTree *ctree, gboolean ascending, gint > > sort_col) > > + GtkCTree *ctree, gboolean ascending, gint > > sort_col, gboolean is_passive) > > { > > GList *l; > > gint i; > > @@ -642,10 +686,18 @@ > > if (ascending) { > > > > for (i = 0, l=list;; l = g_list_next(l), i++) { > > - > > - rlist = gtk_ctree_node_get_row_data(ctree, > > l->data); > > - result = search_gui_compare_records(sort_col, > > rkey, rlist); > > - > > + > > + /* In the case that this is a passive search and > > we're sorting by > > + * count we use the text from the gui column, > > not the count value > > + * held in the record as these two can get out > > of sync. --Emile > > + */ > > + if ((c_sr_count == sort_col) && (is_passive)) > > + result = > > search_gui_compare_passive_count(ctree, node, > > l->data); > > + else { > > + rlist = gtk_ctree_node_get_row_data(ctree, > > l->data); > > + result = search_gui_compare_records(sort_col, > > rkey, rlist); > > + } > > + > > if (result <= 0) { > > /* Our entry is "less" than the > > current (l)*/ > > > > @@ -689,8 +741,16 @@ > > > > for (i = 0, l=list;; l = g_list_next(l), i++) { > > > > - rlist = gtk_ctree_node_get_row_data(ctree, > > l->data); > > - result = search_gui_compare_records(sort_col, > > rkey, rlist); > > + /* In the case that this is a passive search and > > we're sorting by > > + * count we use the text from the gui column, > > not the count value > > + * held in the record as these two can get out > > of sync. --Emile > > + */ > > + if ((c_sr_count == sort_col) && (is_passive)) > > + result = > > search_gui_compare_passive_count(ctree, node, > > l->data); > > + else { > > + rlist = gtk_ctree_node_get_row_data(ctree, > > l->data); > > + result = search_gui_compare_records(sort_col, > > rkey, rlist); > > + } > > > > if (result >= 0) { > > /* Entry is "greater" than the > > current (l)*/ > > @@ -762,8 +822,9 @@ > > * intentional. > > */ > > void search_gui_quick_sort(GArray *array, gint beg, > > gint end, > > - GtkCTree *ctree, gboolean ascending, gint > > sort_col) > > + GtkCTree *ctree, gboolean ascending, gint > > sort_col, gboolean is_passive) > > { > > + GtkCTreeNode *node; > > record_t *rbeg; > > record_t *ri; > > gint i; > > @@ -776,15 +837,24 @@ > > /* Choose the item in the middle for the pivot, > > shift it to the front */ > > search_gui_quick_sort_array_swap(array, beg, > > pivot_index); > > > > - rbeg = gtk_ctree_node_get_row_data(ctree, > > - g_array_index(array, GtkCTreeNode *, beg)); > > + node = g_array_index(array, GtkCTreeNode *, beg); > > + rbeg = gtk_ctree_node_get_row_data(ctree, node); > > > > if (ascending) { > > for (pivot_index = beg, i = beg + 1; i <= end; > > i++) { > > > > - ri = gtk_ctree_node_get_row_data(ctree, > > - g_array_index(array, GtkCTreeNode *, i)); > > - result = search_gui_compare_records(sort_col, > > rbeg, ri); > > + /* In the case that this is a passive search and > > we're sorting by > > + * count we use the text from the gui column, > > not the count value > > + * held in the record as these two can get out > > of sync. --Emile > > + */ > > + if ((c_sr_count == sort_col) && (is_passive)) > > + result = > > search_gui_compare_passive_count(ctree, node, > > + g_array_index(array, GtkCTreeNode *, i)); > > + else { > > + ri = gtk_ctree_node_get_row_data(ctree, > > + g_array_index(array, GtkCTreeNode *, i)); > > + result = search_gui_compare_records(sort_col, > > rbeg, ri); > > + } > > > > if (result == 1) > > search_gui_quick_sort_array_swap(array, > > ++pivot_index, i); > > @@ -792,9 +862,18 @@ > > } else { > > > === message truncated === > > > __________________________________ > Do you Yahoo!? > Yahoo! SiteBuilder - Free web site building tool. Try it! > http://webhosting.yahoo.com/ps/sb/ -- Computer Troubleshooting, New Computer Advice, Virus Clean-up, Hardware/Software Installs, Web Design, Linux Installations: Attune Consulting can help. http://www.attuneconsulting.com [EMAIL PROTECTED] ------------------------------------------------------- The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 3-5 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ Gtk-gnutella-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/gtk-gnutella-devel
