##// END OF EJS Templates
bdiff: improve worst case behavior by 100x....
Vadim Gelfer -
r2577:fa76c5d6 default
parent child Browse files
Show More
@@ -65,7 +65,7 b' static inline uint32_t rol32(uint32_t wo'
65
65
66 int splitlines(const char *a, int len, struct line **lr)
66 int splitlines(const char *a, int len, struct line **lr)
67 {
67 {
68 int h, i;
68 int g, h, i;
69 const char *p, *b = a;
69 const char *p, *b = a;
70 struct line *l;
70 struct line *l;
71
71
@@ -82,7 +82,16 b' int splitlines(const char *a, int len, s'
82 /* build the line array and calculate hashes */
82 /* build the line array and calculate hashes */
83 h = 0;
83 h = 0;
84 for (p = a; p < a + len; p++) {
84 for (p = a; p < a + len; p++) {
85 h = *p + rol32(h, 7); /* a simple hash from GNU diff */
85 /*
86 * a simple hash from GNU diff, with better collision
87 * resistance from hashpjw. this slows down common
88 * case by 10%, but speeds up worst case by 100x.
89 */
90 h = *p + rol32(h, 7);
91 if ((g = h & 0xf0000000)) {
92 h ^= g >> 24;
93 h ^= g;
94 }
86 if (*p == '\n' || p == a + len - 1) {
95 if (*p == '\n' || p == a + len - 1) {
87 l->len = p - b + 1;
96 l->len = p - b + 1;
88 l->h = h * l->len;
97 l->h = h * l->len;
General Comments 0
You need to be logged in to leave comments. Login now