Programming Forums > Application Development > C

Jessehk · Jun 26th, 2008, 11:42 PM

I have some free time now between high school and University so naturally I'm killing it by playing around with C unnecessarily.

Just for the hell of it, I'm trying to write some code that will allow me duplicate the process of an ADT (like a linked-list or hashtable) using a single block of memory for all its nodes without duplicating code.

This is what I've got in essence, except that in the actual code I'm writing, int's are replaced by nodes.

 c Syntax (Toggle Plain Text) 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    size_t capac;     /* The number of items the container can hold */
    size_t unitsize;  /* The size in bytes of each item */
    size_t index;     /* The current index in the memory block */
    void *mem;        /* The actual memory */
} allocator;
 
/* Create an allocator for a specific ADT. Would be called in make_list or make_htable for example */
allocator *makealloc( size_t capac, size_t unitsize ) {
    allocator *a = malloc( sizeof *a );
 
    a->capac = capac;
    a->unitsize = unitsize;
    a->index = 0;
    a->mem = malloc( capac * unitsize );
 
    return a;
}
 
/* Check that the current memory block will be large enough
 * and double it if necessary
 */
void checkcapac( allocator *a ) {
    void *tmp = NULL;
 
    if ( a->index >= a->capac ) {
        a->capac *= 2;
        tmp = realloc( a->mem, a->unitsize * a->capac );
 
        if ( tmp )
            a->mem = tmp;
    }
}
 
/* I know it's dirty.
 * The idea is to cast the raw memory into a pointer to a block of
 * "type" and then return the address of the nth item.
 * Is this wrong? Illegal, or undefined behavior?
 */
#define ALLOC( a, obj, type ) \
{ \
    checkcapac( a ); \
    obj = &(((type *)(a->mem))[a->index++]); \
}
 
/* Let's practise with int's */
/* The calls to ALLOC would be hidden in library code */
int main( void ) {
    allocator *a = makealloc( 1, sizeof( int ) );
    int *x = NULL;
    int *y = NULL;
 
    /* Should cause checkcapac to double the size of the memory with realloc */
    ALLOC( a, x, int );
    ALLOC( a, y, int );
 
    free( x );
    free( y );
    return 0;
}
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    size_t capac;     /* The number of items the container can hold */
    size_t unitsize;  /* The size in bytes of each item */
    size_t index;     /* The current index in the memory block */
    void *mem;        /* The actual memory */
} allocator;

/* Create an allocator for a specific ADT. Would be called in make_list or make_htable for example */
allocator *makealloc( size_t capac, size_t unitsize ) {
    allocator *a = malloc( sizeof *a );
    
    a->capac = capac;
    a->unitsize = unitsize;
    a->index = 0;
    a->mem = malloc( capac * unitsize );

    return a;
}

/* Check that the current memory block will be large enough
 * and double it if necessary
 */
void checkcapac( allocator *a ) {
    void *tmp = NULL;
    
    if ( a->index >= a->capac ) {
        a->capac *= 2;
        tmp = realloc( a->mem, a->unitsize * a->capac );
        
        if ( tmp )
            a->mem = tmp;
    }
}

/* I know it's dirty.
 * The idea is to cast the raw memory into a pointer to a block of
 * "type" and then return the address of the nth item.
 * Is this wrong? Illegal, or undefined behavior?
 */
#define ALLOC( a, obj, type ) \
{ \
    checkcapac( a ); \
    obj = &(((type *)(a->mem))[a->index++]); \
}

/* Let's practise with int's */
/* The calls to ALLOC would be hidden in library code */
int main( void ) {
    allocator *a = makealloc( 1, sizeof( int ) );
    int *x = NULL;
    int *y = NULL;
    
    /* Should cause checkcapac to double the size of the memory with realloc */
    ALLOC( a, x, int );
    ALLOC( a, y, int );
    
    free( x );
    free( y );
    return 0;
}

The code makes sense to me (and it works when the initial capacity passed is large enough to hold all the elements). I only get memory errors (and a lot of them) with valgrind when checkcapac() has to increase the memory (and thus realloc() has to be called).

Is this clearly stupid code, or am I missing something subtle?

I'd be happy to post more code or info on request.

titaniumdecoy · Jun 27th, 2008, 12:19 AM

Your code makes sense to me, and as far as I can tell it is correct, with two exceptions.

First, you cannot free x and y using free() since you did not allocate the memory for each using malloc(). You have to perform bookkeeping on the block of memory you allocated yourself.

Second, you need to take into account the size of each unit when you are assigning to memory:

(Toggle Plain Text)

