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)

Enhancement Request in file cq.c

Unassigned

Bill Parker

BIT-1423

Normal

Configure