supplement

Malloc: Allocates a specified number of bytes to the storage area. The initial value of the storage area is uncertain

  • Malloc returns memory with byte alignment that is always suitable for efficient access to any type of C data structure. On most schemas, this means that malloc allocates memory based on 8-byte or 16-byte boundaries.

  • Malloc (0) either returns NULL, which is a chunk of memory that can (and should) be freed by free

Realloc: Increases or decreases the length of a previous allocation

  • When you increase the length, you may need to move the contents of the previously allocated area to another area large enough to provide the added storage at the end, and the initial value of the new area is uncertain

  • Before and after the function call may be different storage area, so the call should not have a pointer to this storage area, otherwise after the change, the pointer may be illegal access

  • You should use another pointer to hold the return value of RealLoc, because if you use the passed argument to hold the return value, then if realLoc fails, NULL is returned and the original dynamic memory area is no longer accessible, resulting in a memory leak

These two functions return values: on success, a non-null pointer; Error, return NULL

Int stack

stack.h

typedef struct {
    int *elems;
    int logLength;
    int allocLength;
} stack;

void StackNew(stack *s);
void StackDispose(stack *s);
void StackPush(stack *s, int value);
void StackPop(stack *s);
Copy the code

stack.c

void StackNew(stack *s)
{
    s->allocLength = 4;
    s->logLength = 0;
    s->elems = malloc(4 * sizeof(int)); assert(s->elems ! =NULL);
}

void StackDispose(stack *s) 
{
    free(s->elems);
}

void StackPush(stack *s, int value)
{
    if(s->logLength == s->allocLength) 
    {
        s->allocLength *= 2;
        s->elems = realloc(s->elems, s->allocLength * sizeof(int)); assert(s->elems ! =NULL);
    }
    
    s->elems[s->logLength] = value;
    s->logLength++;
}

void StackPop(stack *s) 
{
    assert(s->logLength > 0);
    s->logLength--;
    return s->elems[s->logLength];
}
Copy the code

Generic type stack

stack.h

typedef struct {
    void *elems;
    int elemSize;
    int logLength;
    int allocLength;
} stack;

void StackNew(stack *s, int elemSize);
void StackDispose(stack *s);
void StackPush(stack *s, void *elemValue);
void StackPop(stack *s, void *elemValue);
Copy the code

In the generic type implementation, we usually use void* to replace the data type, but this prevents us from performing pointer operations and losing information about the size of the data type. So we have to add something extra.

stack.c

void StackNew(stack *s, int elemSize)
{
    assert(elemSize > 0);
    s->logLength = 0;
    s->allocLength = 4;
    s->elemSize = elemSize;
    s->elems = malloc(4* s->elemSize); assert(s->elems ! =NULL);
}

void StackDispose(stack *s)
{
    free(s->elems);
}

void StackPush(stack *s, void *elemValue)
{
    if(s->logLength == s->allocLength)
    {
        s->allocLength *= 2;
        s->elems = realloc(s->elems, s->allocLength * s->elemSize); assert(s->elems ! =NULL);
    }
    
    void *source = (char*)s->elems + s->logLength * s->elemSize;
    memcpy(source, elemValue, s->elemSize);
    s->logLength++;
}

void StackPop(stack *s, void *elemValue)
{
    assert(s->logLength > 0);
    void *source = (char*)s->elems + (s->logLength - 1) * s->elemSize;
    memcpy(elemValue, source, s->elemSize);
    s->logLength--;
}
Copy the code

Why not return void* in a StackPop function?

To return void*, the data storage must be dynamically allocated, but to do so is to hand over the release requirement to the user, which is not good for maintenance and can cause problems. In general, the dynamic allocation and release of memory are symmetric. We allocate dynamically in the function, and we also need to free.

Pay attention to

  • In C, declaring a function as static means that the function can only be used in this file and cannot be referenced by other files. This approach is called internal linking.

  • In the process of dynamic memory allocation, it is easy to overlook the need to multiply by elemSize.

  • Void * is error-prone during processing, so be careful.