jacob navia said:

Hi

I have a heap of n objects of size Heap->ElementSize;

I receive from the client program an element to free, so

I have to put it in the free list. Since the heap is

just an array of n * ElementSize bytes, I find out

the index of the element to free from its address, then set

the bit to 1 to mark it as a free element.

Do you see anything wrong with this code?

static int AddToFreeList(ContainerHeap *heap,void *element)

{

char *p = heap->Heap;

char *elem = element;

size_t idx,byte;

idx = elem-p; // get the distance in bytes

if (idx < 0) return -1; // element not in the heap

idx /= heap->ElementSize; // Now in element size units

if (idx > l->Capacity) return -1; // element is not in the heap

byte = idx/8; // The byte in the bit map

// Set the bit in the bitmap to 1.

l->FreeMap[byte] |= (1 << (idx%8));

// Update counters

heap->Used--;

heap->FreeCount++;

return 1;

}

Specifically it is OK to use size_t?

I see lots of things that might be brought up in a code

review, but let me mention just three points.

First, granting that the nominal undefined behavior is acceptable

(and I have no problem with that), the range check comparisons can,

and I would argue should, be done without having to do a pointer

subtraction:

char *e = element, *base = ..., *limit = ...;

if( e < base || e >= limit ) return -1;

Even better if 'base' and 'limit' are stored in the structure

(and with an appropriate type) to begin with; the storage cost

of saving them is negligible.

Second, the question about size_t, and the /= on the calculated

index, are reflective of the "units" changing during the course

of the function. These concerns can be avoided by doing a single

index calculation after the range checks shown above (I am

using 'k' rather than 'idx'):

size_t k = (e-base) / heap->ElementSize;

Here I have used 'size_t' for the type, but it is always right

to use the same type as heap->Capacity, whatever type that

is, since the value for k is guaranteed to be less than

heap->Capacity (and greater than zero). The question about

what type to use then becomes trivial. This also allows

the variable to be made 'const' if that is desired.

Third, the setting of bits (a) is done in multiple steps, (b)

hardwires the constant 8 in the function body (and presumably

assuming that the bits are stored in an array of unsigned char

and CHAR_BIT == 8). This kind of bit-testing/setting/clearing

operations should be abstracted using macros that hide these

details and work for a range of unsigned types. Incorporating

the suggestion made else-thread to check the bit before setting

it, we would

if( ! IS_BIT_SET( heap->FreeMap, k ) ){

SET_BIT( heap->FreeMap, k );

... // set counters, etc

}

It isn't hard to write the IS_BIT_SET() and SET_BIT() macros

so that they work for different values of CHAR_BIT and for

unsigned types of different sizes, making the reasonable

assumption that these types have no padding bits (and that

assumption can be verified by a compile-time check).

Taking these three points into account, the resulting function

body would be:

char *e = element;

if( e < heap->base || e >= heap->limit ) return -1;

const size_t k = (e - heap->base) / heap->ElementSize;

if( ! IS_BIT_SET( heap->FreeMap, k ) ){

SET_BIT( heap->FreeMap, k );

heap->Used--;

heap->FreeCount++;

}

return 1;

Besides being shorter and simpler, I think a revision along

these lines makes it easier to decipher what the function is

doing. So not only are the various problems addressed, but

it's easy to see that they have been addressed.