ALT Linux Team development discussions
 help / color / mirror / Atom feed
From: "Kirill A. Shutsemov" <kirill@shutemov.name>
To: "Dmitry V. Levin" <ldv@altlinux.org>, Alexey Tourbin <at@altlinux.ru>
Cc: "Alexey I. Froloff" <raorn@altlinux.org>,
	devel@lists.altlinux.org, Alexey Gladkov <legion@altlinux.ru>,
	"Kirill A. Shutemov" <kirill@shutemov.name>
Subject: [devel] [PATCH 2/8] set.c: get rid of nested functions
Date: Tue, 16 Nov 2010 17:56:36 +0200
Message-ID: <1289923002-14132-3-git-send-email-kirill@shutemov.name> (raw)
In-Reply-To: <1289923002-14132-1-git-send-email-kirill@shutemov.name>

From: Kirill A. Shutemov <kirill@shutemov.name>

Nested function in C is GCC extension.
Let's try to follow ANSI C syntax.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 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



  parent reply	other threads:[~2010-11-16 15:56 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 1/8] set.c, set.h: get rid of C++-style comments Kirill A. Shutsemov
2010-11-16 15:56 ` Kirill A. Shutsemov [this message]
2010-11-16 22:14   ` [devel] [PATCH 2/8] set.c: get rid of nested functions Dmitry V. Levin
2010-11-16 22:54     ` Kirill A. Shutemov
2010-11-16 23:07       ` Dmitry V. Levin
2010-11-16 23:10         ` Kirill A. Shutemov
2010-11-17 17:55           ` Dmitry V. Levin
2010-11-16 15:56 ` [devel] [PATCH 3/8] set.c: fixup self-test functions declaration Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 4/8] set.c: slightly reformat code to increase its readability Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 5/8] set.c: do not mix declarations and code Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 6/8] set.c: use function-like syntax for sizeof Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 7/8] set.c: cleanup self-tests Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 8/8] set.c: update copyright notice Kirill A. Shutsemov
2010-11-22  5:49   ` Alexey Tourbin
2010-11-23  0:48       ` Alexey Tourbin
2010-11-23  0:56         ` Dmitry V. Levin
2010-11-23  1:38           ` Alexey Tourbin
2010-11-23  6:42             ` Kirill A. Shutemov
2010-11-23 11:50               ` Alexey Tourbin
2010-11-25 22:02                 ` Kirill A. Shutemov
2010-11-26 18:03                 ` Michael Shigorin
2010-11-17  6:59 ` [devel] [PATCH 0/8] rpm: cleanup set.c and set.h REAL
2010-11-22  5:40 ` Alexey Tourbin
2010-11-22  7:14   ` Kirill A. Shutemov
2010-11-22  7:38     ` Alexey Tourbin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1289923002-14132-3-git-send-email-kirill@shutemov.name \
    --to=kirill@shutemov.name \
    --cc=at@altlinux.ru \
    --cc=devel@lists.altlinux.org \
    --cc=ldv@altlinux.org \
    --cc=legion@altlinux.ru \
    --cc=raorn@altlinux.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

ALT Linux Team development discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
		devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
	public-inbox-index devel

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://lore.altlinux.org/org.altlinux.lists.devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git