Add power of 2 test to file(s) 'cq.c/cq.h' (revises BIT-1423)

Description

Subj: Add power of 2 test to file(s) 'cq.c/cq.h' (revised)

This replaces the cq.c code/patch in BIT-1423...

Hello All,

Here is a hunk of code which is a FIXME to the following statement:

/* XXX could check that nbuckets is a power of 2 */

In directory 'src', file 'cq.c'

The patch file which adds this test is below:

— cq.c.orig 2015-06-06 19:01:58.220926680 -0700
+++ cq.c 2015-06-08 18:36:37.323755402 -0700
@@ -414,6 +414,15 @@
return hp->max_qlen;
}

+int cq_IsPowerOfTwo(unsigned int x)
+{
+ /* This function returns one (1) if val is a power of 2, i.e. */
+ /* 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024...2^31 */
+ /* or zero (0) if it isn't a power of two */
+
+ return ((x != 0) && ((x & (~x + 1)) == x));
+}
+
/* Return without doing anything if we fail to allocate a new bucket array */
static int
cq_resize(register struct cq_handle *hp, register int grow)
@@ -422,6 +431,7 @@
register size_t size;
register struct cq_bucket *bp, *bp2, *buckets, *oldbuckets;
struct cq_handle savedhandle;
+ int power_of_2_result; /* for power of two call */

if (hp->noresize)
return (0);
@@ -444,6 +454,11 @@

/* XXX could check that nbuckets is a power of 2 */

+ power_of_2_result = cq_IsPowerOfTwo((unsigned int)nbuckets);
+
+ if (power_of_2_result == 0) /* If this is zero, nbuckets is NOT a power of 2 */
+ return (-1); /* do we need to print a warning/error here as well? */
+
size = sizeof(*buckets) * nbuckets;
buckets = (struct cq_bucket *)malloc(size);
memory_allocation += size;

====================================================================

The function above is a one-liner that can be found on the Web.

The first half of the expression ensures that x is a positive integer.

The second half of the expression, (x & (~x + 1)) == x, is true only
when x is a power of two. It compares x with its two’s complement.

The two’s complement of x is computed with ~x + 1, which inverts the
bits of x and adds 1 (~x + 1 is equivalent to -x, but negation is
technically illegal for an unsigned integer).

Let n be the position of the leftmost 1 bit if x. If x is a power of
two, its lone 1 bit is in position n. This means ~x has a 0 in
position n and 1s everywhere else. When 1 is added to ~x, all
positions below n become 0 and the 0 at position n becomes 1.

In other words, the carry propagates all the way to position n. So
what happens is this: negating x inverts all its bits, but adding
1 inverts them back, from position n on down. So, (x & (~x + 1))
== x is true.

====================================================================

Here is the modification to file 'cq.h' which adds the function
prototype for cq_IsPowerOfTwo:

— cq.h.orig 2015-06-09 08:35:29.001007785 -0700
+++ cq.h 2015-06-09 08:36:08.194989138 -0700
@@ -5,6 +5,7 @@
void *cq_remove(struct cq_handle *, double, void *);
int cq_size(struct cq_handle *);
int cq_max_size(struct cq_handle *);
+int cq_IsPowerOfTwo(unsigned int);
unsigned int cq_memory_allocation(void);
#ifdef DEBUG
void cq_debug(struct cq_handle *, int);

====================================================================

I am attaching the patch file(s) to this bug report

Bill Parker (wp02855 at gmail dot com)

Environment

Enhancement Request in file cq.c

Assignee

Unassigned

Reporter

Bill Parker

Labels

External issue ID

BIT-1423

Components

Affects versions

Priority

Normal
Configure