[devel] [PATCH 0/8] rpm: cleanup set.c and set.h

[devel] [PATCH 0/8] rpm: cleanup set.c and set.h

[Kirill A. Shutsemov]

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

Let's try to make set-versions implementation more maintainable.

Kirill A. Shutemov (8):
  set.c, set.h: get rid of C++-style comments
  set.c: get rid of nested functions
  set.c: fixup self-test functions declaration
  set.c: slightly reformat code to increase its readability
  set.c: do not mix declarations and code
  set.c: use function-like syntax for sizeof.
  set.c: cleanup self-tests
  set.c: update copyright notice

 lib/set.c |  768 +++++++++++++++++++++++++++++++++++++------------------------
 lib/set.h |   12 +-
 2 files changed, 473 insertions(+), 307 deletions(-)

-- 
1.7.3.2

[devel] [PATCH 1/8] set.c, set.h: get rid of C++-style comments

[Kirill A. Shutsemov]

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

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 lib/set.c |  164 ++++++++++++++++++++++++++++++++-----------------------------
 lib/set.h |   12 +++--
 2 files changed, 93 insertions(+), 83 deletions(-)

diff --git a/lib/set.c b/lib/set.c
index a45e02b..e80ce61 100644
--- a/lib/set.c
+++ b/lib/set.c
@@ -28,16 +28,18 @@
  * how multiple escapes can be effectively avoided.
  */
 
-// Estimate base62 buffer size required to encode a given number of bits.
+/* Estimate base62 buffer size required to encode a given number of bits. */
 static inline
 int encode_base62_size(int bitc)
 {
-    // Four bits can make a character; the remaining bits can make
-    // a character, too.  And the string should be null-terminated.
+    /*
+     * Four bits can make a character; the remaining bits can make
+     * a character, too.  And the string should be null-terminated.
+     */
     return (bitc >> 2) + 2;
 }
 
