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? Step through
the code in the
C Tutorial! 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! Do 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 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.
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 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 is important 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
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 can use them to your advantage.
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.
