Casting.
Take a look at the implementations of hl_init and
hl_alloc. Notice that casting
the heap to a heap_header_t * is
a straightforward and very readable way to set and access the
fields of the otherwise unspecified heap.
print_debug functions.
Look at the function print_debug_entering_init. It
only prints "Entering hl_init()" to the screen. Although this
function may be useful to a programmer when implementing and
debugging, it is not the kind of information that should be
printed to the screen when a program includes and makes calls
to your heaplib library. Novice programmers
notoriously litter their code with print statements that are
commented in and out as they code. This is not good form,
especially since some straggling printf's almost
always remain in the final version of the code. Print
statements can be particularly devastating during a long run --
at best they make the code painfully slow; at worst they fill
up the hard drive and make the computer unusable.
One solution to this problem is to create a variable such as
debug_mode_f (_f often indicates a flag in C)
and put the print statement inside an if statement that
checks the variable:
if (print_debug_f) {
print_heap(heap);
}
This solution has the nice property that (if tied to a command line
option) the flag can be turned off and on each time you run the
program. The problem with this approach is that even your
"production-level" code will be littered with if
statements that always evaluate to false.
The code you have been given solves the problem by placing the
body of the print statement as the controlled text in
a conditional group:
void print_debug_entering_init() {
#ifdef PRINT_DEBUG
printf("Entering hl_init()\n");
#endif
}
The preprocessor (part of the compiler) will only insert the
controlled text if the PRINT_DEBUG has been
defined/set.
This Macro approach requires re-compiling in
order to insert the print statements. If you didn't want to
create a separate function, you could also simply wrap
the printf directly:
#ifdef PRINT_DEBUG
printf("the value of x is %d\n", x);
#endif
This may not be the best strategy for every scenario, but it
is good for this assignment. Do not use any print
statements inside your heaplib.c that are not
wrapped in an
#ifdef flag. Compiling
and Running Your Code discussed how to turn the flag on and off
at compile time.
Pointer arithmetic.
To implement this assignment, you will need to understand pointer arithmetic.
As a basic example, see the following snippet of code:
int array[4];
int *ptr = &array + 1;
What do you think ptr points to? Not sure? Paste
the code into
the C
Tutorial, click on "Visualize Execution", and step through
it. When you add 1 to the pointer, the unit of addition
is int, meaning that you're taking the base
address of array, and saying "go one integer
later". The 1 is actually 1 integer, or 4 bytes.
When you are manipulating pointers in this assignment, you
may often want to add "raw bytes". For example, if you want to
get the address that is 16 bytes into your heap, which you've
already cast to be a heap_header_t *, you would
need to write:
heap_header_t *header = (heap_header_t *)heap;
void *sixteen_later = ((char *)header)+16;
Because we suspect you might want to do addition like this a
lot, we've provided you with a simple #define:
#define ADD_BYTES(base_addr, num_bytes) (((char *)(base_addr)) + (num_bytes))
which you can could then use as follows:
heap_header_t *header = (heap_header_t *)heap;
void *sixteen_later = ADD_BYTES(header, 16);
C is not the same everywhere! You should not assume
that you know the size of all variable types in
C. An int might be 4 bytes on one machine and 8
bytes on another. This is one reason why it is VERY
important to use the VM or the Linux machines we have
provided for this class for this specific assignment. If you
never run your code on the machines we test them on, you may
be in for a horrible, seg-faulty surprise. It is always a
good idea to use sizeof() instead of assuming
you know the size of any variable or type in your
code. Alternatively, uintptr_t in
<stdint.h> is guaranteed to contain
the size of a pointer on the machine where the executable is
running. You may find this useful.
Another aspect of C is that the compiler will align your
structures for you. How it performs the alignment varies not
only by machine but also by operating system, so once again,
do not make any assumptions. As an example, look at the
definition of heap_header_t.
typedef struct _heap_header_t {
unsigned int heap_size;
block_info_t blocks[N_SUPPORTED_BLOCKS];
bool in_use_f[N_SUPPORTED_BLOCKS];
} heap_header_t ;
How large is this structure? hl_alloc
calculates the size of the header to be:
sizeof(unsigned int) /* heapsize */
+ sizeof(block_info_t) * N_SUPPORTED_BLOCKS /* block info */
+ sizeof(bool) * N_SUPPORTED_BLOCKS /* in use */
However, if you simply said sizeof(heap_header_t)
you might get a different answer because the size of the
structure is typically rounded to a size that is divisible by 4
(or sometimes 8). This is one of the reasons we require you to
keep your block pointers also 8-byte aligned. (This is also one
of the reasons we did not put the in_use_f flags
inside the block_info_t structure.) You should
decide exactly how you want to pack your data in the heap. It
will be important for you to understand structure alignment so
that as you make these decisions you understand how to
implement them.
Using Macros.
A macro is a <keyword,
definition> pair. Any reference to the keyword will be
replaced by the definition at compile time. You may be
familiar with simple macros such as:
#define ALIGNMENT 8
which is a great way to rid your code of magic numbers. Macros can
also be more complex, taking arguments. For example:
/* Useful shorthand: casts a pointer to a (char *) before adding */
#define ADD_BYTES(base_addr, num_bytes) (((char *)(base_addr)) + (num_bytes))
We recommend using macros for any complicated but simple tasks; your
code will be much more readable, maintainable, and debug-able at no
performance cost.
Ternary Operators.
You will also notice that a ternary operator is used in the
print_block_header function of heaplame. This is very
useful as it allows you to have a conditional output without explicitly
writing an if statement.
block->in_use_f ? "Yes" : "No"
The value before the ? is a boolean expression, and if
true, evaluates to "Yes", otherwise it evaluates to
"No".
Note that the ternary operator has very low precedence, so be sure to
wrap your ternary operator usage in parentheses! i.e.
(x ? 1 : 2)
instead of
x ? 1 : 2
Student implementations of dynamic memory allocators are notoriously ugly
and impossible to debug. Yours should not be. First, because you
will make your own life a living hell. Second, because we will deduct
style points for anything egregious. We have given you sample code with
all sorts of tricks in it because these are tricks that expert
programmers know about and use regularly. Now that you have been shown
these techniques, you will be expected to use them.
Cost of a ridiculously long project writeup? 15 minutes. Shedding
your status as a novice and being able to produce code that is readable,
debug-able, and portable? Priceless.
