From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on sa.int.altlinux.org X-Spam-Level: X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DNS_FROM_OPENWHOIS autolearn=no version=3.2.5 From: "Kirill A. Shutsemov" To: "Dmitry V. Levin" , Alexey Tourbin Date: Tue, 16 Nov 2010 17:56:35 +0200 Message-Id: <1289923002-14132-2-git-send-email-kirill@shutemov.name> X-Mailer: git-send-email 1.7.2.3 In-Reply-To: <1289923002-14132-1-git-send-email-kirill@shutemov.name> References: <1289923002-14132-1-git-send-email-kirill@shutemov.name> Cc: "Alexey I. Froloff" , devel@lists.altlinux.org, Alexey Gladkov , "Kirill A. Shutemov" Subject: [devel] [PATCH 1/8] set.c, set.h: get rid of C++-style comments X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 16 Nov 2010 15:57:02 -0000 Archived-At: List-Archive: List-Post: From: Kirill A. Shutemov Signed-off-by: Kirill A. Shutemov --- 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