summaryrefslogtreecommitdiff
path: root/src/intset.c
diff options
context:
space:
mode:
authorAlon Diamant <alon@everything.me>2014-12-21 15:08:44 +0200
committerAlon Diamant <alon@everything.me>2014-12-21 16:13:45 +0200
commitd74a5a088036342ed430c6199d69f00610e14370 (patch)
treee8440c16347cce26d834992286005efb5b634b5b /src/intset.c
parente3436dd9b886da95b62c347b68be5366877f7b91 (diff)
downloadredis-d74a5a088036342ed430c6199d69f00610e14370.tar.gz
Following @mattsta's friendly review:
1. memory leak in t_set.c has been fixed 2. end-of-line spaces has been removed (from all over the place) 3. for loops have been ordered up to match existing Redis style (less weird) 4. comments format has been fixed (added * in the beggining of every comment line)
Diffstat (limited to 'src/intset.c')
-rw-r--r--src/intset.c52
1 files changed, 21 insertions, 31 deletions
diff --git a/src/intset.c b/src/intset.c
index 21a65994f..92c4ecd6e 100644
--- a/src/intset.c
+++ b/src/intset.c
@@ -261,22 +261,19 @@ int64_t intsetRandom(intset *is) {
return _intsetGet(is,rand()%intrev32ifbe(is->length));
}
-/* How many times bigger should the set length be compared to the requested
+/* How many times bigger should the set length be compared to the requested
* count of members for us to use the Floyd algorithm instead of
- the Knuth algorithm */
+ * the Knuth algorithm */
#define RANDOMMEMBERS_ALGORITHM_SELECTION_RATIO (2)
-/* Copies 'count' random members from the set into the 'values' array.
- 'values' must be an array of int64_t values, of length 'count'.
- Returns the amount of items returned. If this amount is less than 'count',
- then the remaining 'values' are left uninitialized. */
+/* Copies 'count' random members from the set into the 'values' array.
+ * 'values' must be an array of int64_t values, of length 'count'.
+ * Returns the amount of items returned. If this amount is less than 'count',
+ * then the remaining 'values' are left uninitialized. */
int intsetRandomMembers(intset *is, int64_t* values, int count) {
/* We don't check that is and values are non-NULL - the caller must
- play nice. */
- /* redisAssert(is != NULL);
- redisAssert(values != NULL);
- redisAssert(count > 0); */
+ * play nice. */
int length = intsetLen(is);
@@ -286,19 +283,17 @@ int intsetRandomMembers(intset *is, int64_t* values, int count) {
}
/* Choose between the Knuth shuffle algorithm, O(1) space, O(length) time,
- and the Floyd algorithm, O(length) space, O(count) time. */
+ * and the Floyd algorithm, O(length) space, O(count) time. */
if ((RANDOMMEMBERS_ALGORITHM_SELECTION_RATIO * count) > length) {
/* If the count of members requested is almost the length of the set,
- use the Knuth shuffle algorithm, O(1) space, O(length) time. */
+ * use the Knuth shuffle algorithm, O(1) space, O(length) time. */
/* First, fill the values array with unique random indexes inside
- the set. */
+ * the set. */
int in, im, rn, rm;
im = 0;
- for (in = 0;
- in < length && im < count;
- in++) {
+ for (in = 0; in < length && im < count; in++) {
rn = length - in;
rm = count - im;
@@ -309,10 +304,10 @@ int intsetRandomMembers(intset *is, int64_t* values, int count) {
} else {
- /* If the length is considerably more than the count of members
- requested, use Robert Floyd's algorithm, O(length) space,
- O(count) time.
- Based on Jon Bentley's Programming Pearls */
+ /* If the length is considerably more than the count of members
+ * requested, use Robert Floyd's algorithm, O(length) space,
+ * O(count) time.
+ * Based on Jon Bentley's Programming Pearls */
int64_t *is_used = zcalloc(sizeof(int64_t) * length);
int in, im, r;
@@ -320,18 +315,15 @@ int intsetRandomMembers(intset *is, int64_t* values, int count) {
r = 0;
im = 0;
- for (in = length - count;
- in < length && im < count;
- in++) {
+ for (in = length - count; in < length && im < count; in++) {
/* Generate a random number r */
- r = rand() % (in + 1);
+ r = rand() % (in + 1);
/* Do we already have the value in r? */
if (is_used[r]) {
-
/* Use in instead of the generated number */
- r = in;
+ r = in;
}
values[im++] = r ;
@@ -345,10 +337,8 @@ int intsetRandomMembers(intset *is, int64_t* values, int count) {
/* Replace each random index with the value stored there in the intset */
uint8_t encoding = intrev32ifbe(is->encoding);
- for (int currentValue = 0;
- currentValue < count;
- currentValue++) {
- values[currentValue] =
+ for (int currentValue = 0; currentValue < count; currentValue++) {
+ values[currentValue] =
_intsetGetEncoded(is, values[currentValue], encoding);
}
@@ -457,7 +447,7 @@ int main(int argc, char **argv) {
assert(_intsetValueEncoding(+2147483647) == INTSET_ENC_INT32);
assert(_intsetValueEncoding(-2147483649) == INTSET_ENC_INT64);
assert(_intsetValueEncoding(+2147483648) == INTSET_ENC_INT64);
- assert(_intsetValueEncoding(-9223372036854775808ull) ==
+ assert(_intsetValueEncoding(-9223372036854775808ull) ==
INTSET_ENC_INT64);
assert(_intsetValueEncoding(+9223372036854775807ull) ==
INTSET_ENC_INT64);