From 17189b86c1745139d87063ff8f0a07c88b4a5970 Mon Sep 17 00:00:00 2001 From: div0 Date: Sat, 23 May 2009 15:52:37 +0000 Subject: [PATCH] mapinfo: do an explicit heapsort for the mapinfo list, to fix problems with "-" in map names git-svn-id: svn://svn.icculus.org/nexuiz/trunk@6757 f962a42d-fe04-0410-a3ab-8c8b0445ebaa --- data/qcsrc/common/mapinfo.qc | 107 ++++++----------------------------- data/qcsrc/common/util.qc | 61 ++++++++++++++++++-- data/qcsrc/common/util.qh | 6 +- data/qcsrc/menu/menu.qh | 1 + 4 files changed, 79 insertions(+), 96 deletions(-) diff --git a/data/qcsrc/common/mapinfo.qc b/data/qcsrc/common/mapinfo.qc index 60ed7ac87..22cac37e6 100644 --- a/data/qcsrc/common/mapinfo.qc +++ b/data/qcsrc/common/mapinfo.qc @@ -1,30 +1,3 @@ -#ifdef HSOI -// HUGE SET - stored in a string -string HugeSetOfIntegers_empty() -{ - return ""; -} -float HugeSetOfIntegers_get(string pArr, float i) -{ - return stof(substring(pArr, i * 4, 4)); -} -float HugeSetOfIntegers_length(string pArr) -{ - return strlen(pArr) / 4; -} -string HugeSetOfIntegers_concat(string a1, string a2) -{ - return strcat(a1, a2); -} -string HugeSetOfIntegers_insert(string a1, float n, string a2) - // special concat function to build up large lists in less time by binary concatenation -{ - string s; - s = strcat(" ", ftos(n)); - return strcat(a1, substring(s, strlen(s) - 4, 4), a2); -} -#endif - // generic string stuff float startsWith(string haystack, string needle) { @@ -159,76 +132,27 @@ void MapInfo_Enumerate() // filter the info by game type mask (updates MapInfo_count) // -#ifdef HSOI -string _MapInfo_filtered; +float _MapInfo_filtered; +float _MapInfo_filtered_allocated; float MapInfo_FilterList_Lookup(float i) { - return MapInfo_FilterList_Lookup(i); -} - -string MapInfo_FilterGametype_Recursive(float pGametype, float pFeatures, float pFlagsRequired, float pFlagsForbidden, float pBegin, float pEnd, float pAbortOnGenerate) -{ - float m, valid; - string l, r; - - if(pBegin == pEnd) - return HugeSetOfIntegers_empty(); - - m = floor((pBegin + pEnd) / 2); - - l = MapInfo_FilterGametype_Recursive(pGametype, pFeatures, pBegin, m, pAbortOnGenerate); - if not(l) - return string_null; // BAIL OUT - if(MapInfo_Get_ByName(_MapInfo_GlobItem(m), 1, 0) == 2) // if we generated one... BAIL OUT and let the caller continue in the next frame. - if(pAbortOnGenerate) - { - MapInfo_progress = m / _MapInfo_globcount; - return string_null; // BAIL OUT - } - valid = (((MapInfo_Map_supportedGametypes & pGametype) != 0); - valid = valid && ((MapInfo_Map_supportedFeatures & pFeatures) == pFeatures)); - valid = valid && (MapInfo_Map_flags & pFlagsForbidden == 0); - valid = valid && (MapInfo_Map_flags & pFlagsRequired == pFlagsRequired); - r = MapInfo_FilterGametype_Recursive(pGametype, pFeatures, pFlagsRequired, pFlagsForbidden, m + 1, pEnd, pAbortOnGenerate); - if not(r) - return string_null; // BAIL OUT - - if(valid) - return HugeSetOfIntegers_insert(l, m, r); - else - return HugeSetOfIntegers_concat(l, r); + return stof(bufstr_get(_MapInfo_filtered, i)); } -float MapInfo_FilterGametype(float pGametype, float pFeatures, float pFlagsRequired, float pFlagsForbidden, float pAbortOnGenerate) +void _MapInfo_FilterList_swap(float i, float j, entity pass) { - if(_MapInfo_filtered) - strunzone(_MapInfo_filtered); - _MapInfo_filtered = MapInfo_FilterGametype_Recursive(pGametype, pFeatures, pFlagsRequired, pFlagsForbidden, 0, _MapInfo_globcount, pAbortOnGenerate); - if not(_MapInfo_filtered) - { - dprint("Autogenerated a .mapinfo, doing the rest later.\n"); - return 0; - } - _MapInfo_filtered = strzone(_MapInfo_filtered); - MapInfo_count = HugeSetOfIntegers_length(_MapInfo_filtered); - MapInfo_ClearTemps(); - return 1; + string h; + h = bufstr_get(_MapInfo_filtered, i); + bufstr_set(_MapInfo_filtered, i, bufstr_get(_MapInfo_filtered, j)); + bufstr_set(_MapInfo_filtered, j, h); } -void MapInfo_Filter_Free() +float _MapInfo_FilterList_cmp(float i, float j, entity pass) { - if(_MapInfo_filtered) - { - strunzone(_MapInfo_filtered); - _MapInfo_filtered = string_null; - } -} -#else -float _MapInfo_filtered; -float _MapInfo_filtered_allocated; -float MapInfo_FilterList_Lookup(float i) -{ - return stof(bufstr_get(_MapInfo_filtered, i)); + string a, b; + a = _MapInfo_GlobItem(stof(bufstr_get(_MapInfo_filtered, i))); + b = _MapInfo_GlobItem(stof(bufstr_get(_MapInfo_filtered, j))); + return strcasecmp(a, b); } float MapInfo_FilterGametype(float pGametype, float pFeatures, float pFlagsRequired, float pFlagsForbidden, float pAbortOnGenerate) @@ -257,6 +181,10 @@ float MapInfo_FilterGametype(float pGametype, float pFeatures, float pFlagsRequi } MapInfo_count = j + 1; MapInfo_ClearTemps(); + + // sometimes the glob isn't sorted nicely, so fix it here... + heapsort(MapInfo_count, _MapInfo_FilterList_swap, _MapInfo_FilterList_cmp, world); + return 1; } @@ -268,7 +196,6 @@ void MapInfo_Filter_Free() _MapInfo_filtered_allocated = 0; } } -#endif // load info about the i-th map into the MapInfo_Map_* globals string MapInfo_BSPName_ByID(float i) diff --git a/data/qcsrc/common/util.qc b/data/qcsrc/common/util.qc index d4b2eeec4..86c0e8f16 100644 --- a/data/qcsrc/common/util.qc +++ b/data/qcsrc/common/util.qc @@ -1328,7 +1328,7 @@ float isGametypeInFilter(float gt, float tp, string pattern) return 1; } -void shuffle(float n, shuffle_swapfunc_t swap) +void shuffle(float n, swapfunc_t swap, entity pass) { float i, j; for(i = 1; i < n; ++i) @@ -1344,7 +1344,7 @@ void shuffle(float n, shuffle_swapfunc_t swap) // q.e.d. j = floor(random() * (i + 1)); if(j != i) - swap(j, i); + swap(j, i, pass); } } @@ -1374,7 +1374,7 @@ string swapwords(string str, float i, float j) } string _shufflewords_str; -void _shufflewords_swapfunc(float i, float j) +void _shufflewords_swapfunc(float i, float j, entity pass) { _shufflewords_str = swapwords(_shufflewords_str, i, j); } @@ -1383,7 +1383,7 @@ string shufflewords(string str) float n; _shufflewords_str = str; n = tokenizebyseparator(str, " "); - shuffle(n, _shufflewords_swapfunc); + shuffle(n, _shufflewords_swapfunc, world); str = _shufflewords_str; _shufflewords_str = string_null; return str; @@ -1480,3 +1480,56 @@ vector decompressShotOrigin(float f) v_z = ((f & 0xFF) - 128) / 4; return v; } + +void heapsort(float n, swapfunc_t swap, comparefunc_t cmp, entity pass) +{ + float start, end, root, child; + + // heapify + start = floor((n - 2) / 2); + while(start >= 0) + { + // siftdown(start, count-1); + root = start; + while(root * 2 + 1 <= n-1) + { + child = root * 2 + 1; + if(child < n-1) + if(cmp(child, child+1, pass) < 0) + ++child; + if(cmp(root, child, pass) < 0) + { + swap(root, child, pass); + root = child; + } + else + break; + } + // end of siftdown + --start; + } + + // extract + end = n - 1; + while(end > 0) + { + swap(0, end, pass); + --end; + // siftdown(0, end); + root = 0; + while(root * 2 + 1 <= end) + { + child = root * 2 + 1; + if(child < end && cmp(child, child+1, pass) < 0) + ++child; + if(cmp(root, child, pass) < 0) + { + swap(root, child, pass); + root = child; + } + else + break; + } + // end of siftdown + } +} diff --git a/data/qcsrc/common/util.qh b/data/qcsrc/common/util.qh index c9c0f5bd0..296e4e187 100644 --- a/data/qcsrc/common/util.qh +++ b/data/qcsrc/common/util.qh @@ -140,8 +140,10 @@ string getWrappedLine(float w, textLengthUpToWidth_widthFunction_t tw); float isGametypeInFilter(float gt, float tp, string pattern); -typedef void(float i1, float i2) shuffle_swapfunc_t; // is only ever called for i1 < i2 -void shuffle(float n, shuffle_swapfunc_t swap); +typedef void(float i1, float i2, entity pass) swapfunc_t; // is only ever called for i1 < i2 +typedef float(float i1, float i2, entity pass) comparefunc_t; // <0 for <, ==0 for ==, >0 for > (like strcmp) +void shuffle(float n, swapfunc_t swap, entity pass); +void heapsort(float n, swapfunc_t swap, comparefunc_t cmp, entity pass); string swapwords(string str, float i, float j); string shufflewords(string str); diff --git a/data/qcsrc/menu/menu.qh b/data/qcsrc/menu/menu.qh index 2d96f65d1..a84763156 100644 --- a/data/qcsrc/menu/menu.qh +++ b/data/qcsrc/menu/menu.qh @@ -1,6 +1,7 @@ #define localcmd cmd #define NULL (null_entity) +#define world NULL // constants -- 2.39.2