- float cat, x;
- 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)
- {
- category_name[category_draw_count] = cat;
- category_item[category_draw_count] = i;
+ // 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.
+ if(gethostcachenumber(SLIST_FIELD_CATEGORY, first) != x)
+ error("Category mismatch I");
+ if(first > 0)
+ if(gethostcachenumber(SLIST_FIELD_CATEGORY, first - 1) == x)
+ error("Category mismatch II");
+ category_name[category_draw_count] = x;
+ category_item[category_draw_count] = first;
+ ++category_draw_count;
+ 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;
+ }
+ }
+ if (catl == x) {
+ if(gethostcachenumber(SLIST_FIELD_CATEGORY, last) != x)
+ error("Category mismatch III");
+ if(last > 0)
+ if(gethostcachenumber(SLIST_FIELD_CATEGORY, last - 1) == x)
+ error("Category mismatch IV");
+ category_name[category_draw_count] = x;
+ category_item[category_draw_count] = last;