diff options
Diffstat (limited to 'include/import/ebtree.h')
| -rw-r--r-- | include/import/ebtree.h | 136 |
1 files changed, 92 insertions, 44 deletions
diff --git a/include/import/ebtree.h b/include/import/ebtree.h index d6e51d5..31a9cac 100644 --- a/include/import/ebtree.h +++ b/include/import/ebtree.h @@ -250,39 +250,84 @@ #include <import/ebtree-t.h> #include <haproxy/api.h> -static inline int flsnz8_generic(unsigned int x) +/* returns clz from 7 to 0 for 0x01 to 0xFF. Returns 7 for 0 as well. */ +static inline unsigned int clz8(unsigned char c) { - int ret = 0; - if (x >> 4) { x >>= 4; ret += 4; } - return ret + ((0xFFFFAA50U >> (x << 1)) & 3) + 1; + unsigned int r = 4; + + if (c & 0xf0) { + r = 0; + c >>= 4; + } + return r + ((0x000055afU >> (c * 2)) & 0x3); } -/* Note: we never need to run fls on null keys, so we can optimize the fls - * function by removing a conditional jump. +/* FLSNZ: find last set bit for non-zero value. "Last" here means the highest + * one. It returns a value from 1 to 32 for 1<<0 to 1<<31. */ -#if defined(__i386__) || defined(__x86_64__) -/* this code is similar on 32 and 64 bit */ -static inline int flsnz(int x) + +#if (defined(__i386__) || defined(__x86_64__)) && !defined(__atom__) +/* DO NOT USE ON ATOM! The instruction is emulated and is several times slower + * than doing the math by hand. + */ +static inline unsigned int flsnz32(unsigned int x) { - int r; + unsigned int r; __asm__("bsrl %1,%0\n" : "=r" (r) : "rm" (x)); - return r+1; + return r + 1; +} +#define flsnz32(x) flsnz32(x) + +# if defined(__x86_64__) +static inline unsigned int flsnz64(unsigned long long x) +{ + unsigned long long r; + __asm__("bsrq %1,%0\n" + : "=r" (r) : "rm" (x)); + return r + 1; +} +# define flsnz64(x) flsnz64(x) +# endif + +#elif !defined(__atom__) && defined(__GNUC__) && ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 2))) +/* gcc >= 4.2 brings __builtin_clz() and __builtin_clzl(), usable for non-x86 */ + +static inline unsigned int flsnz32(unsigned int x) +{ + return 32 - __builtin_clz(x); +} +# define flsnz32(x) flsnz32(x) + +# if defined(__SIZEOF_LONG__) && (__SIZEOF_LONG__ > 4) +static inline unsigned int flsnz64(unsigned long x) +{ + return (__SIZEOF_LONG__ * 8) - __builtin_clzl(x); } +# define flsnz64(x) flsnz64(x) +# endif -static inline int flsnz8(unsigned char x) +#endif /* end of arch-specific implementations */ + +/*** Fallback versions below ***/ + +#ifndef flsnz8 +# if defined(flsnz32) +# define flsnz8(x) flsnz32((unsigned char)x) +# else +static inline unsigned int flsnz8(unsigned int x) { - int r; - __asm__("movzbl %%al, %%eax\n" - "bsrl %%eax,%0\n" - : "=r" (r) : "a" (x)); - return r+1; + unsigned int ret = 0; + if (x >> 4) { x >>= 4; ret += 4; } + return ret + ((0xFFFFAA50U >> (x << 1)) & 3) + 1; } +# define flsnz8(x) flsnz8(x) +# endif +#endif -#else -// returns 1 to 32 for 1<<0 to 1<<31. Undefined for 0. -#define flsnz(___a) ({ \ - register int ___x, ___bits = 0; \ +#ifndef flsnz32 +# define flsnz32(___a) ({ \ + register unsigned int ___x, ___bits = 0; \ ___x = (___a); \ if (___x & 0xffff0000) { ___x &= 0xffff0000; ___bits += 16;} \ if (___x & 0xff00ff00) { ___x &= 0xff00ff00; ___bits += 8;} \ @@ -291,16 +336,10 @@ static inline int flsnz8(unsigned char x) if (___x & 0xaaaaaaaa) { ___x &= 0xaaaaaaaa; ___bits += 1;} \ ___bits + 1; \ }) - -static inline int flsnz8(unsigned int x) -{ - return flsnz8_generic(x); -} - - #endif -static inline int fls64(unsigned long long x) +#ifndef flsnz64 +static inline unsigned int flsnz64(unsigned long long x) { unsigned int h; unsigned int bits = 32; @@ -310,10 +349,21 @@ static inline int fls64(unsigned long long x) h = x; bits = 0; } - return flsnz(h) + bits; + return flsnz32(h) + bits; } +# define flsnz64(x) flsnz64(x) +#endif + +#ifndef flsnz_long +# define flsnz_long(x) ((sizeof(long) > 4) ? flsnz64(x) : flsnz32(x)) +#endif -#define fls_auto(x) ((sizeof(x) > 4) ? fls64(x) : flsnz(x)) +#ifndef flsnz +# define flsnz(x) ((sizeof(x) > 4) ? flsnz64(x) : (sizeof(x) > 1) ? flsnz32(x) : flsnz8(x)) +#endif + +#define fls64(x) flsnz64(x) +#define fls_auto(x) ((x) ? flsnz(x) : 0) /* Linux-like "container_of". It returns a pointer to the structure of type * <type> which has its member <name> stored at address <ptr>. @@ -720,9 +770,9 @@ static forceinline void __eb_delete(struct eb_node *node) * bytes. Note that parts or all of <ignore> bits may be rechecked. It is only * passed here as a hint to speed up the check. */ -static forceinline int equal_bits(const unsigned char *a, - const unsigned char *b, - int ignore, int len) +static forceinline size_t equal_bits(const unsigned char *a, + const unsigned char *b, + size_t ignore, size_t len) { for (ignore >>= 3, a += ignore, b += ignore, ignore <<= 3; ignore < len; ) { @@ -738,7 +788,7 @@ static forceinline int equal_bits(const unsigned char *a, * it as the number of identical bits. Note that low bit numbers are * assigned to high positions in the byte, as we compare them as strings. */ - ignore -= flsnz8(c); + ignore -= flsnz_long(c); break; } } @@ -786,12 +836,12 @@ static forceinline int check_bits(const unsigned char *a, * permitted. Equal strings are reported as a negative number of bits, which * indicates the end was reached. */ -static forceinline int string_equal_bits(const unsigned char *a, - const unsigned char *b, - int ignore) +static forceinline size_t string_equal_bits(const unsigned char *a, + const unsigned char *b, + size_t ignore) { - int beg; - unsigned char c; + unsigned char c, d; + size_t beg; beg = ignore >> 3; @@ -799,8 +849,6 @@ static forceinline int string_equal_bits(const unsigned char *a, * or at the first zero we encounter on either side. */ while (1) { - unsigned char d; - c = a[beg]; d = b[beg]; beg++; @@ -809,14 +857,14 @@ static forceinline int string_equal_bits(const unsigned char *a, if (c) break; if (!d) - return -1; + return (size_t)-1; } /* OK now we know that a and b differ at byte <beg>, or that both are zero. * We have to find what bit is differing and report it as the number of * identical bits. Note that low bit numbers are assigned to high positions * in the byte, as we compare them as strings. */ - return (beg << 3) - flsnz8(c); + return (beg << 3) - flsnz(c); } static forceinline int cmp_bits(const unsigned char *a, const unsigned char *b, unsigned int pos) |