1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/core/smn_sorting.cpp Mon Feb 26 08:21:09 2007 +0000
1.3 @@ -0,0 +1,365 @@
1.4 +/**
1.5 + * ===============================================================
1.6 + * SourceMod (C)2004-2007 AlliedModders LLC. All rights reserved.
1.7 + * ===============================================================
1.8 + *
1.9 + * This file is not open source and may not be copied without explicit
1.10 + * written permission of AlliedModders LLC. This file may not be redistributed
1.11 + * in whole or significant part.
1.12 + * For information, see LICENSE.txt or http://www.sourcemod.net/license.php
1.13 + *
1.14 + * Version: $Id$
1.15 + */
1.16 +
1.17 +#include "sm_globals.h"
1.18 +#include <IHandleSys.h>
1.19 +#include <stdlib.h>
1.20 +
1.21 +/***********************************
1.22 + * About the double array hack *
1.23 + ***************************
1.24 +
1.25 + Double arrays in Pawn are vectors offset by the current offset. For example:
1.26 +
1.27 + new array[2][2]
1.28 +
1.29 + In this array, index 0 contains the offset from the current offset which
1.30 + results in the final vector [2] (at [0][2]). Meaning, to dereference [1][2],
1.31 + it is equivalent to:
1.32 +
1.33 + address = &array[1] + array[1] + 2 * sizeof(cell)
1.34 +
1.35 + The fact that each offset is from the _current_ position rather than the _base_
1.36 + position is very important. It means that if you to try to swap vector positions,
1.37 + the offsets will no longer match, because their current position has changed. A
1.38 + simple and ingenious way around this is to back up the positions in a separate array,
1.39 + then to overwrite each position in the old array with absolute indices. Pseudo C++ code:
1.40 +
1.41 + cell *array; //assumed to be set to the 2+D array
1.42 + cell *old_offsets = new cell[2];
1.43 + for (int i=0; i<2; i++)
1.44 + {
1.45 + old_offsets = array[i];
1.46 + array[i] = i;
1.47 + }
1.48 +
1.49 + Now, you can swap the array indices with no problem, and do a reverse-lookup to find the original addresses.
1.50 + After sorting/modification is done, you must relocate the new indices. For example, if the two vectors in our
1.51 + demo array were swapped, array[0] would be 1 and array[1] would be 0. This is invalid to the virtual machine.
1.52 + Luckily, this is also simple -- all the information is there.
1.53 +
1.54 + for (int i=0; i<2; i++)
1.55 + {
1.56 + //get the # of the vector we want to relocate in
1.57 + cell vector_index = array[i];
1.58 + //get the real address of this vector
1.59 + char *real_address = (char *)array + (vector_index * sizeof(cell)) + old_offsets[vector_index];
1.60 + //calc and store the new distance offset
1.61 + array[i] = real_address - ( (char *)array + (vector_index + sizeof(cell)) )
1.62 + }
1.63 +
1.64 + Note that the inner expression can be heavily reduced; it is expanded for readability.
1.65 + **********************************/
1.66 +
1.67 +enum SortOrder
1.68 +{
1.69 + Sort_Ascending = 0,
1.70 + Sort_Descending = 1,
1.71 +};
1.72 +
1.73 +int sort_ints_asc(const void *int1, const void *int2)
1.74 +{
1.75 + return (*(int *)int1) - (*(int *)int2);
1.76 +}
1.77 +
1.78 +int sort_ints_desc(const void *int1, const void *int2)
1.79 +{
1.80 + return (*(int *)int2) - (*(int *)int1);
1.81 +}
1.82 +
1.83 +static cell_t sm_SortIntegers(IPluginContext *pContext, const cell_t *params)
1.84 +{
1.85 + cell_t *array;
1.86 + cell_t array_size = params[2];
1.87 + cell_t type = params[3];
1.88 +
1.89 + pContext->LocalToPhysAddr(params[1], &array);
1.90 +
1.91 + if (type == Sort_Ascending)
1.92 + {
1.93 + qsort(array, array_size, sizeof(cell_t), sort_ints_asc);
1.94 + } else {
1.95 + qsort(array, array_size, sizeof(cell_t), sort_ints_desc);
1.96 + }
1.97 +
1.98 + return 1;
1.99 +}
1.100 +
1.101 +int sort_floats_asc(const void *float1, const void *float2)
1.102 +{
1.103 + float r1 = *(float *)float1;
1.104 + float r2 = *(float *)float2;
1.105 +
1.106 + if (r1 < r2)
1.107 + {
1.108 + return -1;
1.109 + } else if (r2 < r1) {
1.110 + return 1;
1.111 + } else {
1.112 + return 0;
1.113 + }
1.114 +}
1.115 +
1.116 +int sort_floats_desc(const void *float1, const void *float2)
1.117 +{
1.118 + float r1 = *(float *)float1;
1.119 + float r2 = *(float *)float2;
1.120 +
1.121 + if (r1 < r2)
1.122 + {
1.123 + return 1;
1.124 + } else if (r2 < r1) {
1.125 + return -1;
1.126 + } else {
1.127 + return 0;
1.128 + }
1.129 +}
1.130 +
1.131 +static cell_t sm_SortFloats(IPluginContext *pContext, const cell_t *params)
1.132 +{
1.133 + cell_t *array;
1.134 + cell_t array_size = params[2];
1.135 + cell_t type = params[3];
1.136 +
1.137 + pContext->LocalToPhysAddr(params[1], &array);
1.138 +
1.139 + if (type == Sort_Ascending)
1.140 + {
1.141 + qsort(array, array_size, sizeof(cell_t), sort_floats_asc);
1.142 + } else {
1.143 + qsort(array, array_size, sizeof(cell_t), sort_floats_desc);
1.144 + }
1.145 +
1.146 + return 1;
1.147 +}
1.148 +
1.149 +static cell_t *g_CurStringArray = NULL;
1.150 +static cell_t *g_CurRebaseMap = NULL;
1.151 +
1.152 +int sort_strings_asc(const void *blk1, const void *blk2)
1.153 +{
1.154 + cell_t reloc1 = *(cell_t *)blk1;
1.155 + cell_t reloc2 = *(cell_t *)blk2;
1.156 +
1.157 + char *str1 = ((char *)(&g_CurStringArray[reloc1]) + g_CurRebaseMap[reloc1]);
1.158 + char *str2 = ((char *)(&g_CurStringArray[reloc2]) + g_CurRebaseMap[reloc2]);
1.159 +
1.160 + return strcmp(str1, str2);
1.161 +}
1.162 +
1.163 +int sort_strings_desc(const void *blk1, const void *blk2)
1.164 +{
1.165 + cell_t reloc1 = *(cell_t *)blk1;
1.166 + cell_t reloc2 = *(cell_t *)blk2;
1.167 +
1.168 + char *str1 = ((char *)(&g_CurStringArray[reloc1]) + g_CurRebaseMap[reloc1]);
1.169 + char *str2 = ((char *)(&g_CurStringArray[reloc2]) + g_CurRebaseMap[reloc2]);
1.170 +
1.171 + return strcmp(str2, str1);
1.172 +}
1.173 +
1.174 +static cell_t sm_SortStrings(IPluginContext *pContext, const cell_t *params)
1.175 +{
1.176 + cell_t *array;
1.177 + cell_t array_size = params[2];
1.178 + cell_t type = params[3];
1.179 +
1.180 + pContext->LocalToPhysAddr(params[1], &array);
1.181 +
1.182 + /** HACKHACK - back up the old indices, replace the indices with something easier */
1.183 + cell_t amx_addr, *phys_addr;
1.184 + int err;
1.185 + if ((err=pContext->HeapAlloc(array_size, &amx_addr, &phys_addr)) != SP_ERROR_NONE)
1.186 + {
1.187 + pContext->ThrowNativeErrorEx(err, "Ran out of memory to sort");
1.188 + }
1.189 +
1.190 + g_CurStringArray = array;
1.191 + g_CurRebaseMap = phys_addr;
1.192 +
1.193 + for (int i=0; i<array_size; i++)
1.194 + {
1.195 + phys_addr[i] = array[i];
1.196 + array[i] = i;
1.197 + }
1.198 +
1.199 + if (type == Sort_Ascending)
1.200 + {
1.201 + qsort(array, array_size, sizeof(cell_t), sort_strings_asc);
1.202 + } else {
1.203 + qsort(array, array_size, sizeof(cell_t), sort_strings_desc);
1.204 + }
1.205 +
1.206 + /* END HACKHACK - restore what we damaged so Pawn doesn't throw up.
1.207 + * We'll browse through each index of the array and patch up the distance.
1.208 + */
1.209 + for (int i=0; i<array_size; i++)
1.210 + {
1.211 + /* Compute the final address of the old array and subtract the new location.
1.212 + * This is the fixed up distance.
1.213 + */
1.214 + array[i] = ((char *)&array[array[i]] + phys_addr[array[i]]) - (char *)&array[i];
1.215 + }
1.216 +
1.217 + pContext->HeapPop(amx_addr);
1.218 +
1.219 + g_CurStringArray = NULL;
1.220 + g_CurRebaseMap = NULL;
1.221 +
1.222 + return 1;
1.223 +}
1.224 +
1.225 +struct sort_info
1.226 +{
1.227 + IPluginFunction *pFunc;
1.228 + Handle_t hndl;
1.229 + cell_t array_addr;
1.230 + cell_t *array_base;
1.231 + cell_t *array_remap;
1.232 +};
1.233 +
1.234 +sort_info g_SortInfo;
1.235 +
1.236 +int sort1d_amx_custom(const void *elem1, const void *elem2)
1.237 +{
1.238 + cell_t c1 = *(cell_t *)elem1;
1.239 + cell_t c2 = *(cell_t *)elem2;
1.240 +
1.241 + cell_t result = 0;
1.242 + IPluginFunction *pf = g_SortInfo.pFunc;
1.243 + pf->PushCell(c1);
1.244 + pf->PushCell(c2);
1.245 + pf->PushCell(g_SortInfo.array_addr);
1.246 + pf->PushCell(g_SortInfo.hndl);
1.247 + pf->Execute(&result);
1.248 +
1.249 + return result;
1.250 +}
1.251 +
1.252 +static cell_t sm_SortCustom1D(IPluginContext *pContext, const cell_t *params)
1.253 +{
1.254 + cell_t *array;
1.255 + cell_t array_size = params[2];
1.256 +
1.257 + IPluginFunction *pFunction = pContext->GetFunctionById(params[3]);
1.258 + if (!pFunction)
1.259 + {
1.260 + return pContext->ThrowNativeError("Function %x is not a valid function", params[3]);
1.261 + }
1.262 +
1.263 + pContext->LocalToPhysAddr(params[1], &array);
1.264 +
1.265 + sort_info oldinfo = g_SortInfo;
1.266 +
1.267 +
1.268 + g_SortInfo.hndl = params[4];
1.269 + g_SortInfo.array_addr = params[1];
1.270 + g_SortInfo.array_remap = NULL;
1.271 + g_SortInfo.array_base = NULL;
1.272 + g_SortInfo.pFunc = pFunction;
1.273 +
1.274 + qsort(array, array_size, sizeof(cell_t), sort1d_amx_custom);
1.275 +
1.276 + g_SortInfo = oldinfo;
1.277 +
1.278 + return 1;
1.279 +}
1.280 +
1.281 +int sort2d_amx_custom(const void *elem1, const void *elem2)
1.282 +{
1.283 + cell_t c1 = *(cell_t *)elem1;
1.284 + cell_t c2 = *(cell_t *)elem2;
1.285 +
1.286 + cell_t c1_addr = g_SortInfo.array_addr + (c1 * sizeof(cell_t)) + g_SortInfo.array_remap[c1];
1.287 + cell_t c2_addr = g_SortInfo.array_addr + (c2 * sizeof(cell_t)) + g_SortInfo.array_remap[c2];
1.288 +
1.289 + IPluginContext *pContext = g_SortInfo.pFunc->GetParentContext();
1.290 + cell_t *c1_r, *c2_r;
1.291 + pContext->LocalToPhysAddr(c1_addr, &c1_r);
1.292 + pContext->LocalToPhysAddr(c2_addr, &c2_r);
1.293 +
1.294 + cell_t result = 0;
1.295 + g_SortInfo.pFunc->PushCell(c1_addr);
1.296 + g_SortInfo.pFunc->PushCell(c2_addr);
1.297 + g_SortInfo.pFunc->PushCell(g_SortInfo.array_addr);
1.298 + g_SortInfo.pFunc->PushCell(g_SortInfo.hndl);
1.299 + g_SortInfo.pFunc->Execute(&result);
1.300 +
1.301 + return result;
1.302 +}
1.303 +
1.304 +static cell_t sm_SortCustom2D(IPluginContext *pContext, const cell_t *params)
1.305 +{
1.306 + cell_t *array;
1.307 + cell_t array_size = params[2];
1.308 + IPluginFunction *pFunction;
1.309 +
1.310 + pContext->LocalToPhysAddr(params[1], &array);
1.311 +
1.312 + if ((pFunction=pContext->GetFunctionById(params[3])) == NULL)
1.313 + {
1.314 + return pContext->ThrowNativeError("Function %x is not a valid function", params[3]);
1.315 + }
1.316 +
1.317 + /** back up the old indices, replace the indices with something easier */
1.318 + cell_t amx_addr, *phys_addr;
1.319 + int err;
1.320 + if ((err=pContext->HeapAlloc(array_size, &amx_addr, &phys_addr)) != SP_ERROR_NONE)
1.321 + {
1.322 + pContext->ThrowNativeErrorEx(err, "Ran out of memory to sort");
1.323 + return 0;
1.324 + }
1.325 +
1.326 + sort_info oldinfo = g_SortInfo;
1.327 +
1.328 + g_SortInfo.pFunc = pFunction;
1.329 + g_SortInfo.hndl = params[4];
1.330 + g_SortInfo.array_addr = params[1];
1.331 +
1.332 + /** Same process as in strings, back up the old indices for later fixup */
1.333 + g_SortInfo.array_base = array;
1.334 + g_SortInfo.array_remap = phys_addr;
1.335 +
1.336 + for (int i=0; i<array_size; i++)
1.337 + {
1.338 + phys_addr[i] = array[i];
1.339 + array[i] = i;
1.340 + }
1.341 +
1.342 + qsort(array, array_size, sizeof(cell_t), sort2d_amx_custom);
1.343 +
1.344 + /** Fixup process! */
1.345 + for (int i=0; i<array_size; i++)
1.346 + {
1.347 + /* Compute the final address of the old array and subtract the new location.
1.348 + * This is the fixed up distance.
1.349 + */
1.350 + array[i] = ((char *)&array[array[i]] + phys_addr[array[i]]) - (char *)&array[i];
1.351 + }
1.352 +
1.353 + pContext->HeapPop(amx_addr);
1.354 +
1.355 + g_SortInfo = oldinfo;
1.356 +
1.357 + return 1;
1.358 +}
1.359 +
1.360 +REGISTER_NATIVES(sortNatives)
1.361 +{
1.362 + {"SortIntegers", sm_SortIntegers},
1.363 + {"SortFloats", sm_SortFloats},
1.364 + {"SortStrings", sm_SortStrings},
1.365 + {"SortCustom1D", sm_SortCustom1D},
1.366 + {"SortCustom2D", sm_SortCustom2D},
1.367 + {NULL, NULL},
1.368 +};
