Result of svn merge -r56700:56797 svn+ssh://svn/svn/linden/branches/more-random into release.

2 files changed, 60 insertions, 69 deletions

diff --git a/indra/lscript/lscript_alloc.h b/indra/lscript/lscript_alloc.h
index 485a65061a..2870364a9c 100644
--- a/indra/lscript/lscript_alloc.h
+++ b/indra/lscript/lscript_alloc.h
@@ -271,74 +271,6 @@ inline LLScriptLibData *lsa_bubble_sort(LLScriptLibData *src, S32 stride, S32 as
 }
 
 
-inline LLScriptLibData *lsa_randomize(LLScriptLibData *src, S32 stride)
-{
-	S32 number = src->getListLength();
-
-	if (number <= 0)
-	{
-		return NULL;
-	}
-
-	if (stride <= 0)
-	{
-		stride = 1;
-	}
-
-	if (number % stride)
-	{
-		LLScriptLibData *retval = src->mListp;
-		src->mListp = NULL;
-		return retval;
-	}
-
-	LLScriptLibData **sortarray = new LLScriptLibData*[number];
-
-	LLScriptLibData *temp = src->mListp;
-	S32 i = 0;
-	while (temp)
-	{
-		sortarray[i] = temp;
-		i++;
-		temp = temp->mListp;
-	}
-
-	S32 k, j, s;
-
-	for (k = 0; k < 20; k++)
-	{
-		for (i = 0; i < number; i += stride)
-		{
-			for (j = i; j < number; j += stride)
-			{
-				if (frand(1.f) > 0.5)
-				{
-					for (s = 0; s < stride; s++)
-					{
-						temp = sortarray[i + s];
-						sortarray[i + s] = sortarray[j + s];
-						sortarray[j + s] = temp;
-					}
-				}
-			}
-		}
-	}
-
-	i = 1;
-	temp = sortarray[0];
-	while (i < number)
-	{
-		temp->mListp = sortarray[i++];
-		temp = temp->mListp;
-	}
-	temp->mListp = NULL;
-
-	src->mListp = NULL;
-
-	LLScriptLibData *ret_value = sortarray[0];
-	delete [] sortarray;
-
-	return ret_value;
-}
+LLScriptLibData* lsa_randomize(LLScriptLibData* src, S32 stride);
 
 #endif
diff --git a/indra/lscript/lscript_library/lscript_alloc.cpp b/indra/lscript/lscript_library/lscript_alloc.cpp
index 8230d181ce..86c8729e9c 100644
--- a/indra/lscript/lscript_library/lscript_alloc.cpp
+++ b/indra/lscript/lscript_library/lscript_alloc.cpp
@@ -1100,3 +1100,62 @@ S32 lsa_postadd_lists(U8 *buffer, S32 offset1, LLScriptLibData *data, S32 heapsi
 	return lsa_heap_add_data(buffer, list1, heapsize, TRUE);
 }
 
+
+LLScriptLibData* lsa_randomize(LLScriptLibData* src, S32 stride)
+{
+	S32 number = src->getListLength();
+	if (number <= 0)
+	{
+		return NULL;
+	}
+	if (stride <= 0)
+	{
+		stride = 1;
+	}
+	if(number % stride)
+	{
+		LLScriptLibData* retval = src->mListp;
+		src->mListp = NULL;
+		return retval;
+	}
+	S32 buckets = number / stride;
+
+	// Copy everything into a special vector for sorting;
+	std::vector<LLScriptLibData*> sort_array;
+	sort_array.reserve(number);
+	LLScriptLibData* temp = src->mListp;
+	while(temp)
+	{
+		sort_array.push_back(temp);
+		temp = temp->mListp;
+	}
+
+	// We cannot simply call random_shuffle or similar algorithm since
+	// we need to obey the stride. So, we iterate over what we have
+	// and swap each with a random other segment.
+	S32 index = 0;
+	S32 ii = 0;
+	for(; ii < number; ii += stride)
+	{
+		index = ll_rand(buckets) * stride;
+		for(S32 jj = 0; jj < stride; ++jj)
+		{
+			std::swap(sort_array[ii + jj], sort_array[index + jj]);
+		}
+	}
+
+	// copy the pointers back out
+	ii = 1;
+	temp = sort_array[0];
+	while (ii < number)
+	{
+		temp->mListp = sort_array[ii++];
+		temp = temp->mListp;
+	}
+	temp->mListp = NULL;
+
+	src->mListp = NULL;
+
+	LLScriptLibData* ret_value = sort_array[0];
+	return ret_value;
+}