#define ALLOC( a, obj, type ) \
{ \
    checkcapac( a ); \
    obj = &(((type *)(a->mem))[a->index++ * a->unitsize]); \
}

There may be other problems with your code but that is all that I can see. Also, you should consider using the memcpy() family of functions provided by the string.h standard library.

I could be completely wrong about some of these points, and if so, hopefully someone will correct me.

The Dark · Jun 27th, 2008, 9:30 AM

After your call to realloc, your original memory area may have been moved (if realloc couldn't extend the original block). If this happened in your second ALLOC call in your main() this would mean that x was now pointing to memory that was no longer allocated.

titaniumdecoy · Jun 27th, 2008, 12:18 PM

@The Dark: I thought the OS would take care of that sort of thing for you. Are you sure x and y wouldn't be automatically "remapped" to point to the new memory block?

grumpy · Jun 27th, 2008, 3:15 PM

Dark is right. If the second usage of ALLOC() reallocates a->mem, then x becomes a dangling pointer to a memory location into the old a->mem (old = corresponding to the value of a->mem held before reallocation). The operating system does not map that pointer.

Jessehk · Jun 28th, 2008, 11:46 AM

Thanks for the replies all of you. Is there an easy to fix this situation?

The first thought I had was that I have to "re-map" the nodes of the data structure on to the new memory block -- but then I would be using malloc() and realloc() would be pointless.

lectricpharaoh · Jun 28th, 2008, 6:03 PM

One thing you might try is instead of using pointers to sub-blocks within the allocated block, use offsets. This way, you will be accessing memory locations relative to the pointer to the start of the large block, and it will be insensitive to whether or not this pointer changes. You will, of course, need to ensure you don't use offsets past the end of the block, but this simply means not accessing more elements than you've allocated space for, which is a given under any circumstances.

Jessehk · Jun 29th, 2008, 9:07 AM

Quote:

Originally Posted by lectricpharaoh

One thing you might try is instead of using pointers to sub-blocks within the allocated block, use offsets. This way, you will be accessing memory locations relative to the pointer to the start of the large block, and it will be insensitive to whether or not this pointer changes. You will, of course, need to ensure you don't use offsets past the end of the block, but this simply means not accessing more elements than you've allocated space for, which is a given under any circumstances.

That sounds interesting. Could you post a quick example with an int or something? I'm having a little difficulty understanding exactly what you mean.

lectricpharaoh · Jun 29th, 2008, 4:30 PM

My C is rather rusty, so the code in this post will be kept to a minimum, but here goes.

If you've ever implemented a linked list using an array, rather than pointers, I'm talking about a similar idea. For a traditional linked list, you might have something like this for a node:

 C Syntax (Toggle Plain Text) 
typedef struct
  {
    item data; // user-defined type here, but can be anything
    node *next;
  } node;
typedef struct
  {
    item data; // user-defined type here, but can be anything
    node *next;
  } node;

This means you need to allocate each node individually, which can lead to awfully poor performance. First, either the OS or the compiler's runtime libraries are probably maintaining records for each allocated block, meaning that each node is going to contain a certain amount of overhead, above and beyond that needed to hold the pointers to next (and previous, for doubly-linked lists) nodes. Second, memory can become quite fragmented, which is terrible for cache performance. This is a strength of traditional linked lists though, as they don't need large amounts of contiguous memory to store large numbers of elements. Still, it is something to bear in mind. Lastly, each call to malloc() and free() can impact performance, depending on the implementation, and how often nodes are added and removed.

Now, let's say you're confident you shouldn't need more than a certain number of nodes in the usual case. We can allocate space for all these nodes at once, and adjust our node structure accordingly:

 C Syntax (Toggle Plain Text) 
typedef struct
  {
    item data;
     int next;
   } node;
    .
    .
    .
node nodeList[SOME_SIZE];
typedef struct
  {
    item data;
     int next;
   } node;
    .
    .
    .
node nodeList[SOME_SIZE];

Here, the next member contains the index of the subsequent node; we can use a specific value to represent the idea that there is no next node (similar to a NULL pointer for the traditional list). Using -1 is probably a safe bet, as is the maximum value for the integer type you're using (as it's highly likely to exceed the number of elements in your array), but you can really use anything you like. As long as it will never be a valid element in your lists, it's all good. Likewise, for the list itself, the head pointer becomes a simple index to the first node.

