Heap alloc in c

Question

#include <stdio.h>
#include <malloc.h>
typedef struct Node {
    int value;      //4
    struct Node* next;      //4
}Node;
Node *create();
void add();
void del();
void search();

Node *create(int v) {
     Node *first;
     first = (Node *)(calloc(1,sizeof(*first)));
     first->value = v;
     first->next = NULL;
     return first;
}
void add(Node **head,int v) {
    Node *p;
    p = (Node *)(calloc(1,sizeof(*p)));
    p->value = v;
    p->next = *head;
    *head = p;

 }
void search(Node *head) {
    Node *p;
    p=head;
    while(p != NULL) {
        printf("address is %d;value address is %d;next address is %d;next content is %d\n",p,&(p->value),&(p->next),p->next);
        p = p->next;
   }
}



int main() {
     Node *head;
     head = create(0);
     add(&head,1);
     add(&head,2);
     add(&head,3);
     search(head);
}

sizeof(Node) == 8, but why is every node's size in the heap is 16 bytes? thinks (my system is 32bit). struct node is 4bytes + 4bytes = 8bytes.

Answer 1

Regarding the real question "why is every node's size in the heap is 16 bytes?"

Well, you can't expect that one memory block will lay exactly at the end of where the previous memory block sits. you can't assume anything about how the heap is managed intenally. two blocks can sit in a gigabyte distance from one another even if they allcoated consequently with malloc.

On Windows , In order for the heap to keep track of the memory blocks allocated, each block gets few more bytes to hold meta-data of the memory block. this is called "Heap Entry", and it is probably why your blocks are a bit bigger.

but again, you can't assume anything of the blocks - positioning in the heap anyway.

Answer 2

well, even if the memory allocated between calls to calloc() was continuous for you program (which you cannot make sure), don't forget that the lib c has 'private' data stored in the hunk of memory you allocated.

usually there is a header like:

struct hdr
{
  size_t size;                  /* Exact size requested by user.  */
  unsigned long int magic;      /* Magic number to check header integrity.  */
  struct hdr *prev;
  struct hdr *next;
  __ptr_t block;                /* Real block allocated, for memalign.  */
  unsigned long int magic2;     /* Extra, keeps us doubleword aligned.  */
};

(code from)

You may see that the block actually the buffer of data that you'll get when calling malloc()/calloc(), is surrounded by a lot of extra data (ok, here is special case for debug, thus there are probably extra magics).

Answer 3

The errors involved in your code were logic errors related to the various list functions. When you have a create function, that functions job is to allocate memory for the node and assign any values required. It does not worry about which node it is dealing with.

Conversely, your add function does NOT allocate anything, it simply calls create to handle that work and then its job is merely properly wiring pointers and next->pointers to the proper node.

Since you are dealing with a head node that contains data, you have 3 possible conditions for add; (1) when head is NULL; (2) when head->next is NULL; and (3) all remaining additions.

Putting those pieces together and adding a print function, your code could look like the following:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;          //4
    struct Node* next;  //4
} Node;

/* function prototypes */
Node *create (int v);
void add (Node **head, int v);
void del ();
void search (Node *head);
void printvalues (Node *head);

int main (void) {

    Node *head = NULL;
    // head = create(0);
    add (&head,0);
    add (&head,1);
    add (&head,2);
    add (&head,3);
    printf ("\nsearching:\n\n");
    search (head);
    printf ("\nprinting:\n\n");
    printvalues (head);
    return 0;
}

/* create - only creates nodes */
Node *create (int v) 
{
    Node *new;
    new = calloc (1, sizeof *new);
    new->value = v;
    new->next = NULL;
    return new;
}

/* add does NOT create - only handles wiring */
void add (Node **head, int v) 
{
    Node *new = create (v);

    if (!*head) {
        *head = new;
        return;
    }

    Node *p = *head;

    while (p && p->next)
        p = p->next;

    if (!(*head)->next)
        (*head)->next = new;
    else
        p->next = new;
}

void search(Node *head) 
{
    Node *p = head;

    while (p != NULL) {
        printf ("  address is %p;  next address is %p;\n", p, p->next);
        p = p->next;
    }
}

void printvalues (Node *head) 
{
    Node *p = head;
    unsigned cnt = 0;

    while (p != NULL) {
        printf ("  node[%2u] value: %d\n", cnt++, p->value);
        p = p->next;
    }
}

Output

$ ./bin/dbgllmess

searching:

  address is 0x1acf010;  next address is 0x1acf030;
  address is 0x1acf030;  next address is 0x1acf050;
  address is 0x1acf050;  next address is 0x1acf070;
  address is 0x1acf070;  next address is (nil);

printing:

  node[ 0] value: 0
  node[ 1] value: 1
  node[ 2] value: 2
  node[ 3] value: 3

Note: you are responsible for freeing the memory allocated when it is no longer needed. Let me know if you have any questions.

Answer 4

The nodes sizes aren't 16 bytes, it's just that malloc() chooses to skip 8 bytes of memory for some reason, likely for its own bookkeeping. If you want to conserve memory, do few large allocations, not many small ones, or else the bookkeeping overhead can cost quite a lot.