From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on sa.int.altlinux.org X-Spam-Level: X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DNS_FROM_OPENWHOIS autolearn=no version=3.2.5 From: "Kirill A. Shutsemov" To: "Dmitry V. Levin" , Alexey Tourbin Date: Tue, 16 Nov 2010 17:56:36 +0200 Message-Id: <1289923002-14132-3-git-send-email-kirill@shutemov.name> X-Mailer: git-send-email 1.7.2.3 In-Reply-To: <1289923002-14132-1-git-send-email-kirill@shutemov.name> References: <1289923002-14132-1-git-send-email-kirill@shutemov.name> Cc: "Alexey I. Froloff" , devel@lists.altlinux.org, Alexey Gladkov , "Kirill A. Shutemov" Subject: [devel] [PATCH 2/8] set.c: get rid of nested functions X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 16 Nov 2010 15:57:04 -0000 Archived-At: List-Archive: List-Post: From: Kirill A. Shutemov Nested function in C is GCC extension. Let's try to follow ANSI C syntax. Signed-off-by: Kirill A. Shutemov --- lib/set.c | 205 +++++++++++++++++++++++++++++++++--------------------------- 1 files changed, 113 insertions(+), 92 deletions(-) diff --git a/lib/set.c b/lib/set.c index e80ce61..1b516c7 100644 --- a/lib/set.c +++ b/lib/set.c @@ -39,21 +39,25 @@ int encode_base62_size(int bitc) return (bitc >> 2) + 2; } +static inline +char *put_digit(char *base62, int c) +{ + assert(c >= 0 && c <= 61); + if (c < 10) + *base62++ = c + '0'; + else if (c < 36) + *base62++ = c - 10 + 'a'; + else if (c < 62) + *base62++ = c - 36 + 'A'; + + return base62; +} + /* Main base62 encoding routine: pack bitv into base62 string. */ static int encode_base62(int bitc, const char *bitv, char *base62) { char *base62_start = base62; - void put_digit(int c) - { - assert(c >= 0 && c <= 61); - if (c < 10) - *base62++ = c + '0'; - else if (c < 36) - *base62++ = c - 10 + 'a'; - else if (c < 62) - *base62++ = c - 36 + 'A'; - } int bits2 = 0; /* number of high bits set */ int bits6 = 0; /* number of regular bits set */ int num6b = 0; /* pending 6-bit number */ @@ -64,21 +68,21 @@ int encode_base62(int bitc, const char *bitv, char *base62) switch (num6b) { case 61: /* escape */ - put_digit(61); + base62 = put_digit(base62, 61); /* extra "00...." high bits (in the next character) */ bits2 = 2; bits6 = 0; num6b = 0; break; case 62: - put_digit(61); + base62 = put_digit(base62, 61); /* extra "01...." hight bits */ bits2 = 2; bits6 = 0; num6b = 16; break; case 63: - put_digit(61); + base62 = put_digit(base62, 61); /* extra "10...." hight bits */ bits2 = 2; bits6 = 0; @@ -86,7 +90,7 @@ int encode_base62(int bitc, const char *bitv, char *base62) break; default: assert(num6b < 61); - put_digit(num6b); + base62 = put_digit(base62, num6b); bits2 = 0; bits6 = 0; num6b = 0; @@ -96,7 +100,7 @@ int encode_base62(int bitc, const char *bitv, char *base62) } if (bits6 + bits2) { assert(num6b < 61); - put_digit(num6b); + base62 = put_digit(base62, num6b); } *base62 = '\0'; return base62 - base62_start; @@ -111,37 +115,47 @@ int decode_base62_size(const char *base62) return (len << 2) + (len << 1); } +static inline +int char_to_num(int c) +{ + if (c >= '0' && c <= '9') + return c - '0'; + if (c >= 'a' && c <= 'z') + return c - 'a' + 10; + if (c >= 'A' && c <= 'Z') + return c - 'A' + 36; + return -1; +} + +static inline +char *put6bits(char *bitv, int c) +{ + *bitv++ = (c >> 0) & 1; + *bitv++ = (c >> 1) & 1; + *bitv++ = (c >> 2) & 1; + *bitv++ = (c >> 3) & 1; + *bitv++ = (c >> 4) & 1; + *bitv++ = (c >> 5) & 1; + + return bitv; +} + +static inline +char *put4bits(char *bitv, int c) +{ + *bitv++ = (c >> 0) & 1; + *bitv++ = (c >> 1) & 1; + *bitv++ = (c >> 2) & 1; + *bitv++ = (c >> 3) & 1; + + return bitv; +} + /* Main base62 decoding routine: unpack base62 string into bitv. */ static int decode_base62(const char *base62, char *bitv) { char *bitv_start = bitv; - int char_to_num(int c) - { - if (c >= '0' && c <= '9') - return c - '0'; - if (c >= 'a' && c <= 'z') - return c - 'a' + 10; - if (c >= 'A' && c <= 'Z') - return c - 'A' + 36; - return -1; - } - void put6bits(int c) - { - *bitv++ = (c >> 0) & 1; - *bitv++ = (c >> 1) & 1; - *bitv++ = (c >> 2) & 1; - *bitv++ = (c >> 3) & 1; - *bitv++ = (c >> 4) & 1; - *bitv++ = (c >> 5) & 1; - } - void put4bits(int c) - { - *bitv++ = (c >> 0) & 1; - *bitv++ = (c >> 1) & 1; - *bitv++ = (c >> 2) & 1; - *bitv++ = (c >> 3) & 1; - } int c; while ((c = *base62++)) { int num6b = char_to_num(c); @@ -156,22 +170,22 @@ int decode_base62(const char *base62, char *bitv) return -3; switch (num6b & (16 + 32)) { case 0: - put6bits(61); + bitv = put6bits(bitv, 61); break; case 16: - put6bits(62); + bitv = put6bits(bitv, 62); break; case 32: - put6bits(63); + bitv = put6bits(bitv, 63); break; default: return -4; break; } - put4bits(num6b); + bitv = put4bits(bitv, num6b); } else { - put6bits(num6b); + bitv = put6bits(bitv, num6b); } } return bitv - bitv_start; @@ -235,17 +249,19 @@ void test_base62() * http://algo2.iti.uni-karlsruhe.de/singler/publications/cacheefficientbloomfilters-wea2007.pdf */ +static inline +int log2i(int n) +{ + int m = 0; + while (n >>= 1) + m++; + return m; +} + /* Calculate Mshift paramter for encoding. */ static int encode_golomb_Mshift(int c, int bpp) { - int log2i(int n) - { - int m = 0; - while (n >>= 1) - m++; - return m; - } /* * XXX Slightly better Mshift estimations are probably possible. * Recheck "Compression and coding algorithms" by Moffat & Turpin. @@ -446,19 +462,21 @@ void maskv(int c, unsigned *v, unsigned mask) } static +int cmpv(const void *arg1, const void *arg2) +{ + unsigned v1 = *(unsigned *) arg1; + unsigned v2 = *(unsigned *) arg2; + if (v1 > v2) + return 1; + if (v1 < v2) + return -1; + return 0; +} + +static void sortv(int c, unsigned *v) { - int cmp(const void *arg1, const void *arg2) - { - unsigned v1 = *(unsigned *) arg1; - unsigned v2 = *(unsigned *) arg2; - if (v1 > v2) - return 1; - if (v1 < v2) - return -1; - return 0; - } - qsort(v, c, sizeof *v, cmp); + qsort(v, c, sizeof *v, cmpv); } static @@ -756,6 +774,35 @@ struct set *set_free(struct set *set) return NULL; } +/* Jenkins' one-at-a-time hash */ +static inline +unsigned int jenkins_hash(const char *str) +{ + unsigned int hash = 0x9e3779b9; + const unsigned char *p = (const unsigned char *) str; + while (*p) { + hash += *p++; + hash += (hash << 10); + hash ^= (hash >> 6); + } + hash += (hash << 3); + hash ^= (hash >> 11); + hash += (hash << 15); + return hash; +} + +static inline +int cmp_sv(const void *arg1, const void *arg2) +{ + struct sv *sv1 = (struct sv *) arg1; + struct sv *sv2 = (struct sv *) arg2; + if (sv1->v > sv2->v) + return 1; + if (sv2->v > sv1->v) + return -1; + return 0; +} + /* This routine does the whole job. */ const char *set_fini(struct set *set, int bpp) { @@ -766,38 +813,12 @@ const char *set_fini(struct set *set, int bpp) if (bpp > 32) return NULL; unsigned mask = (bpp < 32) ? (1u << bpp) - 1 : ~0u; - /* Jenkins' one-at-a-time hash */ - inline - unsigned int hash(const char *str) - { - unsigned int hash = 0x9e3779b9; - const unsigned char *p = (const unsigned char *) str; - while (*p) { - hash += *p++; - hash += (hash << 10); - hash ^= (hash >> 6); - } - hash += (hash << 3); - hash ^= (hash >> 11); - hash += (hash << 15); - return hash; - } /* hash sv strings */ int i; for (i = 0; i < set->c; i++) - set->sv[i].v = hash(set->sv[i].s) & mask; + set->sv[i].v = jenkins_hash(set->sv[i].s) & mask; /* sort by hash value */ - int cmp(const void *arg1, const void *arg2) - { - struct sv *sv1 = (struct sv *) arg1; - struct sv *sv2 = (struct sv *) arg2; - if (sv1->v > sv2->v) - return 1; - if (sv2->v > sv1->v) - return -1; - return 0; - } - qsort(set->sv, set->c, sizeof *set->sv, cmp); + qsort(set->sv, set->c, sizeof *set->sv, cmp_sv); /* warn on hash collisions */ for (i = 0; i < set->c - 1; i++) { if (set->sv[i].v != set->sv[i+1].v) -- 1.7.3.2