Creating a struct at address pointed by pointer

Question

I have a unsigned char* head that is pointing to a certain addess in memory and now I have to create a typedef struct that I've declared starting at the location of that pointer...I am confused on how to do that!

Here is the declaration of the typedef

 typedef struct {
    struct block *next;
    struct block *prev;
    int size;
    unsigned char *buffer;
} block;

My assignment involves implementing malloc, so I can't use malloc. A block is part of a free_list which contains all chunks of free memory blocks that I have in my program heap. Hence, the previous and next pointers that point to the previous and next free blocks of memory.

Head points to the start of the free_list. When I have to split say the first block of free memory to satisfy a malloc() request that needs less space then that free block has I need to move my head and create a new block struct there.

Hope this makes sense. If not, the assignment looks something like this

So you have an `unsigned char *` that you know is really a `block *` and you want to access the `block`? — mu is too short, Mar 23 '13 at 22:19
Are you sure that certain address has allocation belonging to your application? — Volkan, Mar 23 '13 at 22:20
@Georges and you allocated it with the correct size, i.e. sizeof(block)? Why is it an unsigned char* now? — Geier, Mar 23 '13 at 22:23
block* head = (block*)malloc(sizeof(block));/* would be a better one. +1 to @Geier */ — Volkan, Mar 23 '13 at 22:24
head points to the start of a place in memory where I can overwrite data...You may assume that I have enough space! — Georges Krinker, Mar 23 '13 at 22:25
@lshan except that you must not cast the return value of `malloc()`. — , Mar 23 '13 at 22:26
@H2CO3 It is not a must, just unnecessary since it is a void *. I agree. — Volkan, Mar 23 '13 at 22:27
@lhsan [it **is** a must.](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) - in other words, casting it is an error. — , Mar 23 '13 at 22:29
@H2CO3 read the link you have given carefully. And no religions in computer languages area please ... — Volkan, Mar 23 '13 at 22:32
@lhsan I've read it several times carefully. This is not a religion, these are facts - this is still C and not C++ here. — , Mar 23 '13 at 22:33

score 1 · Accepted Answer · answered Mar 23 '13 at 22:44

Your struct has no tag, so you need to give it one in order for it to point to itself:

 typedef struct block {
    struct block *next;
    struct block *prev;
    int size;
    unsigned char *buffer;
} block;

If you're using C99 you can initialise the memory at head directly, if necessary, without declaring a temporary struct block:

*(block *)head = (block){NULL, NULL, 0, NULL};

You now have a struct block at the address head, as long as you cast it properly.

e.g.

((block *)head)->size = 5;

Or you assign a cast pointer to it:

block *p = (block *)head;
p->size = 5;

score 0 · Answer 2 · answered Mar 23 '13 at 22:22

0

unsigned char* head = /* whatever you have assuming that it has a sufficient size. */;

/* Create a block in memory */
block* b = (block*)malloc(sizeof(block));

/*
*   modify data in b here as you wish.
*/
b->next = 0;
b->prev = 0;
/* etc... */

/* copy b to head */
memcpy(head, b, sizeof(block));

/* free block */
free(b);

The above assumes that head has enough space to store an instance of block. What it does is create a block, and copy the memory to the position of head, then free the allocated block.

answered Mar 23 '13 at 22:22

user123

8,970
2
31
52

1

He still needs to know that it requires enough space to store memory of size (block) to avoid any seg faults or errors. – user123 Mar 23 '13 at 22:24
The point of the assignment is to implement malloc(), hence I shouldn't be using malloc() lol... – Georges Krinker Mar 23 '13 at 22:26
1

That information would've been useful in the Question description :P – user123 Mar 23 '13 at 22:28
@Magtheridon96: http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc – Mat Mar 23 '13 at 23:08

score 0 · Answer 3 · answered Mar 23 '13 at 22:28

0

From comments:

head points to the start of a place in memory where I can overwrite data...You may assume that I have enough space!

Then to obtain a properly typed pointer:

struct block *p = (struct block *)head;

and to have a copy of the block:

struct block b = *(struct block *)head;

answered Mar 23 '13 at 22:28

Not a copy... b becomes a structural accessor. – Volkan Mar 23 '13 at 22:29
I'm confused how b now holds a block struct at location &head. – Georges Krinker Mar 23 '13 at 22:31
@lhsan Docs please. I couldn't find the expression "structural accessor" using Google. Do you mean that if I write `b.member = 42;` then in the original struct, it will be changed to 42 too? Because it won't. – Mar 23 '13 at 22:31
@GeorgesKrinker It doesn't. It holds the same contents as `*head` at another address. – Mar 23 '13 at 22:31
struct block b = *(struct block *)head; means: symbol b accesses contents of memory pointed by head as a struct block. So modifying b will modify anything at head... b.member = head->member – Volkan Mar 23 '13 at 22:35
@lhsan Exactly. And now we have two instances of the struct: `*head` and `b`. – Mar 23 '13 at 22:36
Oh you mean ... I think instance as a real memory occupying thing, so head and b are symbols to access them, head is a pointer b is a struct (actually a pointer but compiler now considers it as struct itself) So sorry for the misunderstanding...Really a copy for me is a literal allocation with cloned data. (Old timer I am said yoda)... – Volkan Mar 23 '13 at 22:38

Gene · Answer 4 · 2013-03-23T23:04:56.290

The operating system will provide an API call to allocate blocks of memory that your malloc can carve up and provide to callers. In Linux/unix look at sbrk. In Windows look at the Win32 heap API. Your records will point into this block. Making sure no two allocated sections of the block overlap is the job of your allocator code.

It looks like your records are implementing a free list. So how are you going to allocate list nodes when you don't have an allocator (yet)? The usual solution is to do it in the free blocks themselves. So a free block has the structure:

typedef struct free_block {
    struct free_block *next, *prev;
    size_t size;
    unsigned char buffer[1];
} FREE_BLOCK;

Now this data structure actually lies at the start of a free block. Its buffer has only 1 byte in the declaration, but the actual buffer is size bytes. Initially you'd have something like:

static FREE_BLOCK *free_list = sbrk(ARENA_SIZE);
free_list->next = free_list->prev = free_list;
free_list->size = ARENA_SIZE - offsetof(FREEBLOCK, buffer);

This places the whole arena on the free list as a single block. Your allocator will search free_list to find a block that's big enough, carve out the piece it needs, put the remaining small block (if any) back on the free list. For freeing, it will add the freed block to the list and coalesce adjacent blocks.

Simple free list allocators differ in how they choose the free block to allocate from: first fit, rotating first fit, best fit, worst fit, etc. In practice rotating first fit seems to work as well as or better than any of the others.

Incidentally, all of the common algorithms implemented with free lists don't need double links. Single ones will do.

Since this is an academic assignment, it should be fine to just call malloc (instead of an operating system API) to establish the big block (often called the "arena") your allocator will manage. You could also declare a big array of bytes.

Creating a struct at address pointed by pointer

4 Answers4

Linked