There is one concern with this approach, though. When allocating nodes, you need to know which ones have already been allocated. You can either walk through the list to determine which nodes are available (slow as hell), or you can maintain a list of which ones are free. This latter solution is probably the best, and considering you only need to mark free/used status, you can use a bool, or even a single bit. If you're not anticipating too many nodes, then in your list itself, you can have an array of bool. If you want a lot of nodes, or simply want to waste as little memory as possible, you can use a block of char, int, etc and perform binary math. Either way, finding a free node will be an O(N) operation, while actually allocating it (or subsequently freeing it) will be O(1). Considering that a similar process will be happening behind the scenes with malloc() as the system walks the heap to find a large enough free block, it's really not the drawback it might seem to be. It does increase the complexity of the implementation a bit, though.

Now, your actual list will need to store the pointer to the allocated block, but this is a single pointer for the entire list, whereas everything else (the head pointer, node next pointers, etc) are all simple index values. If you resize the list to be smaller, you will first have to 'compact' the array by moving elements as close to the start of the array as possible; it will then be trivial to determine the smallest size the array can be set to (you can maintain a 'used node count' to ease this process, if you like, which will allow you to reject invalid shrinking attempts without wasting CPU time). When resizing it larger, nothing special needs to be done, as all the indexes will remain valid.

There are two other advantages I can think of. First, using a large block to hold all your nodes means you can adapt it with relative ease to use file-based storage, as a file can be viewed as a disk-based array. Second, while a linked-list can only be processed sequentially, you can process an array-based list out of order. That is, you can process the elements in the order they're laid out in memory (or on disk), rather than the logical order. If there is some operation that just needs to be applied to all elements, and the order doesn't matter, then this is an advantage. Remember that you are probably tracking the list, and marking free/used nodes, so this is a trivial feature to add. If you need to apply some operation to all elements, and you're using a disk-based implementation, this can greatly speed up the process.

Jessehk · Jun 29th, 2008, 9:12 PM

Thanks for that (very) in-depth reply. It looks like something I can have fun with over the next few days (do I need a new hobby?

).

Jun 26th, 2008, 11:42 PM	#1
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 644 Rep Power: 4	Errors with realloc() w.r.t. managing shared memory I have some free time now between high school and University so naturally I'm killing it by playing around with C unnecessarily. Just for the hell of it, I'm trying to write some code that will allow me duplicate the process of an ADT (like a linked-list or hashtable) using a single block of memory for all its nodes without duplicating code. This is what I've got in essence, except that in the actual code I'm writing, int's are replaced by nodes. c Syntax (Toggle Plain Text) #include <stdio.h> #include <stdlib.h> typedef struct { size_t capac; /* The number of items the container can hold / size_t unitsize; / The size in bytes of each item / size_t index; / The current index in the memory block / void mem; /* The actual memory / } allocator; / Create an allocator for a specific ADT. Would be called in make_list or make_htable for example / allocator makealloc( size_t capac, size_t unitsize ) { allocator a = malloc( sizeof a ); a->capac = capac; a->unitsize = unitsize; a->index = 0; a->mem = malloc( capac * unitsize ); return a; } /* Check that the current memory block will be large enough * and double it if necessary / void checkcapac( allocator a ) { void tmp = NULL; if ( a->index >= a->capac ) { a->capac = 2; tmp = realloc( a->mem, a->unitsize * a->capac ); if ( tmp ) a->mem = tmp; } } /* I know it's dirty. * The idea is to cast the raw memory into a pointer to a block of * "type" and then return the address of the nth item. * Is this wrong? Illegal, or undefined behavior? / #define ALLOC( a, obj, type ) \ { \ checkcapac( a ); \ obj = &(((type )(a->mem))[a->index++]); \ } /* Let's practise with int's / / The calls to ALLOC would be hidden in library code / int main( void ) { allocator a = makealloc( 1, sizeof( int ) ); int x = NULL; int y = NULL; /* Should cause checkcapac to double the size of the memory with realloc / ALLOC( a, x, int ); ALLOC( a, y, int ); free( x ); free( y ); return 0; } #include <stdio.h> #include <stdlib.h> typedef struct { size_t capac; / The number of items the container can hold / size_t unitsize; / The size in bytes of each item / size_t index; / The current index in the memory block / void mem; /* The actual memory / } allocator; / Create an allocator for a specific ADT. Would be called in make_list or make_htable for example / allocator makealloc( size_t capac, size_t unitsize ) { allocator a = malloc( sizeof a ); a->capac = capac; a->unitsize = unitsize; a->index = 0; a->mem = malloc( capac * unitsize ); return a; } /* Check that the current memory block will be large enough * and double it if necessary / void checkcapac( allocator a ) { void tmp = NULL; if ( a->index >= a->capac ) { a->capac = 2; tmp = realloc( a->mem, a->unitsize * a->capac ); if ( tmp ) a->mem = tmp; } } /* I know it's dirty. * The idea is to cast the raw memory into a pointer to a block of * "type" and then return the address of the nth item. * Is this wrong? Illegal, or undefined behavior? / #define ALLOC( a, obj, type ) \ { \ checkcapac( a ); \ obj = &(((type )(a->mem))[a->index++]); \ } /* Let's practise with int's / / The calls to ALLOC would be hidden in library code / int main( void ) { allocator a = makealloc( 1, sizeof( int ) ); int x = NULL; int y = NULL; /* Should cause checkcapac to double the size of the memory with realloc */ ALLOC( a, x, int ); ALLOC( a, y, int ); free( x ); free( y ); return 0; } The code makes sense to me (and it works when the initial capacity passed is large enough to hold all the elements). I only get memory errors (and a lot of them) with valgrind when checkcapac() has to increase the memory (and thus realloc() has to be called). Is this clearly stupid code, or am I missing something subtle? I'd be happy to post more code or info on request. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Jun 27th, 2008, 12:19 AM	#2
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 856 Rep Power: 3	Re: Errors with realloc() w.r.t. writing managing shared memory Your code makes sense to me, and as far as I can tell it is correct, with two exceptions. First, you cannot free x and y using free() since you did not allocate the memory for each using malloc(). You have to perform bookkeeping on the block of memory you allocated yourself. Second, you need to take into account the size of each unit when you are assigning to memory: (Toggle Plain Text) #define ALLOC( a, obj, type ) \ { \ checkcapac( a ); \ obj = &(((type )(a->mem))[a->index++ a->unitsize]); \ } #define ALLOC( a, obj, type ) \ { \ checkcapac( a ); \ obj = &(((type )(a->mem))[a->index++ a->unitsize]); \ } There may be other problems with your code but that is all that I can see. Also, you should consider using the memcpy() family of functions provided by the string.h standard library. I could be completely wrong about some of these points, and if so, hopefully someone will correct me. Last edited by titaniumdecoy; Jun 27th, 2008 at 12:47 AM.

