Use malloc to allocate space for multiple elements in a linked list

Ritzy33 0
Viewed 81

I have a struct in C that is similar to this:

struct node{
    char* word;
    struct node* next
}

and for every element I have to allocate dynamic space with malloc, like this:

struct node* new = (struct node*)malloc(sizeof(struct node));
new -> word = (char*)malloc(k*sizeof(char));   //k is an integer variable

but to make the program faster I want to use malloc to allocate, a.e., 50 elements at one time and assign the memory to every element. How can I do that?

struct malloc c
3 Answers

This should do the trick :)

  1. You request the amount of size for one item, times 50. (r2)
  2. The first few bytes are used for the first node structure (r8)
  3. Then, in the for-loop, we add the amount of bytes that the node structure is long to the pointer (r20). Let's say the our allocated memory is on position 100 (for example) in memory. That means that we allocated memory position 100 until 1000 (amusing sizeof(node)==16 and k=2). We simply move up the pointer by 16 and get out new pointer 116.
  4. Now, this pointer '116', we put on member 'word' as as char* pointer. As this word is k times long we add this to our current pointer as well (15)
  5. And so we start over in the loop, until we filled 50 node structures and it's members.

Don't forget you only have to free the first pointer when you want to get rid of this list.

void *mem;
mem = malloc((sizeof(struct node) + (k * sizeof(char))) * 50);

node *firstItem;
node *curIitem;
void *curPos;

firstItem = (struct node*) mem;
curIitem = (struct node*) 0;
curPos = mem;


for (unsigned int i=0; i < 50; i++) {
    if (curIitem != (struct node*) 0) {
        curPos = (void*) ((k * sizeof(char)) + (long long)curPos);
        curIitem->next = (struct node*) curPos;
    }

    curIitem = (struct node*) curPos;
    curPos = (void*)  (sizeof(struct node) + (long long) curPos);
    curIitem->word = (char*) curPos;
}

EDITED: modified the example (since it included some errors) and added an explanation.

Tycho0

Above are some good suggestions. Fleshing out a proof-of-principle method, following is a snippet of code utilizing the method of defining your node chain as a structure array.

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

#define NODESIZE 50

struct node{
    char* word;
    struct node* next;
} arx[NODESIZE];

void setup_links(struct node arr[], int arr_size)
{
    for (int i = 0; i < arr_size - 1; i++)
    {
        arr[i].next = &arr[i + 1];
        arr[i + 1].next = NULL;
    }
}

void print_chain(struct node * head)
{
    struct node * work;
    int i = 0;
    work = head;

    while (work != NULL)
    {
        printf("Node: %d, Address: %p\n", i, work);
        i++;
        work = work->next;
    }
}

int main()
{
    setup_links(arx, NODESIZE);

    printf("Size of node list is: %ld\n", sizeof(arx));
    printf("Beginning address for node is: %p\n", arx);
    print_chain(arx);

    return 0;
}

Here, the "malloc" is implied when allocating enough memory for fifty structures. The additional functions were added to prove out that the memory was allocated. Following, is a sample of the terminal output from running this sample.

@Una:~/C_Programs/Console/NodeArray/bin/Release$ ./NodeArray 
Size of node list is: 800
Beginning address for node is: 0x55ab69ade040
Node: 0, Address: 0x55ab69ade040
Node: 1, Address: 0x55ab69ade050
Node: 2, Address: 0x55ab69ade060
Node: 3, Address: 0x55ab69ade070
Node: 4, Address: 0x55ab69ade080
Node: 5, Address: 0x55ab69ade090
Node: 6, Address: 0x55ab69ade0a0

As noted, this is just one of the ways you might accomplish the one-off allocation of memory for multiple nodes structures. You might try out others to see if performance is better. Give that a try.

NoDakker0

Instead of 2 allocations, consider C's Flexible array member.

  struct node {
    struct node *next;
    char word[];  // Move to end
  };

  size_t k = strlen("123") + 1;
  struct node *new = malloc(sizeof *new + sizeof new->word[0] * k);
  if (new) {
    new->next = NULL;
    strcpy(new->word, "123");
  }

Not quite the 1 allocation instead of 50, but at least 1 allocation instead of 2 and is more C idiomatic.

chux - Reinstate Monica0
Related