CODEWITHSUNDEEP
c
Joe
Joe

Reputation: 43

Analyzing and Understand what this code does

Long time lurker, first time poster. I'm a student and haven't touched a programming course in two years. Now that I'm taking courses again, I'm having difficulty reading and understanding other people's code. I have a sample-code here from HMC containing a portion of a simple memory allocator in C.

void free_block(ptr p) {
     *p = *p & ~1;                         /* clear allocated flag */    
     next = (unsigned*)((char*)p + *p);    /* find next blk */   
     if ((*next & 1) == 0)                 /* if not allocated... */     
     *p += *next;                          /*   add to this block */
      }

Despite the comments, I'm still having confusion as to what's going on here exactly. I know what the code does but I would never be able to code this myself. If someone could possibly explain the mathy portions of this code, I would be extremely grateful.

Upvotes: 4

Views: 85

Answers (2)

John C
John C

Reputation: 1981

The operations are presumably clear, so I'll try to handle the actual interpretation in context.

*p = *p & ~1;                         /* clear allocated flag */

The ~ operator complements the bits. So, ~1 is all 1 bits except the last, therefore zeroing out the last bit.

We don't know why...yet.

next = (unsigned*)((char*)p + *p);    /* find next blk */

Here, we have p cast to a pointer to a char ((char*)p), added to whatever the contents of p happen to be. That sum is treated as a pointer to an unsigned int. More or less, you're treating p as an offset from itself.

I'm pretty sure this is a bad idea without a lot more support code to make sure it's safe, but you're reading the code, not writing it...

if ((*next & 1) == 0)                 /* if not allocated... */

We now know why the least-significant bit was dropped in the first line. In this scheme, the code uses that bit to mark that the block has been allocated.

    *p += *next;                      /*   add to this block */

Here, we're just pushing p to beyond the thing we last allocated.

Without knowing what next points at, we can guess that it's moving through some sort of linked list-like structure. It's precarious, though, without knowing how p gets populated and how those pointers get structured.

But the upshot is that the code claims the next block and skips the pointer past it.

Upvotes: 1

Jeff
Jeff

Reputation: 2505

Due to byte alignment, the last binary bit is not needed for allocation size, so instead it is being used as a flag whether that block is allocated. The size of the allocation, is represented by the value at the beginning of the block.

~1 is a bitwise inverse of 1, meaning instead of 0x01, it is 0xFE

 *p = *p & ~1;                         /* clear allocated flag */

 0xFFFFFFFE 
(1111 1111 1111 1111 1111 1111 1111 1110)

A bitwise AND operation with the current value clears the last bit. The result is the size of the original allocation.

Technically, it dereferences the value at the address at p, and performs a bitwise AND operation with 0xFFFFFFFE effectively keeping all of the value bits but the least significant (ensuring the value no longer ends with a 1 if it originally did).

 next = (unsigned*)((char*)p + *p);    /* find next blk */

'next' is a pointer that point to the subsequent location from p + [result value from the above statement]

 if ((*next & 1) == 0)                 /* if not allocated... */     
    *p += *next;                          /*   add to this block */

if the binary value at 'next' does not end with a one (bitwise AND operation), take the value at 'p' and add the value at 'next', and assign the result to the location at 'p'.

So, in other words, if the next block is unallocated, then the original block includes it by adding that block size to itself (effectively removing it's existence).

Good luck. I hope this helps.

Upvotes: 1

Related Questions