* [devel] [PATCH 1/8] set.c, set.h: get rid of C++-style comments
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
@ 2010-11-16 15:56 ` Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 2/8] set.c: get rid of nested functions Kirill A. Shutsemov
` (8 subsequent siblings)
9 siblings, 0 replies; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [devel] [PATCH 2/8] set.c: get rid of nested functions
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
2010-11-16 22:14 ` Dmitry V. Levin
2010-11-16 15:56 ` [devel] [PATCH 3/8] set.c: fixup self-test functions declaration Kirill A. Shutsemov
` (7 subsequent siblings)
9 siblings, 1 reply; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* Re: [devel] [PATCH 2/8] set.c: get rid of nested functions
2010-11-16 15:56 ` [devel] [PATCH 2/8] set.c: get rid of nested functions Kirill A. Shutsemov
@ 2010-11-16 22:14 ` Dmitry V. Levin
2010-11-16 22:54 ` Kirill A. Shutemov
0 siblings, 1 reply; 26+ messages in thread
From: Dmitry V. Levin @ 2010-11-16 22:14 UTC (permalink / raw)
To: Kirill A. Shutsemov; +Cc: ALT Devel discussion list
[-- 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 --]
^ permalink raw reply [flat|nested] 26+ messages in thread* Re: [devel] [PATCH 2/8] set.c: get rid of nested functions
2010-11-16 22:14 ` Dmitry V. Levin
@ 2010-11-16 22:54 ` Kirill A. Shutemov
2010-11-16 23:07 ` Dmitry V. Levin
0 siblings, 1 reply; 26+ messages in thread
From: Kirill A. Shutemov @ 2010-11-16 22:54 UTC (permalink / raw)
To: Dmitry V. Levin; +Cc: ALT Devel discussion list
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
^ permalink raw reply [flat|nested] 26+ messages in thread* Re: [devel] [PATCH 2/8] set.c: get rid of nested functions
2010-11-16 22:54 ` Kirill A. Shutemov
@ 2010-11-16 23:07 ` Dmitry V. Levin
2010-11-16 23:10 ` Kirill A. Shutemov
0 siblings, 1 reply; 26+ messages in thread
From: Dmitry V. Levin @ 2010-11-16 23:07 UTC (permalink / raw)
To: Kirill A. Shutemov; +Cc: ALT Devel discussion list
[-- 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 --]
^ permalink raw reply [flat|nested] 26+ messages in thread* Re: [devel] [PATCH 2/8] set.c: get rid of nested functions
2010-11-16 23:07 ` Dmitry V. Levin
@ 2010-11-16 23:10 ` Kirill A. Shutemov
2010-11-17 17:55 ` Dmitry V. Levin
0 siblings, 1 reply; 26+ messages in thread
From: Kirill A. Shutemov @ 2010-11-16 23:10 UTC (permalink / raw)
To: ALT Devel discussion list
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
^ permalink raw reply [flat|nested] 26+ messages in thread
* [devel] [PATCH 3/8] set.c: fixup self-test functions declaration
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 ` [devel] [PATCH 2/8] set.c: get rid of nested functions Kirill A. Shutsemov
@ 2010-11-16 15:56 ` Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 4/8] set.c: slightly reformat code to increase its readability Kirill A. Shutsemov
` (6 subsequent siblings)
9 siblings, 0 replies; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [devel] [PATCH 4/8] set.c: slightly reformat code to increase its readability
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
` (2 preceding siblings ...)
2010-11-16 15:56 ` [devel] [PATCH 3/8] set.c: fixup self-test functions declaration Kirill A. Shutsemov
@ 2010-11-16 15:56 ` Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 5/8] set.c: do not mix declarations and code Kirill A. Shutsemov
` (5 subsequent siblings)
9 siblings, 0 replies; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [devel] [PATCH 5/8] set.c: do not mix declarations and code
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
` (3 preceding siblings ...)
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 ` Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 6/8] set.c: use function-like syntax for sizeof Kirill A. Shutsemov
` (4 subsequent siblings)
9 siblings, 0 replies; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [devel] [PATCH 6/8] set.c: use function-like syntax for sizeof.
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
` (4 preceding siblings ...)
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 ` Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 7/8] set.c: cleanup self-tests Kirill A. Shutsemov
` (3 subsequent siblings)
9 siblings, 0 replies; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [devel] [PATCH 7/8] set.c: cleanup self-tests
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
` (5 preceding siblings ...)
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 ` Kirill A. Shutsemov
2010-11-16 15:56 ` [devel] [PATCH 8/8] set.c: update copyright notice Kirill A. Shutsemov
` (2 subsequent siblings)
9 siblings, 0 replies; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* [devel] [PATCH 8/8] set.c: update copyright notice
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
` (6 preceding siblings ...)
2010-11-16 15:56 ` [devel] [PATCH 7/8] set.c: cleanup self-tests Kirill A. Shutsemov
@ 2010-11-16 15:56 ` Kirill A. Shutsemov
2010-11-22 5:49 ` Alexey Tourbin
2010-11-17 6:59 ` [devel] [PATCH 0/8] rpm: cleanup set.c and set.h REAL
2010-11-22 5:40 ` Alexey Tourbin
9 siblings, 1 reply; 26+ messages in thread
From: Kirill A. Shutsemov @ 2010-11-16 15:56 UTC (permalink / raw)
To: Dmitry V. Levin, Alexey Tourbin
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Kirill A. Shutemov
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
^ permalink raw reply [flat|nested] 26+ messages in thread* Re: [devel] [PATCH 8/8] set.c: update copyright notice
2010-11-16 15:56 ` [devel] [PATCH 8/8] set.c: update copyright notice Kirill A. Shutsemov
@ 2010-11-22 5:49 ` Alexey Tourbin
0 siblings, 1 reply; 26+ messages in thread
From: Alexey Tourbin @ 2010-11-22 5:49 UTC (permalink / raw)
To: ALT Linux Team development discussions
Cc: Alexey I. Froloff, Kirill A. Shutemov, Alexey Gladkov, Dmitry V. Levin
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.
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
` (7 preceding siblings ...)
2010-11-16 15:56 ` [devel] [PATCH 8/8] set.c: update copyright notice Kirill A. Shutsemov
@ 2010-11-17 6:59 ` REAL
2010-11-22 5:40 ` Alexey Tourbin
9 siblings, 0 replies; 26+ messages in thread
From: REAL @ 2010-11-17 6:59 UTC (permalink / raw)
To: ALT Linux Team development discussions
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 Евгений Ростовцев, программист ЦНИТ КемГУ
^ permalink raw reply [flat|nested] 26+ messages in thread* Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h
2010-11-16 15:56 [devel] [PATCH 0/8] rpm: cleanup set.c and set.h Kirill A. Shutsemov
` (8 preceding siblings ...)
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
9 siblings, 1 reply; 26+ messages in thread
From: Alexey Tourbin @ 2010-11-22 5:40 UTC (permalink / raw)
To: Kirill A. Shutsemov
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Dmitry V. Levin
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(-)
^ permalink raw reply [flat|nested] 26+ messages in thread* Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h
2010-11-22 5:40 ` Alexey Tourbin
@ 2010-11-22 7:14 ` Kirill A. Shutemov
2010-11-22 7:38 ` Alexey Tourbin
0 siblings, 1 reply; 26+ messages in thread
From: Kirill A. Shutemov @ 2010-11-22 7:14 UTC (permalink / raw)
To: Alexey Tourbin; +Cc: Alexey I. Froloff, devel, Alexey Gladkov, Dmitry V. Levin
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
^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: [devel] [PATCH 0/8] rpm: cleanup set.c and set.h
2010-11-22 7:14 ` Kirill A. Shutemov
@ 2010-11-22 7:38 ` Alexey Tourbin
0 siblings, 0 replies; 26+ messages in thread
From: Alexey Tourbin @ 2010-11-22 7:38 UTC (permalink / raw)
To: Kirill A. Shutemov
Cc: Alexey I. Froloff, devel, Alexey Gladkov, Dmitry V. Levin
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.
^ permalink raw reply [flat|nested] 26+ messages in thread