ngx_sort

2 files changed, 29 insertions, 0 deletions

diff --git a/src/core/ngx_string.c b/src/core/ngx_string.c
index fe8cfacdd..7b5287f0a 100644
--- a/src/core/ngx_string.c
+++ b/src/core/ngx_string.c
@@ -1202,6 +1202,33 @@ done:
 }
 
 
+/* ngx_sort() is implemented as insertion sort because we need stable sort */
+
+void
+ngx_sort(void *base, size_t n, size_t size,
+    int (*cmp)(const void *, const void *))
+{
+    u_char  *p1, *p2;
+    u_char   buf[256];
+
+    for (p1 = (u_char *) base + size;
+         p1 < (u_char *) base + n * size;
+         p1 += size)
+    {
+        ngx_memcpy(buf, p1, size);
+
+        for (p2 = p1;
+             p2 > (u_char *) base && cmp(p2 - size, buf) > 0;
+             p2 -= size)
+        {
+            ngx_memcpy(p2, p2 - size, size);
+        }
+
+        ngx_memcpy(p2, buf, size);
+    }
+}
+
+
 #if (NGX_MEMCPY_LIMIT)
 
 void *
diff --git a/src/core/ngx_string.h b/src/core/ngx_string.h
index 00d0ae93a..18306d2d2 100644
--- a/src/core/ngx_string.h
+++ b/src/core/ngx_string.h
@@ -150,6 +150,8 @@ uintptr_t ngx_escape_uri(u_char *dst, u_char *src, size_t size,
 void ngx_unescape_uri(u_char **dst, u_char **src, size_t size, ngx_uint_t type);
 
 
+void ngx_sort(void *base, size_t n, size_t size,
+    int (*cmp)(const void *, const void *));
 #define ngx_qsort            qsort