From 8cedf0c162fcfe347d2f7dccaf33053210c870ca Mon Sep 17 00:00:00 2001 From: Rudolf Polzer Date: Fri, 11 Oct 2013 06:33:13 +0200 Subject: [PATCH] use a proper binary search --- qcsrc/menu/xonotic/serverlist.c | 171 ++++++++++++-------------------- 1 file changed, 61 insertions(+), 110 deletions(-) diff --git a/qcsrc/menu/xonotic/serverlist.c b/qcsrc/menu/xonotic/serverlist.c index 216a98adb..a69f310cc 100644 --- a/qcsrc/menu/xonotic/serverlist.c +++ b/qcsrc/menu/xonotic/serverlist.c @@ -670,124 +670,75 @@ void XonoticServerList_draw(entity me) // ^ unfortunately no such optimization can be made-- we must process through the // entire list, otherwise there is no way to know which item is first in its category. - if(itemcount) - { - // binary search method suggested by div - /*float cat = 0, x; - float first, middle, last; - float newfirst = 0; - float catf = 0, catl = 0; - for(x = 1; x <= category_ent_count; ++x) - { - first = newfirst; - last = (itemcount - 1); - middle = floor((first + last) / 2); - - if( - ((catf = gethostcachenumber(SLIST_FIELD_CATEGORY, first)) < x) - && - ((catl = gethostcachenumber(SLIST_FIELD_CATEGORY, last)) >= x) - ) - { - for(;;) - { - cat = gethostcachenumber(SLIST_FIELD_CATEGORY, middle); - if(cat >= x) { last = middle; } - else if(cat < x) { first = middle; } - if((last - middle) == 1) - { - print(sprintf("highhit: x='%d', dc='%d', first='%d', middle='%d', last='%d', cat='%d'.\n", x, category_draw_count, first, middle, last, cat)); - category_name[category_draw_count] = x; - category_item[category_draw_count] = last; - ++category_draw_count; - ++me.nItems; - newfirst = last; // already scanned through these, skip 'em - break; - } - middle = floor((first + last) / 2); + // binary search method suggested by div + float x; + float begin = 0; + for(x = 1; x <= category_ent_count; ++x) { + float first = begin; + float last = (itemcount - 1); + if (first > last) { + // List is empty. + break; + } + float catf = gethostcachenumber(SLIST_FIELD_CATEGORY, first); + float catl = gethostcachenumber(SLIST_FIELD_CATEGORY, last); + if (catf > x) { + // The first one is already > x. + // Therefore, category x does not exist. + // Higher numbered categories do exist though. + } else if (catl < x) { + // The last one is < x. + // Thus this category - and any following - + // don't exist. + break; + } else if (catf == x) { + // Starts at first. This breaks the loop + // invariant in the binary search and thus has + // to be handled separately. + print(sprintf("hit: x='%d', dc='%d', first='%d', last='%d', catf='%d', catl='%d'.\n", x, category_draw_count, first, last, catf, catl)); + category_name[category_draw_count] = x; + category_item[category_draw_count] = first; + ++category_draw_count; + ++me.nItems; + begin = first + 1; + } else { + // At this point, catf <= x < catl, thus + // catf < catl, thus first < last. + // INVARIANTS: + // last - first >= 1 + // catf == gethostcachenumber(SLIST_FIELD_CATEGORY(first) + // catl == gethostcachenumber(SLIST_FIELD_CATEGORY(last) + // catf < x + // catl >= x + while (last - first > 1) { + float middle = floor((first + last) / 2); + // By loop condition, middle != first && middle != last. + float cat = gethostcachenumber(SLIST_FIELD_CATEGORY, middle); + if (cat >= x) { + last = middle; + catl = cat; + } else { + first = middle; + catf = cat; } } - else if(catf == x) - { - print(sprintf("lowhit: x='%d', dc='%d', first='%d', middle='%d', last='%d', cat='%d'.\n", x, category_draw_count, first, middle, last, catf)); + if (catl == x) { + print(sprintf("hit: x='%d', dc='%d', first='%d', last='%d', catf='%d', catl='%d'.\n", x, category_draw_count, first, last, catf, catl)); category_name[category_draw_count] = x; - category_item[category_draw_count] = first; + category_item[category_draw_count] = last; ++category_draw_count; ++me.nItems; - newfirst = first + 1; // already scanned through these, skip 'em - } - }*/ - - // my binary search method - float cat = 0, x; - float first, middle, last; - float newfirst = 0; - for(x = 1; x <= category_ent_count; ++x) - { - first = newfirst; - last = (itemcount - 1); - middle = floor((first + last) / 2); - - while(first <= last) - { - cat = gethostcachenumber(SLIST_FIELD_CATEGORY, middle); - if(cat > x) { last = middle - 1; } - else if(cat == x) - { - if(middle == 0 || (gethostcachenumber(SLIST_FIELD_CATEGORY, middle - 1) != x)) // check if middle is the first of its category - { - //print(sprintf("hit: x='%d', dc='%d', first='%d', middle='%d', last='%d', cat='%d'.\n", x, category_draw_count, first, middle, last, cat)); - category_name[category_draw_count] = cat; - category_item[category_draw_count] = middle; - ++category_draw_count; - ++me.nItems; - newfirst = middle + 1; // already scanned through these, skip 'em - break; - } - else { last = middle - 1; } // nope, try again - } - else { first = middle + 1; } - middle = floor((first + last) / 2); } + begin = last + 1; // already scanned through these, skip 'em } + } - // old linear search method - /*float cat = 0, i = 0, x = 0; - for(i = 0; i < itemcount; ++i) // FIXME this loop is TOTALLY unacceptable (O(servers)). Make it O(categories * log(servers)). Yes, that is possible. - { - cat = gethostcachenumber(SLIST_FIELD_CATEGORY, i); - if(cat) - { - if(category_draw_count == 0) - { - print(sprintf("hit: i='%d', dc='%d', cat='%d'.\n", i, category_draw_count, cat)); - category_name[category_draw_count] = cat; - category_item[category_draw_count] = i; - ++category_draw_count; - ++me.nItems; - } - else - { - found = 0; - for(x = 0; x < category_draw_count; ++x) { if(cat == category_name[x]) { found = 1; } } - if not(found) - { - print(sprintf("hit: i='%d', dc='%d', cat='%d'.\n", i, category_draw_count, cat)); - category_name[category_draw_count] = cat; - category_item[category_draw_count] = i; - ++category_draw_count; - ++me.nItems; - } - } - } - }*/ - if(autocvar_menu_slist_categories_onlyifmultiple && (category_draw_count == 1)) - { - category_name[0] = -1; - category_item[0] = -1; - category_draw_count = 0; - me.nItems = itemcount; - } + if(autocvar_menu_slist_categories_onlyifmultiple && (category_draw_count == 1)) + { + category_name[0] = -1; + category_item[0] = -1; + category_draw_count = 0; + me.nItems = itemcount; } } else { me.nItems = gethostcachevalue(SLIST_HOSTCACHEVIEWCOUNT); } -- 2.39.2