Permalink
Browse files

First pass at an alphabet array.

Rather than comparing the parameters simply stuff them into
an existing array based upon the first letter of the parameter.

This will be faster than other solutions *If* the first letter of
parameters are overwhelmingly of different letters.

When a duplicate is encountered this falls back to the pre-existing
solution.
  • Loading branch information...
1 parent 7fa9e31 commit 9dd2aea8f2fe50eec155c133887a6a17b08cf6e1 @icefox committed Sep 5, 2012
Showing with 96 additions and 8 deletions.
  1. +96 −7 skwurly.c
  2. +0 −1 skwurly.h
View
@@ -16,14 +16,102 @@ static inline int str_compare(const char* a, const char* b) {
return *a - *b;
}
-char* url_sort(const char* url) {
+char* url_sort_slow(const char* url);
+
+// building an array with twice the number of params
+// and working from middle of array
+// to remove shuffling requirement on prepending
+const char* params[MAX_PARAMS*2];
+unsigned short param_length[MAX_PARAMS*2];
+
+struct param {
+ const char* start;
+ unsigned short length;
+};
+param abparams[26];
+bool init = false;
+int low = 0;
+int high = 25;
- // building an array with twice the number of params
- // and working from middle of array
- // to remove shuffling requirement on prepending
- const char* params[MAX_PARAMS*2];
- unsigned short param_length[MAX_PARAMS*2];
+char* url_sort(const char* url) {
+ const char* orig_url = url;
+
+ // scan to first '?'
+ const char* start = strchr(url, '?');
+ url = start;
+ if (url == NULL || *(url+1) == '\0') {
+ return (char *) orig_url;
+ }
+
+ int i;
+ if (!init) {
+ for (i = low; i <= high; ++i)
+ abparams[i].start = 0;
+ init = true;
+ }
+
+ char *last_param = (char*)url;
+ int last = ((int)*(last_param+1)) - 97;
+ low = last;
+ high = last;
+ abparams[last].start = last_param;
+
+ bool sorted = true;
+ // and find the others
+ //printf("serach: %s\n", orig_url);
+ //printf("found: %d\n", last);
+ for (; *url; ++url) {
+ if (*url == '&') {
+ // grab a pointer to the param and the first char for easy action
+ const char* p = url+1;
+ int cur = *p - 97;
+ if (abparams[cur].start != 0) {
+ init = false;
+ return url_sort_slow(orig_url);
+ }
+ if (cur < low) low = cur;
+ if (cur > high) high = cur;
+ //printf("found: %d\n", cur);
+ abparams[cur].start = p;
+ abparams[last].length = url - last_param - 1;
+
+ last_param = (char*)url;
+ int currentChar = *(url+1) - 97;
+ if (currentChar < last)
+ sorted = false;
+ last = currentChar;
+ }
+ }
+
+ // sorted will be 1 if theres only one param or if the url is already sorted
+ if (sorted) {
+ init = false;
+ return (char*) orig_url;
+ }
+
+ abparams[last].length = url - last_param - 2;
+
+ // initialize our return value
+ char* sorted_url = (char*) malloc(url - orig_url+1);
+
+ // copy in chars up to and including '?'
+ char* cursor = mempcpy(sorted_url, orig_url, (start+1) - orig_url);
+
+ //printf("%d %d %s\n", low, high, orig_url);
+ for (int i = low; i <= high; ++i) {
+ if (abparams[i].start != 0) {
+ //printf("%d %d\n", i, abparams[i].length);
+ cursor = mempcpy(cursor, abparams[i].start, abparams[i].length);
+ abparams[i].start = 0;
+ *cursor++ = '&';
+ }
+ }
+ *cursor = '\0';
+
+ return sorted_url;
+}
+char* url_sort_slow(const char* url) {
const char* orig_url = url;
// scan to first '?'
@@ -65,7 +153,7 @@ char* url_sort(const char* url) {
const char* p = url+1;
// if it sorts to before head just insert it and move head to it
- if (str_compare(params[head], p) > -1) {
+ if (str_compare(params[head], p) >= -1) {
sorted = 0;
params[--head] = p;
last_param = head;
@@ -128,3 +216,4 @@ char* url_sort(const char* url) {
return sorted_url;
}
+
View
@@ -1,6 +1,5 @@
#ifndef __SKWURLY_H_
#define __SKWURLY_H_
-#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

0 comments on commit 9dd2aea

Please sign in to comment.