-// Main base62 encoding routine: pack bitv into base62 string.
+/* Main base62 encoding routine: pack bitv into base62 string. */
 static
 int encode_base62(int bitc, const char *bitv, char *base62)
 {
@@ -52,32 +54,32 @@ int encode_base62(int bitc, const char *bitv, char *base62)
 	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
+    int bits2 = 0; /* number of high bits set */
+    int bits6 = 0; /* number of regular bits set */
+    int num6b = 0; /* pending 6-bit number */
     while (bitc-- > 0) {
 	assert(bits6 + bits2 < 6);
 	num6b |= (*bitv++ << bits6++);
 	if (bits6 + bits2 == 6) {
 	    switch (num6b) {
 	    case 61:
-		// escape
+		/* escape */
 		put_digit(61);
-		// extra "00...." high bits (in the next character)
+		/* extra "00...." high bits (in the next character) */
 		bits2 = 2;
 		bits6 = 0;
 		num6b = 0;
 		break;
 	    case 62:
 		put_digit(61);
-		// extra "01...." hight bits
+		/* extra "01...." hight bits */
 		bits2 = 2;
 		bits6 = 0;
 		num6b = 16;
 		break;
 	    case 63:
 		put_digit(61);
-		// extra "10...." hight bits
+		/* extra "10...." hight bits */
 		bits2 = 2;
 		bits6 = 0;
 		num6b = 32;
@@ -100,16 +102,16 @@ int encode_base62(int bitc, const char *bitv, char *base62)
     return base62 - base62_start;
 }
 
-// Estimate how many bits will result from decoding a base62 string.
+/* Estimate how many bits will result from decoding a base62 string. */
 static inline
 int decode_base62_size(const char *base62)
 {
     int len = strlen(base62);
-    // Each character will fill at most 6 bits.
+    /* Each character will fill at most 6 bits. */
     return (len << 2) + (len << 1);
 }
 
-// Main base62 decoding routine: unpack base62 string into bitv.
+/* Main base62 decoding routine: unpack base62 string into bitv. */
 static
 int decode_base62(const char *base62, char *bitv)
 {
@@ -183,30 +185,30 @@ void test_base62()
 	1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1,
 	0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0,
 	0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0,
-	// trigger some 'Z'
+	/* trigger some 'Z' */
 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     };
     const int rnd_bitc = sizeof rnd_bitv;
-    // encode
+    /* encode */
     char base62[encode_base62_size(rnd_bitc)];
     int len = encode_base62(rnd_bitc, rnd_bitv, base62);
     assert(len > 0);
     assert(len == (int)strlen(base62));
     fprintf(stderr, "len=%d base62=%s\n", len, base62);
-    // The length cannot be shorter than 6 bits per symbol.
+    /* The length cannot be shorter than 6 bits per symbol. */
     assert(len >= rnd_bitc / 6);
-    // Neither too long: each second character must fill at least 4 bits.
+    /* Neither too long: each second character must fill at least 4 bits. */
     assert(len <= rnd_bitc / 2 / 4 + rnd_bitc / 2 / 6 + 1);
-    // decode
+    /* decode */
     char bitv[decode_base62_size(base62)];
     int bitc = decode_base62(base62, bitv);
     fprintf(stderr, "rnd_bitc=%d bitc=%d\n", rnd_bitc, bitc);
     assert(bitc >= rnd_bitc);
-    // Decoded bits must match.
+    /* Decoded bits must match. */
     int i;
     for (i = 0; i < rnd_bitc; i++)
 	assert(rnd_bitv[i] == bitv[i]);
-    // The remaining bits must be zero bits.
+    /* The remaining bits must be zero bits. */
     for (i = rnd_bitc; i < bitc; i++)
 	assert(bitv[i] == 0);
     fprintf(stderr, "%s: base62 test OK\n", __FILE__);
@@ -233,7 +235,7 @@ void test_base62()
  * http://algo2.iti.uni-karlsruhe.de/singler/publications/cacheefficientbloomfilters-wea2007.pdf
  */
 
-// Calculate Mshift paramter for encoding.
+/* Calculate Mshift paramter for encoding. */
 static
 int encode_golomb_Mshift(int c, int bpp)
 {
@@ -244,10 +246,12 @@ int encode_golomb_Mshift(int c, int bpp)
 	    m++;
 	return m;
     }
-    // XXX Slightly better Mshift estimations are probably possible.
-    // Recheck "Compression and coding algorithms" by Moffat & Turpin.
+    /*
+     * XXX Slightly better Mshift estimations are probably possible.
+     * Recheck "Compression and coding algorithms" by Moffat & Turpin.
+     */
     int Mshift = bpp - log2i(c) - 1;
-    // Adjust out-of-range values.
+    /* Adjust out-of-range values. */
     if (Mshift < 7)
 	Mshift = 7;
     if (Mshift > 31)
@@ -256,16 +260,18 @@ int encode_golomb_Mshift(int c, int bpp)
     return Mshift;
 }
 
-// Estimate how many bits can be filled up.
+/* Estimate how many bits can be filled up. */
 static inline
 int encode_golomb_size(int c, int Mshift)
 {
-    // XXX No precise estimation.  However, we do not expect unary-encoded bits
-    // to take more than binary-encoded Mshift bits.
+    /*
+     * XXX No precise estimation.  However, we do not expect unary-encoded bits
+     * to take more than binary-encoded Mshift bits.
+     */
     return (Mshift << 1) * c + 16;
 }
 
-// Main golomb encoding routine: package integers into bits.
+/* Main golomb encoding routine: package integers into bits. */
 static
 int encode_golomb(int c, const unsigned *v, int Mshift, char *bitv)
 {
@@ -275,12 +281,12 @@ int encode_golomb(int c, const unsigned *v, int Mshift, char *bitv)
 	c--;
 	unsigned v0 = *v++;
 	int i;
-	// first part: variable-length sequence
+	/* first part: variable-length sequence */
 	unsigned q = v0 >> Mshift;
 	for (i = 0; i < (int)q; i++)
 	    *bitv++ = 0;
 	*bitv++ = 1;
-	// second part: lower Mshift bits
+	/* second part: lower Mshift bits */
 	unsigned r = v0 & mask;
 	for (i = 0; i < Mshift; i++)
 	    *bitv++ = (r >> i) & 1;
@@ -288,23 +294,25 @@ int encode_golomb(int c, const unsigned *v, int Mshift, char *bitv)
     return bitv - bitv_start;
 }
 
-// Estimate how many values will emerge.
+/* Estimate how many values will emerge. */
 static inline
 int decode_golomb_size(int bitc, int Mshift)
 {
-    // Each (Mshift + 1) bits can make a value.
-    // The remaining bits cannot make a value, though.
+    /*
+     * Each (Mshift + 1) bits can make a value.
+     * The remaining bits cannot make a value, though.
+     */
     return bitc / (Mshift + 1);
 }
 
-// Main golomb decoding routine: unpackage bits into values.
+/* Main golomb decoding routine: unpackage bits into values. */
 static
 int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 {
     unsigned *v_start = v;
-    // next value
+    /* next value */
     while (bitc > 0) {
-	// first part
+	/* first part */
 	unsigned q = 0;
 	char bit = 0;
 	while (bitc > 0) {
@@ -315,13 +323,13 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 	    else
 		break;
 	}
-	// trailing zero bits in the input are okay
+	/* trailing zero bits in the input are okay */
 	if (bitc == 0 && bit == 0)
 	    break;
-	// otherwise, incomplete value is not okay
+	/* otherwise, incomplete value is not okay */
 	if (bitc < Mshift)
 	    return -1;
-	// second part
+	/* second part */
 	unsigned r = 0;
 	int i;
 	for (i = 0; i < Mshift; i++) {
@@ -329,7 +337,7 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 	    if (*bitv++)
 		r |= (1 << i);
 	}
-	// the value
+	/* the value */
 	*v++ = (q << Mshift) | r;
     }
     return v - v_start;
@@ -339,9 +347,9 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 void test_golomb()
 {
     const unsigned rnd_v[] = {
-	// do re mi fa sol la si
+	/* do re mi fa sol la si */
 	1, 2, 3, 4, 5, 6, 7,
-	// koshka sela na taksi
+	/* koshka sela na taksi */
 	7, 6, 5, 4, 3, 2, 1,
     };
     const int rnd_c = sizeof rnd_v / sizeof *rnd_v;
@@ -350,7 +358,7 @@ void test_golomb()
     fprintf(stderr, "rnd_c=%d bpp=%d Mshift=%d\n", rnd_c, bpp, Mshift);
     assert(Mshift > 0);
     assert(Mshift < bpp);
-    // encode
+    /* encode */
     int alloc_bitc = encode_golomb_size(rnd_c, Mshift);
     assert(alloc_bitc > rnd_c);
     char bitv[alloc_bitc];
@@ -358,19 +366,19 @@ void test_golomb()
     fprintf(stderr, "alloc_bitc=%d bitc=%d\n", alloc_bitc, bitc);
     assert(bitc > rnd_c);
     assert(bitc <= alloc_bitc);
-    // decode
+    /* decode */
     int alloc_c = decode_golomb_size(bitc, Mshift);
     assert(alloc_c >= rnd_c);
     unsigned v[alloc_c];
     int c = decode_golomb(bitc, bitv, Mshift, v);
     fprintf(stderr, "rnd_c=%d alloc_c=%d c=%d\n", rnd_c, alloc_c, c);
     assert(alloc_c >= c);
-    // Decoded values must match.
+    /* Decoded values must match. */
     assert(rnd_c == c);
     int i;
     for (i = 0; i < c; i++)
 	assert(rnd_v[i] == v[i]);
-    // At the end of the day, did it save your money?
+    /* At the end of the day, did it save your money? */
     int golomb_bpp = bitc / c;
     fprintf(stderr, "bpp=%d golomb_bpp=%d\n", bpp, golomb_bpp);
     assert(golomb_bpp < bpp);
@@ -506,35 +514,35 @@ int encode_set_size(int c, int bpp)
 {
     int Mshift = encode_golomb_Mshift(c, bpp);
     int bitc = encode_golomb_size(c, Mshift);
-    // two leading characters are special
+    /* two leading characters are special */
     return 2 + encode_base62_size(bitc);
 }
 
 static
 int encode_set(int c, unsigned *v, int bpp, char *base62)
 {
-    // XXX v is non-const due to encode_delta
+    /* XXX v is non-const due to encode_delta */
     int Mshift = encode_golomb_Mshift(c, bpp);
     int bitc = encode_golomb_size(c, Mshift);
     char bitv[bitc];
-    // bpp
+    /* bpp */
     if (bpp < 10 || bpp > 32)
 	return -1;
     *base62++ = bpp - 7 + 'a';
-    // golomb parameter
+    /* golomb parameter */
     if (Mshift < 7 || Mshift > 31)
 	return -2;
     *base62++ = Mshift - 7 + 'a';
-    // delta
+    /* delta */
     encode_delta(c, v);
-    // golomb
+    /* golomb */
     bitc = encode_golomb(c, v, Mshift, bitv);
 #ifdef SELF_TEST
     decode_delta(c, v);
 #endif
     if (bitc < 0)
 	return -3;
-    // base62
+    /* base62 */
     int len = encode_base62(bitc, bitv, base62);
     if (len < 0)
 	return -4;
@@ -544,17 +552,17 @@ int encode_set(int c, unsigned *v, int bpp, char *base62)
 static
 int decode_set_init(const char *str, int *pbpp, int *pMshift)
 {
-    // 7..32 values encoded with 'a'..'z'
+    /* 7..32 values encoded with 'a'..'z' */
     int bpp = *str++ + 7 - 'a';
     if (bpp < 10 || bpp > 32)
 	return -1;
-    // golomb parameter
+    /* golomb parameter */
     int Mshift = *str++ + 7 - 'a';
     if (Mshift < 7 || Mshift > 31)
 	return -2;
     if (Mshift >= bpp)
 	return -3;
-    // no empty sets for now
+    /* no empty sets for now */
     if (*str == '\0')
 	return -4;
     *pbpp = bpp;
@@ -574,16 +582,16 @@ static
 int decode_set(const char *str, int Mshift, unsigned *v)
 {
     str += 2;
-    // base62
+    /* base62 */
     char bitv[decode_base62_size(str)];
     int bitc = decode_base62(str, bitv);
     if (bitc < 0)
 	return -1;
-    // golomb
+    /* golomb */
     int c = decode_golomb(bitc, bitv, Mshift, v);
     if (c < 0)
 	return -2;
-    // delta
+    /* delta */
     decode_delta(c, v);
     return c;
 }
@@ -608,13 +616,13 @@ void test_set()
 	0xb584, 0xb89f, 0xbb40, 0xf39e,
     };
     int rnd_c = sizeof rnd_v / sizeof *rnd_v;
-    // encode
+    /* encode */
     int bpp = 16;
     char base62[encode_set_size(rnd_c, bpp)];
     int len = encode_set(rnd_c, rnd_v, bpp, base62);
     assert(len > 0);
     fprintf(stderr, "len=%d set=%s\n", len, base62);
-    // decode
+    /* decode */
     int Mshift = bpp;
     int rc = decode_set_init(base62, &bpp, &Mshift);
     assert(rc == 0);
@@ -624,7 +632,7 @@ void test_set()
     assert(c >= rnd_c);
     unsigned v[c];
     c = decode_set(base62, Mshift, v);
-    // Decoded values must match.
+    /* Decoded values must match. */
     assert(c == rnd_c);
     int i;
     for (i = 0; i < c; i++)
@@ -639,31 +647,31 @@ void test_set()
 
 #include "set.h"
 
-// main API routine
+/* main API routine */
 int rpmsetcmp(const char *str1, const char *str2)
 {
 	if (strncmp(str1, "set:", 4) == 0)
 	    str1 += 4;
 	if (strncmp(str2, "set:", 4) == 0)
 	    str2 += 4;
-	// initialize decoding
+	/* initialize decoding */
 	int bpp1, Mshift1;
 	int bpp2, Mshift2;
 	if (decode_set_init(str1, &bpp1, &Mshift1) < 0)
 	    return -3;
 	if (decode_set_init(str2, &bpp2, &Mshift2) < 0)
 	    return -4;
-	// make room for hash values
+	/* make room for hash values */
 	unsigned v1[decode_set_size(str1, Mshift1)];
 	unsigned v2[decode_set_size(str2, Mshift2)];
-	// decode hash values
+	/* decode hash values */
 	int c1 = decode_set(str1, Mshift1, v1);
 	if (c1 < 0)
 	    return -3;
 	int c2 = decode_set(str2, Mshift2, v2);
 	if (c2 < 0)
 	    return -4;
-	// adjust for comparison
+	/* adjust for comparison */
 	if (bpp1 > bpp2) {
 	    bpp1 = bpp2;
 	    c1 = downsample_set(c1, v1, bpp1);
@@ -672,7 +680,7 @@ int rpmsetcmp(const char *str1, const char *str2)
 	    bpp2 = bpp1;
 	    c2 = downsample_set(c2, v2, bpp2);
 	}
-	// compare
+	/* compare */
 	int ge = 1;
 	int le = 1;
 	int i1 = 0, i2 = 0;
@@ -689,7 +697,7 @@ int rpmsetcmp(const char *str1, const char *str2)
 		i1++;
 		i2++;
 	    }
-	// return
+	/* return */
 	if (i1 < c1)
 	    le = 0;
 	if (i2 < c2)
@@ -710,7 +718,7 @@ int rpmsetcmp(const char *str1, const char *str2)
 #include "system.h"
 #include "rpmlib.h"
 
-// Internally, "struct set" is just a bag of strings and their hash values.
+/* Internally, "struct set" is just a bag of strings and their hash values. */
 struct set {
     int c;
     struct sv {
@@ -748,7 +756,7 @@ struct set *set_free(struct set *set)
     return NULL;
 }
 
-// This routine does the whole job.
+/* This routine does the whole job. */
 const char *set_fini(struct set *set, int bpp)
 {
     if (set->c < 1)
@@ -758,7 +766,7 @@ 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
+    /* Jenkins' one-at-a-time hash */
     inline
     unsigned int hash(const char *str)
     {
@@ -774,11 +782,11 @@ const char *set_fini(struct set *set, int bpp)
 	hash += (hash << 15);
 	return hash;
     }
-    // hash sv strings
+    /* hash sv strings */
     int i;
     for (i = 0; i < set->c; i++)
 	set->sv[i].v = hash(set->sv[i].s) & mask;
-    // sort by hash value
+    /* sort by hash value */
     int cmp(const void *arg1, const void *arg2)
     {
 	struct sv *sv1 = (struct sv *) arg1;
@@ -790,7 +798,7 @@ const char *set_fini(struct set *set, int bpp)
 	return 0;
     }
     qsort(set->sv, set->c, sizeof *set->sv, cmp);
-    // warn on hash collisions
+    /* warn on hash collisions */
     for (i = 0; i < set->c - 1; i++) {
 	if (set->sv[i].v != set->sv[i+1].v)
 	    continue;
@@ -799,7 +807,7 @@ const char *set_fini(struct set *set, int bpp)
 	fprintf(stderr, "warning: hash collision: %s %s\n",
 		set->sv[i].s, set->sv[i+1].s);
     }
-    // encode
+    /* encode */
     unsigned v[set->c];
     for (i = 0; i < set->c; i++)
 	v[i] = set->sv[i].v;
@@ -871,4 +879,4 @@ int main()
     return 0;
 }
 #endif
-// ex: set ts=8 sts=4 sw=4 noet:
+/* ex: set ts=8 sts=4 sw=4 noet: */
diff --git a/lib/set.h b/lib/set.h
index 49b8ea6..6f32e88 100644
--- a/lib/set.h
+++ b/lib/set.h
@@ -1,7 +1,9 @@
 #ifndef SET_H
 #define SET_H
 
-/* Compare two set-versions.
+/*
+ * Compare two set-versions.
+ *
  * Return value:
  *  1: set1  >  set2
  *  0: set1 ==  set2
@@ -16,16 +18,16 @@ int rpmsetcmp(const char *set1, const char *set2);
  * API for creating set versions.
  */
 
-// initialize new set
+/* initialize new set */
 struct set *set_new(void);
 
-// add new symbol to set
+/* add new symbol to set */
 void set_add(struct set *set, const char *sym);
 
-// make set-version
+/* make set-version */
 const char *set_fini(struct set *set, int bpp);
 
-// free set
+/* free set */
 struct set *set_free(struct set *set);
 
 #endif
-- 
1.7.3.2

[devel] [PATCH 2/8] set.c: get rid of nested functions

[Kirill A. Shutsemov]

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

[devel] [PATCH 3/8] set.c: fixup self-test functions declaration

[Kirill A. Shutsemov]

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

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 lib/set.c |   17 ++++++++++-------
 1 files changed, 10 insertions(+), 7 deletions(-)

diff --git a/lib/set.c b/lib/set.c
index 1b516c7..03c8149 100644
--- a/lib/set.c
+++ b/lib/set.c
@@ -192,7 +192,8 @@ int decode_base62(const char *base62, char *bitv)
 }
 
 #ifdef SELF_TEST
-void test_base62()
+static
+void test_base62(void)
 {
     const char rnd_bitv[] = {
 	1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1,
@@ -360,7 +361,8 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 }
 
 #ifdef SELF_TEST
-void test_golomb()
+static
+void test_golomb(void)
 {
     const unsigned rnd_v[] = {
 	/* do re mi fa sol la si */
@@ -430,7 +432,8 @@ void decode_delta(int c, unsigned *v)
 }
 
 #ifdef SELF_TEST
-void test_delta()
+static
+void test_delta(void)
 {
     unsigned v[] = {
 	1, 3, 7, 0
@@ -494,7 +497,7 @@ int uniqv(int c, unsigned *v)
 
 #ifdef SELF_TEST
 static
-void test_aux()
+void test_aux(void)
 {
     unsigned v[] = { 2, 3, 1, 2, 7, 6, 5 };
     int c = sizeof v / sizeof *v;
@@ -625,7 +628,7 @@ int downsample_set(int c, unsigned *v, int bpp)
 
 #ifdef SELF_TEST
 static
-void test_set()
+void test_set(void)
 {
     unsigned rnd_v[] = {
 	0x020a, 0x07e5, 0x3305, 0x35f5,
@@ -842,7 +845,7 @@ const char *set_fini(struct set *set, int bpp)
 
 #ifdef SELF_TEST
 static
-void test_api()
+void test_api(void)
 {
     struct set *set1 = set_new();
     set_add(set1, "mama");
@@ -889,7 +892,7 @@ void test_api()
 #endif
 
 #ifdef SELF_TEST
-int main()
+int main(int argc, char **argv)
 {
     test_base62();
     test_golomb();
-- 
1.7.3.2

[devel] [PATCH 4/8] set.c: slightly reformat code to increase its readability

[Kirill A. Shutsemov]

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

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 lib/set.c |  212 +++++++++++++++++++++++++++++++++++++++++++------------------
 1 files changed, 149 insertions(+), 63 deletions(-)

diff --git a/lib/set.c b/lib/set.c
index 03c8149..9dd3eb4 100644
--- a/lib/set.c
+++ b/lib/set.c
@@ -61,48 +61,54 @@ int encode_base62(int bitc, const char *bitv, char *base62)
     int bits2 = 0; /* number of high bits set */
     int bits6 = 0; /* number of regular bits set */
     int num6b = 0; /* pending 6-bit number */
+
     while (bitc-- > 0) {
 	assert(bits6 + bits2 < 6);
 	num6b |= (*bitv++ << bits6++);
-	if (bits6 + bits2 == 6) {
-	    switch (num6b) {
-	    case 61:
-		/* escape */
-		base62 = put_digit(base62, 61);
-		/* extra "00...." high bits (in the next character) */
-		bits2 = 2;
-		bits6 = 0;
-		num6b = 0;
-		break;
-	    case 62:
-		base62 = put_digit(base62, 61);
-		/* extra "01...." hight bits */
-		bits2 = 2;
-		bits6 = 0;
-		num6b = 16;
-		break;
-	    case 63:
-		base62 = put_digit(base62, 61);
-		/* extra "10...." hight bits */
-		bits2 = 2;
-		bits6 = 0;
-		num6b = 32;
-		break;
-	    default:
-		assert(num6b < 61);
-		base62 = put_digit(base62, num6b);
-		bits2 = 0;
-		bits6 = 0;
-		num6b = 0;
-		break;
-	    }
+
+	if (bits6 + bits2 != 6)
+	    continue;
+
+	switch (num6b) {
+	case 61:
+	    /* escape */
+	    base62 = put_digit(base62, 61);
+	    /* extra "00...." high bits (in the next character) */
+	    bits2 = 2;
+	    bits6 = 0;
+	    num6b = 0;
+	    break;
+	case 62:
+	    base62 = put_digit(base62, 61);
+	    /* extra "01...." hight bits */
+	    bits2 = 2;
+	    bits6 = 0;
+	    num6b = 16;
+	    break;
+	case 63:
+	    base62 = put_digit(base62, 61);
+	    /* extra "10...." hight bits */
+	    bits2 = 2;
+	    bits6 = 0;
+	    num6b = 32;
+	    break;
+	default:
+	    assert(num6b < 61);
+	    base62 = put_digit(base62, num6b);
+	    bits2 = 0;
+	    bits6 = 0;
+	    num6b = 0;
+	    break;
 	}
     }
+
     if (bits6 + bits2) {
 	assert(num6b < 61);
 	base62 = put_digit(base62, num6b);
     }
+
     *base62 = '\0';
+
     return base62 - base62_start;
 }
 
@@ -111,6 +117,7 @@ static inline
 int decode_base62_size(const char *base62)
 {
     int len = strlen(base62);
+
     /* Each character will fill at most 6 bits. */
     return (len << 2) + (len << 1);
 }
@@ -124,6 +131,7 @@ int char_to_num(int c)
 	return c - 'a' + 10;
     if (c >= 'A' && c <= 'Z')
 	return c - 'A' + 36;
+
     return -1;
 }
 
@@ -157,37 +165,44 @@ int decode_base62(const char *base62, char *bitv)
 {
     char *bitv_start = bitv;
     int c;
+
     while ((c = *base62++)) {
 	int num6b = char_to_num(c);
+
 	if (num6b < 0)
 	    return -1;
-	if (num6b == 61) {
-	    c = *base62++;
-	    if (c == 0)
-		return -2;
-	    num6b = char_to_num(c);
-	    if (num6b < 0)
-		return -3;
-	    switch (num6b & (16 + 32)) {
-	    case 0:
-		bitv = put6bits(bitv, 61);
-		break;
-	    case 16:
-		bitv = put6bits(bitv, 62);
-		break;
-	    case 32:
-		bitv = put6bits(bitv, 63);
-		break;
-	    default:
-		return -4;
-		break;
-	    }
-	    bitv = put4bits(bitv, num6b);
-	}
-	else {
+
+	if (num6b != 61) {
 	    bitv = put6bits(bitv, num6b);
+	    continue;
+	}
+
+	c = *base62++;
+	if (c == 0)
+	    return -2;
+
+	num6b = char_to_num(c);
+	if (num6b < 0)
+	    return -3;
+
+	switch (num6b & (16 + 32)) {
+	case 0:
+	    bitv = put6bits(bitv, 61);
+	    break;
+	case 16:
+	    bitv = put6bits(bitv, 62);
+	    break;
+	case 32:
+	    bitv = put6bits(bitv, 63);
+	    break;
+	default:
+	    return -4;
+	    break;
 	}
+
+	bitv = put4bits(bitv, num6b);
     }
+
     return bitv - bitv_start;
 }
 
@@ -254,8 +269,10 @@ static inline
 int log2i(int n)
 {
     int m = 0;
+
     while (n >>= 1)
 	m++;
+
     return m;
 }
 
@@ -268,11 +285,14 @@ int encode_golomb_Mshift(int c, int bpp)
      * Recheck "Compression and coding algorithms" by Moffat & Turpin.
      */
     int Mshift = bpp - log2i(c) - 1;
+
     /* Adjust out-of-range values. */
     if (Mshift < 7)
 	Mshift = 7;
+
     if (Mshift > 31)
 	Mshift = 31;
+
     assert(Mshift < bpp);
     return Mshift;
 }
@@ -294,20 +314,25 @@ int encode_golomb(int c, const unsigned *v, int Mshift, char *bitv)
 {
     char *bitv_start = bitv;
     const unsigned mask = (1 << Mshift) - 1;
+
     while (c > 0) {
 	c--;
 	unsigned v0 = *v++;
 	int i;
 	/* first part: variable-length sequence */
 	unsigned q = v0 >> Mshift;
+
 	for (i = 0; i < (int)q; i++)
 	    *bitv++ = 0;
 	*bitv++ = 1;
+
 	/* second part: lower Mshift bits */
 	unsigned r = v0 & mask;
+
 	for (i = 0; i < Mshift; i++)
 	    *bitv++ = (r >> i) & 1;
     }
+
     return bitv - bitv_start;
 }
 
@@ -327,11 +352,13 @@ static
 int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 {
     unsigned *v_start = v;
+
     /* next value */
     while (bitc > 0) {
 	/* first part */
 	unsigned q = 0;
 	char bit = 0;
+
 	while (bitc > 0) {
 	    bitc--;
 	    bit = *bitv++;
@@ -340,15 +367,19 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 	    else
 		break;
 	}
+
 	/* trailing zero bits in the input are okay */
 	if (bitc == 0 && bit == 0)
 	    break;
+
 	/* otherwise, incomplete value is not okay */
 	if (bitc < Mshift)
 	    return -1;
+
 	/* second part */
 	unsigned r = 0;
 	int i;
+
 	for (i = 0; i < Mshift; i++) {
 	    bitc--;
 	    if (*bitv++)
@@ -357,6 +388,7 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 	/* the value */
 	*v++ = (q << Mshift) | r;
     }
+
     return v - v_start;
 }
 
@@ -412,8 +444,10 @@ void test_golomb(void)
 static
 void encode_delta(int c, unsigned *v)
 {
-    assert(c > 0);
     unsigned int v0 = *v++;
+
+    assert(c > 0);
+
     while (--c > 0) {
 	*v -= v0;
 	v0 += *v++;
@@ -423,8 +457,10 @@ void encode_delta(int c, unsigned *v)
 static
 void decode_delta(int c, unsigned *v)
 {
-    assert(c > 0);
     unsigned int v0 = *v++;
+
+    assert(c > 0);
+
     while (--c > 0) {
 	*v += v0;
 	v0 = *v++;
@@ -469,10 +505,12 @@ 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;
 }
 
@@ -486,11 +524,13 @@ static
 int uniqv(int c, unsigned *v)
 {
     int i, j;
+
     for (i = 0, j = 0; i < c; i++) {
 	while (i + 1 < c && v[i] == v[i+1])
 	    i++;
 	v[j++] = v[i];
     }
+
     assert(j <= c);
     return j;
 }
@@ -535,6 +575,7 @@ int encode_set_size(int c, int bpp)
 {
     int Mshift = encode_golomb_Mshift(c, bpp);
     int bitc = encode_golomb_size(c, Mshift);
+
     /* two leading characters are special */
     return 2 + encode_base62_size(bitc);
 }
@@ -546,27 +587,35 @@ int encode_set(int c, unsigned *v, int bpp, char *base62)
     int Mshift = encode_golomb_Mshift(c, bpp);
     int bitc = encode_golomb_size(c, Mshift);
     char bitv[bitc];
+
     /* bpp */
     if (bpp < 10 || bpp > 32)
 	return -1;
     *base62++ = bpp - 7 + 'a';
+
     /* golomb parameter */
     if (Mshift < 7 || Mshift > 31)
 	return -2;
     *base62++ = Mshift - 7 + 'a';
+
     /* delta */
     encode_delta(c, v);
+
     /* golomb */
     bitc = encode_golomb(c, v, Mshift, bitv);
+
 #ifdef SELF_TEST
     decode_delta(c, v);
 #endif
+
     if (bitc < 0)
 	return -3;
+
     /* base62 */
     int len = encode_base62(bitc, bitv, base62);
     if (len < 0)
 	return -4;
+
     return 2 + len;
 }
 
@@ -575,17 +624,23 @@ int decode_set_init(const char *str, int *pbpp, int *pMshift)
 {
     /* 7..32 values encoded with 'a'..'z' */
     int bpp = *str++ + 7 - 'a';
+
     if (bpp < 10 || bpp > 32)
 	return -1;
+
     /* golomb parameter */
     int Mshift = *str++ + 7 - 'a';
+
     if (Mshift < 7 || Mshift > 31)
 	return -2;
+
     if (Mshift >= bpp)
 	return -3;
+
     /* no empty sets for now */
     if (*str == '\0')
 	return -4;
+
     *pbpp = bpp;
     *pMshift = Mshift;
     return 0;
@@ -606,12 +661,15 @@ int decode_set(const char *str, int Mshift, unsigned *v)
     /* base62 */
     char bitv[decode_base62_size(str)];
     int bitc = decode_base62(str, bitv);
+
     if (bitc < 0)
 	return -1;
+
     /* golomb */
     int c = decode_golomb(bitc, bitv, Mshift, v);
     if (c < 0)
 	return -2;
+
     /* delta */
     decode_delta(c, v);
     return c;
@@ -621,8 +679,10 @@ static
 int downsample_set(int c, unsigned *v, int bpp)
 {
     unsigned mask = (1 << bpp) - 1;
+
     maskv(c, v, mask);
     sortv(c, v);
+
     return uniqv(c, v);
 }
 
@@ -675,23 +735,29 @@ int rpmsetcmp(const char *str1, const char *str2)
 	    str1 += 4;
 	if (strncmp(str2, "set:", 4) == 0)
 	    str2 += 4;
+
 	/* initialize decoding */
 	int bpp1, Mshift1;
 	int bpp2, Mshift2;
+
 	if (decode_set_init(str1, &bpp1, &Mshift1) < 0)
 	    return -3;
 	if (decode_set_init(str2, &bpp2, &Mshift2) < 0)
 	    return -4;
+
 	/* make room for hash values */
 	unsigned v1[decode_set_size(str1, Mshift1)];
 	unsigned v2[decode_set_size(str2, Mshift2)];
+
 	/* decode hash values */
 	int c1 = decode_set(str1, Mshift1, v1);
 	if (c1 < 0)
 	    return -3;
+
 	int c2 = decode_set(str2, Mshift2, v2);
 	if (c2 < 0)
 	    return -4;
+
 	/* adjust for comparison */
 	if (bpp1 > bpp2) {
 	    bpp1 = bpp2;
@@ -701,28 +767,30 @@ int rpmsetcmp(const char *str1, const char *str2)
 	    bpp2 = bpp1;
 	    c2 = downsample_set(c2, v2, bpp2);
 	}
+
 	/* compare */
 	int ge = 1;
 	int le = 1;
 	int i1 = 0, i2 = 0;
-	while (i1 < c1 && i2 < c2)
+	while (i1 < c1 && i2 < c2) {
 	    if (v1[i1] < v2[i2]) {
 		le = 0;
 		i1++;
-	    }
-	    else if (v1[i1] > v2[i2]) {
+	    } else if (v1[i1] > v2[i2]) {
 		ge = 0;
 		i2++;
-	    }
-	    else {
+	    } else {
 		i1++;
 		i2++;
 	    }
+	}
+
 	/* return */
 	if (i1 < c1)
 	    le = 0;
 	if (i2 < c2)
 	    ge = 0;
+
 	if (le && ge)
 	    return 0;
 	if (ge)
@@ -751,16 +819,20 @@ struct set {
 struct set *set_new()
 {
     struct set *set = xmalloc(sizeof *set);
+
     set->c = 0;
     set->sv = NULL;
+
     return set;
 }
 
 void set_add(struct set *set, const char *sym)
 {
     const int delta = 1024;
+
     if ((set->c & (delta - 1)) == 0)
 	set->sv = xrealloc(set->sv, sizeof(*set->sv) * (set->c + delta));
+
     set->sv[set->c].s = xstrdup(sym);
     set->sv[set->c].v = 0;
     set->c++;
@@ -770,8 +842,10 @@ struct set *set_free(struct set *set)
 {
     if (set) {
 	int i;
+
 	for (i = 0; i < set->c; i++)
 	    set->sv[i].s = _free(set->sv[i].s);
+
 	set->sv = _free(set->sv);
     }
     return NULL;
@@ -783,14 +857,17 @@ 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;
 }
 
@@ -799,10 +876,13 @@ 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;
 }
 
@@ -816,12 +896,15 @@ const char *set_fini(struct set *set, int bpp)
     if (bpp > 32)
 	return NULL;
     unsigned mask = (bpp < 32) ? (1u << bpp) - 1 : ~0u;
+
     /* hash sv strings */
     int i;
     for (i = 0; i < set->c; i++)
 	set->sv[i].v = jenkins_hash(set->sv[i].s) & mask;
+
     /* sort by hash value */
     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)
@@ -831,15 +914,18 @@ const char *set_fini(struct set *set, int bpp)
 	fprintf(stderr, "warning: hash collision: %s %s\n",
 		set->sv[i].s, set->sv[i+1].s);
     }
+
     /* encode */
     unsigned v[set->c];
     for (i = 0; i < set->c; i++)
 	v[i] = set->sv[i].v;
+
     int c = uniqv(set->c, v);
     char base62[encode_set_size(c, bpp)];
     int len = encode_set(c, v, bpp, base62);
     if (len < 0)
 	return NULL;
+
     return xstrdup(base62);
 }
 
-- 
1.7.3.2

[devel] [PATCH 5/8] set.c: do not mix declarations and code

[Kirill A. Shutsemov]

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

Let's move variable declarations to the begin of blocks.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 lib/set.c |  111 +++++++++++++++++++++++++++++++++++-------------------------
 1 files changed, 65 insertions(+), 46 deletions(-)

diff --git a/lib/set.c b/lib/set.c
index 9dd3eb4..2a8d8b3 100644
--- a/lib/set.c
+++ b/lib/set.c
@@ -11,6 +11,7 @@
 #include <stdio.h>
 #endif
 
+#include <alloca.h>
 #include <string.h>
 #include <stdlib.h>
 #include <assert.h>
@@ -280,11 +281,13 @@ int log2i(int n)
 static
 int encode_golomb_Mshift(int c, int bpp)
 {
+    int Mshift;
+
     /*
      * XXX Slightly better Mshift estimations are probably possible.
      * Recheck "Compression and coding algorithms" by Moffat & Turpin.
      */
-    int Mshift = bpp - log2i(c) - 1;
+    Mshift = bpp - log2i(c) - 1;
 
     /* Adjust out-of-range values. */
     if (Mshift < 7)
@@ -315,20 +318,20 @@ int encode_golomb(int c, const unsigned *v, int Mshift, char *bitv)
     char *bitv_start = bitv;
     const unsigned mask = (1 << Mshift) - 1;
 
-    while (c > 0) {
-	c--;
-	unsigned v0 = *v++;
+    while (c-- > 0) {
+	unsigned v0, q, r;
 	int i;
-	/* first part: variable-length sequence */
-	unsigned q = v0 >> Mshift;
 
-	for (i = 0; i < (int)q; i++)
+	v0 = *v++;
+
+	/* first part: variable-length sequence */
+	q = v0 >> Mshift;
+	for (i = 0; i < (int) q; i++)
 	    *bitv++ = 0;
 	*bitv++ = 1;
 
 	/* second part: lower Mshift bits */
-	unsigned r = v0 & mask;
-
+	r = v0 & mask;
 	for (i = 0; i < Mshift; i++)
 	    *bitv++ = (r >> i) & 1;
     }
@@ -355,10 +358,13 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 
     /* next value */
     while (bitc > 0) {
-	/* first part */
-	unsigned q = 0;
-	char bit = 0;
+	unsigned q, r;
+	char bit;
+	int i;
 
+	/* first part */
+	q = 0;
+	bit = 0;
 	while (bitc > 0) {
 	    bitc--;
 	    bit = *bitv++;
@@ -377,14 +383,13 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v)
 	    return -1;
 
 	/* second part */
-	unsigned r = 0;
-	int i;
-
+	r = 0;
 	for (i = 0; i < Mshift; i++) {
 	    bitc--;
 	    if (*bitv++)
 		r |= (1 << i);
 	}
+
 	/* the value */
 	*v++ = (q << Mshift) | r;
     }
@@ -586,6 +591,7 @@ int encode_set(int c, unsigned *v, int bpp, char *base62)
     /* XXX v is non-const due to encode_delta */
     int Mshift = encode_golomb_Mshift(c, bpp);
     int bitc = encode_golomb_size(c, Mshift);
+    int len;
     char bitv[bitc];
 
     /* bpp */
@@ -612,7 +618,7 @@ int encode_set(int c, unsigned *v, int bpp, char *base62)
 	return -3;
 
     /* base62 */
-    int len = encode_base62(bitc, bitv, base62);
+    len = encode_base62(bitc, bitv, base62);
     if (len < 0)
 	return -4;
 
@@ -622,15 +628,15 @@ int encode_set(int c, unsigned *v, int bpp, char *base62)
 static
 int decode_set_init(const char *str, int *pbpp, int *pMshift)
 {
-    /* 7..32 values encoded with 'a'..'z' */
-    int bpp = *str++ + 7 - 'a';
+    int bpp, Mshift;
 
+    /* 7..32 values encoded with 'a'..'z' */
+    bpp = *str++ + 7 - 'a';
     if (bpp < 10 || bpp > 32)
 	return -1;
 
     /* golomb parameter */
-    int Mshift = *str++ + 7 - 'a';
-
+    Mshift = *str++ + 7 - 'a';
     if (Mshift < 7 || Mshift > 31)
 	return -2;
 
@@ -649,24 +655,32 @@ int decode_set_init(const char *str, int *pbpp, int *pMshift)
 static inline
 int decode_set_size(const char *str, int Mshift)
 {
+    int bitc;
+
     str += 2;
-    int bitc = decode_base62_size(str);
+    bitc = decode_base62_size(str);
+
     return decode_golomb_size(bitc, Mshift);
 }
 
 static
 int decode_set(const char *str, int Mshift, unsigned *v)
 {
+    char *bitv;
+    int bitc;
+    int c;
+
     str += 2;
+
     /* base62 */
-    char bitv[decode_base62_size(str)];
-    int bitc = decode_base62(str, bitv);
+    bitv = alloca(decode_base62_size(str));
+    bitc = decode_base62(str, bitv);
 
     if (bitc < 0)
 	return -1;
 
     /* golomb */
-    int c = decode_golomb(bitc, bitv, Mshift, v);
+    c = decode_golomb(bitc, bitv, Mshift, v);
     if (c < 0)
 	return -2;
 
@@ -731,30 +745,32 @@ void test_set(void)
 /* main API routine */
 int rpmsetcmp(const char *str1, const char *str2)
 {
+	int bpp1, Mshift1, c1, i1;
+	int bpp2, Mshift2, c2, i2;
+	int ge, le;
+	unsigned *v1, *v2;
+
 	if (strncmp(str1, "set:", 4) == 0)
 	    str1 += 4;
 	if (strncmp(str2, "set:", 4) == 0)
 	    str2 += 4;
 
 	/* initialize decoding */
-	int bpp1, Mshift1;
-	int bpp2, Mshift2;
-
 	if (decode_set_init(str1, &bpp1, &Mshift1) < 0)
 	    return -3;
 	if (decode_set_init(str2, &bpp2, &Mshift2) < 0)
 	    return -4;
 
 	/* make room for hash values */
-	unsigned v1[decode_set_size(str1, Mshift1)];
-	unsigned v2[decode_set_size(str2, Mshift2)];
+	v1 = alloca(sizeof(*v1) * decode_set_size(str1, Mshift1));
+	v2 = alloca(sizeof(*v2) * decode_set_size(str2, Mshift2));
 
 	/* decode hash values */
-	int c1 = decode_set(str1, Mshift1, v1);
+	c1 = decode_set(str1, Mshift1, v1);
 	if (c1 < 0)
 	    return -3;
 
-	int c2 = decode_set(str2, Mshift2, v2);
+	c2 = decode_set(str2, Mshift2, v2);
 	if (c2 < 0)
 	    return -4;
 
@@ -769,9 +785,8 @@ int rpmsetcmp(const char *str1, const char *str2)
 	}
 
 	/* compare */
-	int ge = 1;
-	int le = 1;
-	int i1 = 0, i2 = 0;
+	ge = 1; le = 1;
+	i1 = 0; i2 = 0;
 	while (i1 < c1 && i2 < c2) {
 	    if (v1[i1] < v2[i2]) {
 		le = 0;
@@ -840,14 +855,15 @@ void set_add(struct set *set, const char *sym)
 
 struct set *set_free(struct set *set)
 {
-    if (set) {
-	int i;
+    int i;
 
-	for (i = 0; i < set->c; i++)
-	    set->sv[i].s = _free(set->sv[i].s);
+    if (!set)
+	return NULL;
+
+    for (i = 0; i < set->c; i++)
+	set->sv[i].s = _free(set->sv[i].s);
+    set->sv = _free(set->sv);
 
-	set->sv = _free(set->sv);
-    }
     return NULL;
 }
 
@@ -889,16 +905,20 @@ int cmp_sv(const void *arg1, const void *arg2)
 /* This routine does the whole job. */
 const char *set_fini(struct set *set, int bpp)
 {
+    unsigned mask;
+    unsigned v[set->c];
+    char *base62;
+    int c, len, i;
+
     if (set->c < 1)
 	return NULL;
     if (bpp < 10)
 	return NULL;
     if (bpp > 32)
 	return NULL;
-    unsigned mask = (bpp < 32) ? (1u << bpp) - 1 : ~0u;
+    mask = (bpp < 32) ? (1u << bpp) - 1 : ~0u;
 
     /* hash sv strings */
-    int i;
     for (i = 0; i < set->c; i++)
 	set->sv[i].v = jenkins_hash(set->sv[i].s) & mask;
 
@@ -916,13 +936,12 @@ const char *set_fini(struct set *set, int bpp)
     }
 
     /* encode */
-    unsigned v[set->c];
     for (i = 0; i < set->c; i++)
 	v[i] = set->sv[i].v;
 
-    int c = uniqv(set->c, v);
-    char base62[encode_set_size(c, bpp)];
-    int len = encode_set(c, v, bpp, base62);
+    c = uniqv(set->c, v);
+    base62 = alloca(encode_set_size(c, bpp));
+    len = encode_set(c, v, bpp, base62);
     if (len < 0)
 	return NULL;
 
-- 
1.7.3.2

[devel] [PATCH 6/8] set.c: use function-like syntax for sizeof.

[Kirill A. Shutsemov]

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

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 lib/set.c |   14 +++++++-------
 1 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/lib/set.c b/lib/set.c
index 2a8d8b3..b4ed87d 100644
--- a/lib/set.c
+++ b/lib/set.c
@@ -219,7 +219,7 @@ void test_base62(void)
 	/* trigger some 'Z' */
 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     };
-    const int rnd_bitc = sizeof rnd_bitv;
+    const int rnd_bitc = sizeof(rnd_bitv);
     /* encode */
     char base62[encode_base62_size(rnd_bitc)];
     int len = encode_base62(rnd_bitc, rnd_bitv, base62);
@@ -407,7 +407,7 @@ void test_golomb(void)
 	/* koshka sela na taksi */
 	7, 6, 5, 4, 3, 2, 1,
     };
-    const int rnd_c = sizeof rnd_v / sizeof *rnd_v;
+    const int rnd_c = sizeof(rnd_v) / sizeof(*rnd_v);
     int bpp = 10;
     int Mshift = encode_golomb_Mshift(rnd_c, bpp);
     fprintf(stderr, "rnd_c=%d bpp=%d Mshift=%d\n", rnd_c, bpp, Mshift);
@@ -522,7 +522,7 @@ int cmpv(const void *arg1, const void *arg2)
 static
 void sortv(int c, unsigned *v)
 {
-    qsort(v, c, sizeof *v, cmpv);
+    qsort(v, c, sizeof(*v), cmpv);
 }
 
 static
@@ -545,7 +545,7 @@ static
 void test_aux(void)
 {
     unsigned v[] = { 2, 3, 1, 2, 7, 6, 5 };
-    int c = sizeof v / sizeof *v;
+    int c = sizeof(v) / sizeof(*v);
     maskv(c, v, 4 - 1);
     sortv(c, v);
     c = uniqv(c, v);
@@ -710,7 +710,7 @@ void test_set(void)
 	0x82ae, 0x8415, 0xa3e7, 0xb07e,
 	0xb584, 0xb89f, 0xbb40, 0xf39e,
     };
-    int rnd_c = sizeof rnd_v / sizeof *rnd_v;
+    int rnd_c = sizeof(rnd_v) / sizeof(*rnd_v);
     /* encode */
     int bpp = 16;
     char base62[encode_set_size(rnd_c, bpp)];
@@ -833,7 +833,7 @@ struct set {
 
 struct set *set_new()
 {
-    struct set *set = xmalloc(sizeof *set);
+    struct set *set = xmalloc(sizeof(*set));
 
     set->c = 0;
     set->sv = NULL;
@@ -923,7 +923,7 @@ const char *set_fini(struct set *set, int bpp)
 	set->sv[i].v = jenkins_hash(set->sv[i].s) & mask;
 
     /* sort by hash value */
-    qsort(set->sv, set->c, sizeof *set->sv, cmp_sv);
+    qsort(set->sv, set->c, sizeof(*set->sv), cmp_sv);
 
     /* warn on hash collisions */
     for (i = 0; i < set->c - 1; i++) {
-- 
1.7.3.2

[devel] [PATCH 7/8] set.c: cleanup self-tests

[Kirill A. Shutsemov]

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

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 lib/set.c |   94 +++++++++++++++++++++++++++++++++++++++----------------------
 1 files changed, 60 insertions(+), 34 deletions(-)

diff --git a/lib/set.c b/lib/set.c
index b4ed87d..a98e3f8 100644
--- a/lib/set.c
+++ b/lib/set.c
@@ -220,23 +220,29 @@ void test_base62(void)
 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     };
     const int rnd_bitc = sizeof(rnd_bitv);
+    char *base62, *bitv;
+    int i, len, bitc;
+
     /* encode */
-    char base62[encode_base62_size(rnd_bitc)];
-    int len = encode_base62(rnd_bitc, rnd_bitv, base62);
+    base62 = alloca(encode_base62_size(rnd_bitc));
+    len = encode_base62(rnd_bitc, rnd_bitv, base62);
     assert(len > 0);
-    assert(len == (int)strlen(base62));
+    assert(len == (int) strlen(base62));
     fprintf(stderr, "len=%d base62=%s\n", len, base62);
+
     /* The length cannot be shorter than 6 bits per symbol. */
     assert(len >= rnd_bitc / 6);
+
     /* Neither too long: each second character must fill at least 4 bits. */
     assert(len <= rnd_bitc / 2 / 4 + rnd_bitc / 2 / 6 + 1);
+
     /* decode */
-    char bitv[decode_base62_size(base62)];
-    int bitc = decode_base62(base62, bitv);
+    bitv = alloca(decode_base62_size(base62));
+    bitc = decode_base62(base62, bitv);
     fprintf(stderr, "rnd_bitc=%d bitc=%d\n", rnd_bitc, bitc);
     assert(bitc >= rnd_bitc);
+
     /* Decoded bits must match. */
-    int i;
     for (i = 0; i < rnd_bitc; i++)
 	assert(rnd_bitv[i] == bitv[i]);
     /* The remaining bits must be zero bits. */
@@ -402,39 +408,47 @@ static
 void test_golomb(void)
 {
     const unsigned rnd_v[] = {
-	/* do re mi fa sol la si */
 	1, 2, 3, 4, 5, 6, 7,
-	/* koshka sela na taksi */
 	7, 6, 5, 4, 3, 2, 1,
     };
     const int rnd_c = sizeof(rnd_v) / sizeof(*rnd_v);
-    int bpp = 10;
-    int Mshift = encode_golomb_Mshift(rnd_c, bpp);
+    char *bitv;
+    unsigned *v;
+    int bpp, Mshift;
+    int alloc_bitc, bitc;
+    int alloc_c, c, golomb_bpp;
+    int i;
+
+    bpp = 10;
+    Mshift = encode_golomb_Mshift(rnd_c, bpp);
     fprintf(stderr, "rnd_c=%d bpp=%d Mshift=%d\n", rnd_c, bpp, Mshift);
     assert(Mshift > 0);
     assert(Mshift < bpp);
+
     /* encode */
-    int alloc_bitc = encode_golomb_size(rnd_c, Mshift);
+    alloc_bitc = encode_golomb_size(rnd_c, Mshift);
     assert(alloc_bitc > rnd_c);
-    char bitv[alloc_bitc];
-    int bitc = encode_golomb(rnd_c, rnd_v, Mshift, bitv);
+    bitv = alloca(alloc_bitc);
+    bitc = encode_golomb(rnd_c, rnd_v, Mshift, bitv);
     fprintf(stderr, "alloc_bitc=%d bitc=%d\n", alloc_bitc, bitc);
     assert(bitc > rnd_c);
     assert(bitc <= alloc_bitc);
+
     /* decode */
-    int alloc_c = decode_golomb_size(bitc, Mshift);
+    alloc_c = decode_golomb_size(bitc, Mshift);
     assert(alloc_c >= rnd_c);
-    unsigned v[alloc_c];
-    int c = decode_golomb(bitc, bitv, Mshift, v);
+    v = alloca(sizeof(*v) * alloc_c);
+    c = decode_golomb(bitc, bitv, Mshift, v);
     fprintf(stderr, "rnd_c=%d alloc_c=%d c=%d\n", rnd_c, alloc_c, c);
     assert(alloc_c >= c);
+
     /* Decoded values must match. */
     assert(rnd_c == c);
-    int i;
     for (i = 0; i < c; i++)
 	assert(rnd_v[i] == v[i]);
+
     /* At the end of the day, did it save your money? */
-    int golomb_bpp = bitc / c;
+    golomb_bpp = bitc / c;
     fprintf(stderr, "bpp=%d golomb_bpp=%d\n", bpp, golomb_bpp);
     assert(golomb_bpp < bpp);
     fprintf(stderr, "%s: golomb test OK\n", __FILE__);
@@ -480,6 +494,7 @@ void test_delta(void)
 	1, 3, 7, 0
     };
     int c = 3;
+
     encode_delta(c, v);
     assert(v[0] == 1);
     assert(v[1] == 2);
@@ -546,6 +561,7 @@ void test_aux(void)
 {
     unsigned v[] = { 2, 3, 1, 2, 7, 6, 5 };
     int c = sizeof(v) / sizeof(*v);
+
     maskv(c, v, 4 - 1);
     sortv(c, v);
     c = uniqv(c, v);
@@ -711,25 +727,32 @@ void test_set(void)
 	0xb584, 0xb89f, 0xbb40, 0xf39e,
     };
     int rnd_c = sizeof(rnd_v) / sizeof(*rnd_v);
+    char *base62;
+    unsigned *v;
+    int bpp, Mshift;
+    int i, len, rc, c;
+
     /* encode */
-    int bpp = 16;
-    char base62[encode_set_size(rnd_c, bpp)];
-    int len = encode_set(rnd_c, rnd_v, bpp, base62);
+    bpp = 16;
+    base62 = alloca(encode_set_size(rnd_c, bpp));
+    len = encode_set(rnd_c, rnd_v, bpp, base62);
     assert(len > 0);
     fprintf(stderr, "len=%d set=%s\n", len, base62);
+
     /* decode */
-    int Mshift = bpp;
-    int rc = decode_set_init(base62, &bpp, &Mshift);
+    Mshift = bpp;
+    rc = decode_set_init(base62, &bpp, &Mshift);
     assert(rc == 0);
     assert(bpp == 16);
     assert(Mshift < bpp);
-    int c = decode_set_size(base62, Mshift);
+
+    c = decode_set_size(base62, Mshift);
     assert(c >= rnd_c);
-    unsigned v[c];
+    v = alloca(sizeof(*v) * c);
     c = decode_set(base62, Mshift, v);
+
     /* Decoded values must match. */
     assert(c == rnd_c);
-    int i;
     for (i = 0; i < c; i++)
 	assert(v[i] == rnd_v[i]);
     fprintf(stderr, "%s: set test OK\n", __FILE__);
@@ -952,35 +975,38 @@ const char *set_fini(struct set *set, int bpp)
 static
 void test_api(void)
 {
-    struct set *set1 = set_new();
+    struct set *set1, *set2;
+    const char *str10, *str11, *str20, *str21, *str22;
+    int cmp;
+
+    set1 = set_new();
     set_add(set1, "mama");
     set_add(set1, "myla");
     set_add(set1, "ramu");
-    const char *str10 = set_fini(set1, 16);
+    str10 = set_fini(set1, 16);
     fprintf(stderr, "set10=%s\n", str10);
 
-    int cmp;
-    struct set *set2 = set_new();
+    set2 = set_new();
     set_add(set2, "myla");
     set_add(set2, "mama");
-    const char *str20 = set_fini(set2, 16);
+    str20 = set_fini(set2, 16);
     fprintf(stderr, "set20=%s\n", str20);
     cmp = rpmsetcmp(str10, str20);
     assert(cmp == 1);
 
     set_add(set2, "ramu");
-    const char *str21 = set_fini(set2, 16);
+    str21 = set_fini(set2, 16);
     fprintf(stderr, "set21=%s\n", str21);
     cmp = rpmsetcmp(str10, str21);
     assert(cmp == 0);
 
     set_add(set2, "baba");
-    const char *str22 = set_fini(set2, 16);
+    str22 = set_fini(set2, 16);
     cmp = rpmsetcmp(str10, str22);
     assert(cmp == -1);
 
     set_add(set1, "deda");
-    const char *str11 = set_fini(set1, 16);
+    str11 = set_fini(set1, 16);
     cmp = rpmsetcmp(str11, str22);
     assert(cmp == -2);
 
-- 
1.7.3.2

[devel] [PATCH 8/8] set.c: update copyright notice

[Kirill A. Shutsemov]

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

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
---
 lib/set.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/lib/set.c b/lib/set.c
index a98e3f8..614212e 100644
--- a/lib/set.c
+++ b/lib/set.c
@@ -2,6 +2,7 @@
  * set.c - base62, golomb and set-string routines
  *
  * Copyright (C) 2010  Alexey Tourbin <at@altlinux.org>
+ * Copyright (C) 2010  Kirill A. Shutemov <kirill@shutemov.name>
  *
  * License: GPLv2+ or LGPL, see RPM COPYING
  */
-- 
1.7.3.2

Re: [devel] [PATCH 2/8] set.c: get rid of nested functions

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 255 bytes --]

On Tue, Nov 16, 2010 at 05:56:36PM +0200, Kirill A. Shutsemov wrote:
[...]
> +static inline
> +char *put_digit(char *base62, int c)
> -    void put_digit(int c)
> -    {

Why shouldn't this and other functions remain returning void?


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 2/8] set.c: get rid of nested functions

[Kirill A. Shutemov]

On Wed, Nov 17, 2010 at 01:14:58AM +0300, Dmitry V. Levin wrote:
> On Tue, Nov 16, 2010 at 05:56:36PM +0200, Kirill A. Shutsemov wrote:
> [...]
> > +static inline
> > +char *put_digit(char *base62, int c)
> > -    void put_digit(int c)
> > -    {
> 
> Why shouldn't this and other functions remain returning void?

We shift base62 to the next position and want caller to know about this.

So we have two options:

- return new position;
- pass char ** as argument instead of char *.

Do you prefere the last one? Or I missed something?

-- 
 Kirill A. Shutemov

Re: [devel] [PATCH 2/8] set.c: get rid of nested functions

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 746 bytes --]

On Wed, Nov 17, 2010 at 12:54:53AM +0200, Kirill A. Shutemov wrote:
> On Wed, Nov 17, 2010 at 01:14:58AM +0300, Dmitry V. Levin wrote:
> > On Tue, Nov 16, 2010 at 05:56:36PM +0200, Kirill A. Shutsemov wrote:
> > [...]
> > > +static inline
> > > +char *put_digit(char *base62, int c)
> > > -    void put_digit(int c)
> > > -    {
> > 
> > Why shouldn't this and other functions remain returning void?
> 
> We shift base62 to the next position and want caller to know about this.
> 
> So we have two options:
> 
> - return new position;
> - pass char ** as argument instead of char *.
> 
> Do you prefere the last one?

Which one is more readable,
base62 = put_digit(base62, 61);
or
put_digit(&base62, 61);
?


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 2/8] set.c: get rid of nested functions

[Kirill A. Shutemov]

On Wed, Nov 17, 2010 at 02:07:28AM +0300, Dmitry V. Levin wrote:
> On Wed, Nov 17, 2010 at 12:54:53AM +0200, Kirill A. Shutemov wrote:
> > On Wed, Nov 17, 2010 at 01:14:58AM +0300, Dmitry V. Levin wrote:
> > > On Tue, Nov 16, 2010 at 05:56:36PM +0200, Kirill A. Shutsemov wrote:
> > > [...]
> > > > +static inline
> > > > +char *put_digit(char *base62, int c)
> > > > -    void put_digit(int c)
> > > > -    {
> > > 
> > > Why shouldn't this and other functions remain returning void?
> > 
> > We shift base62 to the next position and want caller to know about this.
> > 
> > So we have two options:
> > 
> > - return new position;
> > - pass char ** as argument instead of char *.
> > 
> > Do you prefere the last one?
> 
> Which one is more readable,
> base62 = put_digit(base62, 61);
> or
> put_digit(&base62, 61);
> ?

Ok, I'll rework it.

Any comments on other patches?

-- 
 Kirill A. Shutemov

Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h

[REAL]

16.11.2010 21:56, Kirill A. Shutsemov пишет:
> From: Kirill A. Shutemov<kirill@shutemov.name>
>
> Let's try to make set-versions implementation more maintainable.

Для удобства:

http://www.altlinux.org/Чистка_кода_C/C++

-- 

REAL aka Евгений Ростовцев, программист ЦНИТ КемГУ

Re: [devel] [PATCH 2/8] set.c: get rid of nested functions

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 169 bytes --]

On Wed, Nov 17, 2010 at 01:10:15AM +0200, Kirill A. Shutemov wrote:
> Any comments on other patches?

It's hard to review a series of noop patches. :)


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h

[Alexey Tourbin]

On Tue, Nov 16, 2010 at 05:56:34PM +0200, Kirill A. Shutsemov wrote:
> Let's try to make set-versions implementation more maintainable.
> 
> Kirill A. Shutemov (8):
>   set.c, set.h: get rid of C++-style comments
>   set.c: get rid of nested functions

I reckon most of these changes aren't necessary.
This is my coding style, and yes, I use -std=gnu99 features.

>   set.c: fixup self-test functions declaration
>   set.c: slightly reformat code to increase its readability
>   set.c: do not mix declarations and code
>   set.c: use function-like syntax for sizeof.
>   set.c: cleanup self-tests
>   set.c: update copyright notice
> 
>  lib/set.c |  768 +++++++++++++++++++++++++++++++++++++------------------------
>  lib/set.h |   12 +-
>  2 files changed, 473 insertions(+), 307 deletions(-)

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Alexey Tourbin]

On Tue, Nov 16, 2010 at 05:56:42PM +0200, Kirill A. Shutsemov wrote:
> Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
> ---
>  lib/set.c |    1 +
>  1 files changed, 1 insertions(+), 0 deletions(-)
> 
> diff --git a/lib/set.c b/lib/set.c
> index a98e3f8..614212e 100644
> --- a/lib/set.c
> +++ b/lib/set.c
> @@ -2,6 +2,7 @@
>   * set.c - base62, golomb and set-string routines
>   *
>   * Copyright (C) 2010  Alexey Tourbin <at@altlinux.org>
> + * Copyright (C) 2010  Kirill A. Shutemov <kirill@shutemov.name>
>   *
>   * License: GPLv2+ or LGPL, see RPM COPYING
>   */

This is the most impudent patch in the series.

Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h

[Kirill A. Shutemov]

On Mon, Nov 22, 2010 at 08:40:46AM +0300, Alexey Tourbin wrote:
> On Tue, Nov 16, 2010 at 05:56:34PM +0200, Kirill A. Shutsemov wrote:
> > Let's try to make set-versions implementation more maintainable.
> > 
> > Kirill A. Shutemov (8):
> >   set.c, set.h: get rid of C++-style comments
> >   set.c: get rid of nested functions
> 
> I reckon most of these changes aren't necessary.

Cleanup is never necessary.

> This is my coding style, and yes, I use -std=gnu99 features.

Ok. Pushed to git. Just in case.

-- 
 Kirill A. Shutemov

Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h

[Alexey Tourbin]

On Mon, Nov 22, 2010 at 09:14:50AM +0200, Kirill A. Shutemov wrote:
> On Mon, Nov 22, 2010 at 08:40:46AM +0300, Alexey Tourbin wrote:
> > On Tue, Nov 16, 2010 at 05:56:34PM +0200, Kirill A. Shutsemov wrote:
> > > Let's try to make set-versions implementation more maintainable.
> > > 
> > > Kirill A. Shutemov (8):
> > >   set.c, set.h: get rid of C++-style comments
> > >   set.c: get rid of nested functions
> > 
> > I reckon most of these changes aren't necessary.
> Cleanup is never necessary.

"Cleanup" is inappropriate term here, along with "more maintainable".
Rather, the code in question could be "more portable".  E.g. nested
functions are non-portable.  But I find them convenient.

Thus I choose to sacrifice portability for convenience - I see no reason
to stick to c89, as long as gcc itself is portable.

> > This is my coding style, and yes, I use -std=gnu99 features.
> Ok. Pushed to git. Just in case.

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Alexey Tourbin]

On Mon, Nov 22, 2010 at 03:34:15PM +0300, Kharitonov A. Dmitry wrote:
> >>--- a/lib/set.c
> >>+++ b/lib/set.c
> >>@@ -2,6 +2,7 @@
> >>   * set.c - base62, golomb and set-string routines
> >>   *
> >>   * Copyright (C) 2010  Alexey Tourbin<at@altlinux.org>
> >>+ * Copyright (C) 2010  Kirill A. Shutemov<kirill@shutemov.name>
> >>   *
> >>   * License: GPLv2+ or LGPL, see RPM COPYING
> >>   */
> >This is the most impudent patch in the series.
> А кто такой этот Кирилл? почему он так 
> агрессивно пытается стать соавтором? не 
> сделав при этом ничего?

As the story goes, Kirill made some trivial changes to my code,
and the last (and the most impudent) change was to list himself
as a copyright holder of the code in question.

The question is then what's the enough amount of work to become
a copyright holder.  I believe that one has to write a distinct
piece of code that's not been written before, and the code should
exercise a distinct feature or trait that's not been available
before.  Trivial changes, including trivial bugfixes, do not amount
for authorship and/or copyright.

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 532 bytes --]

On Tue, Nov 23, 2010 at 03:48:28AM +0300, Alexey Tourbin wrote:
[...]
> The question is then what's the enough amount of work to become
> a copyright holder.  I believe that one has to write a distinct
> piece of code that's not been written before, and the code should
> exercise a distinct feature or trait that's not been available
> before.  Trivial changes, including trivial bugfixes, do not amount
> for authorship and/or copyright.

http://www.gnu.org/prep/maintain/maintain.html#Legally-Significant


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Alexey Tourbin]

On Tue, Nov 23, 2010 at 03:56:22AM +0300, Dmitry V. Levin wrote:
> On Tue, Nov 23, 2010 at 03:48:28AM +0300, Alexey Tourbin wrote:
> [...]
> > The question is then what's the enough amount of work to become
> > a copyright holder.  I believe that one has to write a distinct
> > piece of code that's not been written before, and the code should
> > exercise a distinct feature or trait that's not been available
> > before.  Trivial changes, including trivial bugfixes, do not amount
> > for authorship and/or copyright.
> 
> http://www.gnu.org/prep/maintain/maintain.html#Legally-Significant

GNU criteria are somewhat controversial.

1) "more than around 15 lines" is not a definition, and it won't stand in court.
2) "minor changes by the same person can add up to a significant contribution"
is morally wrong.  As if I can make a significant contribution by constantly
reindenting the code, back and forth.  I agree that some calculations might
be going on here, but I don't believe that a series of trivial contributions 
could've summed up to a non-trivial one.

My own criteria is as follows:
1) Show me the piece(s) of code that you've actually written.
2) Show me how it makes a difference.

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Kirill A. Shutemov]

On Tue, Nov 23, 2010 at 04:38:53AM +0300, Alexey Tourbin wrote:
> On Tue, Nov 23, 2010 at 03:56:22AM +0300, Dmitry V. Levin wrote:
> > On Tue, Nov 23, 2010 at 03:48:28AM +0300, Alexey Tourbin wrote:
> > [...]
> > > The question is then what's the enough amount of work to become
> > > a copyright holder.  I believe that one has to write a distinct
> > > piece of code that's not been written before, and the code should
> > > exercise a distinct feature or trait that's not been available
> > > before.  Trivial changes, including trivial bugfixes, do not amount
> > > for authorship and/or copyright.
> > 
> > http://www.gnu.org/prep/maintain/maintain.html#Legally-Significant
> 
> GNU criteria are somewhat controversial.

Just stop discussing this. I've drop it, before 'git push'.

-- 
 Kirill A. Shutemov

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Alexey Tourbin]

On Tue, Nov 23, 2010 at 08:42:25AM +0200, Kirill A. Shutemov wrote:
> On Tue, Nov 23, 2010 at 04:38:53AM +0300, Alexey Tourbin wrote:
> > On Tue, Nov 23, 2010 at 03:56:22AM +0300, Dmitry V. Levin wrote:
> > > http://www.gnu.org/prep/maintain/maintain.html#Legally-Significant
> > GNU criteria are somewhat controversial.
> Just stop discussing this. I've drop it, before 'git push'.

Anyway, I wonder why you ever THOUGHT you should fix my code.  As if it's
something wrong with the code (which it isn't).  I think it passed many
times a scrutiny (before it's been committed), and it looks GOOD.

Also, I payed a lot of time to write COMMENTS and explain why exactly
the code is supposed to work (the comments have been re-edited many times
before I felt them enough convincing).  Is there really something wrong
with the code, except for -std=gnu99 issues?

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Kirill A. Shutemov]

On Tue, Nov 23, 2010 at 02:50:04PM +0300, Alexey Tourbin wrote:
> On Tue, Nov 23, 2010 at 08:42:25AM +0200, Kirill A. Shutemov wrote:
> > On Tue, Nov 23, 2010 at 04:38:53AM +0300, Alexey Tourbin wrote:
> > > On Tue, Nov 23, 2010 at 03:56:22AM +0300, Dmitry V. Levin wrote:
> > > > http://www.gnu.org/prep/maintain/maintain.html#Legally-Significant
> > > GNU criteria are somewhat controversial.
> > Just stop discussing this. I've drop it, before 'git push'.
> 
> Anyway, I wonder why you ever THOUGHT you should fix my code.  As if it's
> something wrong with the code (which it isn't).  I think it passed many
> times a scrutiny (before it's been committed), and it looks GOOD.

No, it doesn't. Mixing code and declarations looks really ugly.
Other than that, probably, it's my style preferences. I like kernel code
style.

> 
> Also, I payed a lot of time to write COMMENTS and explain why exactly
> the code is supposed to work (the comments have been re-edited many times
> before I felt them enough convincing).

Comments are nice. Thanks.

> Is there really something wrong
> with the code, except for -std=gnu99 issues?

See my patchset about optimization of rpmsetcmp().

-- 
 Kirill A. Shutemov

Re: [devel] [PATCH 8/8] set.c: update copyright notice

[Michael Shigorin]

On Tue, Nov 23, 2010 at 02:50:04PM +0300, Alexey Tourbin wrote:
> Anyway, I wonder why you ever THOUGHT you should fix my code.  As if it's
> something wrong with the code (which it isn't).  I think it passed many
> times a scrutiny (before it's been committed), and it looks GOOD.

Не знаю, как он выглядит, но тормоза невыносимые.

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/