Jun 27th, 2008, 9:30 AM	#3
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	Re: Errors with realloc() w.r.t. writing managing shared memory After your call to realloc, your original memory area may have been moved (if realloc couldn't extend the original block). If this happened in your second ALLOC call in your main() this would mean that x was now pointing to memory that was no longer allocated.

Jun 27th, 2008, 12:18 PM	#4
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 856 Rep Power: 3	Re: Errors with realloc() w.r.t. writing managing shared memory @The Dark: I thought the OS would take care of that sort of thing for you. Are you sure x and y wouldn't be automatically "remapped" to point to the new memory block?

Jun 27th, 2008, 3:15 PM	#5
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,223 Rep Power: 5	Re: Errors with realloc() w.r.t. writing managing shared memory Dark is right. If the second usage of ALLOC() reallocates a->mem, then x becomes a dangling pointer to a memory location into the old a->mem (old = corresponding to the value of a->mem held before reallocation). The operating system does not map that pointer.

Jun 28th, 2008, 11:46 AM	#6
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 644 Rep Power: 4	Re: Errors with realloc() w.r.t. writing managing shared memory Thanks for the replies all of you. Is there an easy to fix this situation? The first thought I had was that I have to "re-map" the nodes of the data structure on to the new memory block -- but then I would be using `malloc()` and `realloc()` would be pointless. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Jun 28th, 2008, 6:03 PM	#7
lectricpharaoh Caffeinated Neural Net Join Date: Jun 2005 Location: Dry west coast of Canada Posts: 1,039 Rep Power: 5	Re: Errors with realloc() w.r.t. writing managing shared memory One thing you might try is instead of using pointers to sub-blocks within the allocated block, use offsets. This way, you will be accessing memory locations relative to the pointer to the start of the large block, and it will be insensitive to whether or not this pointer changes. You will, of course, need to ensure you don't use offsets past the end of the block, but this simply means not accessing more elements than you've allocated space for, which is a given under any circumstances. __________________ And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot. - Vaarsuvius, Order of the Stick

Jun 29th, 2008, 4:30 PM	#9
lectricpharaoh Caffeinated Neural Net Join Date: Jun 2005 Location: Dry west coast of Canada Posts: 1,039 Rep Power: 5	Re: Errors with realloc() w.r.t. writing managing shared memory My C is rather rusty, so the code in this post will be kept to a minimum, but here goes. If you've ever implemented a linked list using an array, rather than pointers, I'm talking about a similar idea. For a traditional linked list, you might have something like this for a node: C Syntax (Toggle Plain Text) typedef struct { item data; // user-defined type here, but can be anything node next; } node; typedef struct { item data; // user-defined type here, but can be anything node next; } node; This means you need to allocate each node individually, which can lead to awfully poor performance. First, either the OS or the compiler's runtime libraries are probably maintaining records for each allocated block, meaning that each node is going to contain a certain amount of overhead, above and beyond that needed to hold the pointers to next (and previous, for doubly-linked lists) nodes. Second, memory can become quite fragmented, which is terrible for cache performance. This is a strength of traditional linked lists though, as they don't need large amounts of contiguous memory to store large numbers of elements. Still, it is something to bear in mind. Lastly, each call to `malloc()` and `free()` can impact performance, depending on the implementation, and how often nodes are added and removed. Now, let's say you're confident you shouldn't need more than a certain number of nodes in the usual case. We can allocate space for all these nodes at once, and adjust our node structure accordingly: C Syntax (Toggle Plain Text) typedef struct { item data; int next; } node; . . . node nodeList[SOME_SIZE]; typedef struct { item data; int next; } node; . . . node nodeList[SOME_SIZE]; Here, the next member contains the index of the subsequent node; we can use a specific value to represent the idea that there is no next node (similar to a `NULL` pointer for the traditional list). Using -1 is probably a safe bet, as is the maximum value for the integer type you're using (as it's highly likely to exceed the number of elements in your array), but you can really use anything you like. As long as it will never be a valid element in your lists, it's all good. Likewise, for the list itself, the head pointer becomes a simple index to the first node. There is one concern with this approach, though. When allocating nodes, you need to know which ones have already been allocated. You can either walk through the list to determine which nodes are available (slow as hell), or you can maintain a list of which ones are free. This latter solution is probably the best, and considering you only need to mark free/used status, you can use a `bool`, or even a single bit. If you're not anticipating too many nodes, then in your list itself, you can have an array of `bool`. If you want a lot of nodes, or simply want to waste as little memory as possible, you can use a block of `char`, `int`, etc and perform binary math. Either way, finding a free node will be an O(N) operation, while actually allocating it (or subsequently freeing it) will be O(1). Considering that a similar process will be happening behind the scenes with `malloc()` as the system walks the heap to find a large enough free block, it's really not the drawback it might seem to be. It does increase the complexity of the implementation a bit, though. Now, your actual list will need to store the pointer to the allocated block, but this is a single pointer for the entire list, whereas everything else (the head pointer, node next pointers, etc) are all simple index values. If you resize the list to be smaller, you will first have to 'compact' the array by moving elements as close to the start of the array as possible; it will then be trivial to determine the smallest size the array can be set to (you can maintain a 'used node count' to ease this process, if you like, which will allow you to reject invalid shrinking attempts without wasting CPU time). When resizing it larger, nothing special needs to be done, as all the indexes will remain valid. There are two other advantages I can think of. First, using a large block to hold all your nodes means you can adapt it with relative ease to use file-based storage, as a file can be viewed as a disk-based array. Second, while a linked-list can only be processed sequentially, you can process an array-based list out of order. That is, you can process the elements in the order they're laid out in memory (or on disk), rather than the logical order. If there is some operation that just needs to be applied to all elements, and the order doesn't matter, then this is an advantage. Remember that you are probably tracking the list, and marking free/used nodes, so this is a trivial feature to add. If you need to apply some operation to all elements, and you're using a disk-based implementation, this can greatly speed up the process. __________________ And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot. - Vaarsuvius, Order of the Stick

Jun 29th, 2008, 9:12 PM	#10
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 644 Rep Power: 4	Re: Errors with realloc() w.r.t. writing managing shared memory Thanks for that (very) in-depth reply. It looks like something I can have fun with over the next few days (do I need a new hobby? ). __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
structure with an array in shared memory	SAWG	C	1	Apr 28th, 2008 12:24 AM
queue - shared memory	programmingnoob	C++	4	Mar 26th, 2007 8:19 PM
Difficulties with memory leaks and the STL + boost	Jessehk	C++	5	Nov 26th, 2006 12:17 PM
Heap vs. Stack memory	Eric the Red	C++	11	Oct 24th, 2006 6:18 PM
Very annoying errors	Aphex_Twin	C++	2	Jun 9th, 2005 3:43 PM

Programming Forums > Application Development > C

Errors with realloc() w.r.t. writing managing shared memory