realloc returns null

I write the following files to solve question https://code.google.com/codejam/contest/2442487/dashboard#s=p0

In the solution, I use a stack (my first stack implementation in c), however when it dynamically reduce stack size from 64 to 32, the program crashed.

After some debugging, I found that NULL is returned when realloc is called to adjust the buffer size. But I have no idea what is wrong or even how to figure out what is wrong.

Please help OTZ.

Stack.h:

#include<stdlib.h>
#define DECL_STACK_TYPE(type, name) \
typedef struct stack_##name { \
    type * buffer; \
    int size; \
    int top; \
} * name; \
void stack_delete(name s) { \
    free(s->buffer); \
    free(s); \
} \
type stack_peek(name s) { \
    return (s->buffer[s->top]); \
} \
int stack_isEmpty(name s) { \
    return (s->top == -1); \
} \
int stack_isFull(name s) { \
    return (s->top == s->size-1); \
} \
name newStack(int size) { \
    if (size<4) size = 4; \
    name s; \
    s = malloc(sizeof(struct stack_##name)); \
    s->buffer = (type*) malloc(size*sizeof(type)); \
    s->size = size; \
    s->top = -1; \
    return s; \
} \
int stack_push(name s, type item) { \
    type * temp; \
    if (stack_isFull(s)) { \
        temp = (type*) realloc(s->buffer, s->size*2*sizeof(type)); \
        if (!temp) return 0; \
        s->size *= 2; \
    } \
    s->buffer[++s->top] = item;\
    return 1; \
} \
type stack_pop(name s) { \
    type temp; \
    temp = s->buffer[s->top--]; \
    if (s->top * 4 <= s->size && s->size >= 8) { \
        s->size /= 2; \
        type * temp_buffer = s->buffer; \
        s->buffer = (type*) realloc(s->buffer, s->size*sizeof(type)); \
    } \
    return temp; \
}

A.c:

#include<stdio.h>
#include"Stack.h"    

typedef struct {
    int origin;
    int end;
    int count;
} J,*pJ;    

int compare_J(const void * ip1, const void * ip2) {
    pJ p1 = (pJ) ip1;
    pJ p2 = (pJ) ip2;
    if (p1->origin != p2->origin) {
        return (int) (p1->origin-p2->origin);
    } else if (p1->end != p2->end) {
        return (int) p1->end-p2->end;
    } else {
        return (int) p1->count-p2->count;
    }
}    

DECL_STACK_TYPE(J, stack)       

int ticket_cost(int from, int to, int n) {
    int i,ans;
    ans = 0;
    for (i=0;i<to-from;i++) {
        ans += n-i;
    }
    return ans;
}    

int main() {
    freopen("A.in","r",stdin);
    //freopen("A.out","w",stdout);    

    int T,N,M;
    J j[1000],j_temp;
    int i,k,t,ans,index,cur_end,cur_count,iter;

    scanf("%d",&T);
    for (t=1;t<=T;t++) {
        ans = 0;
        scanf("%d %d",&N,&M);
        for (i=0;i<M;i++) {
            scanf("%d %d %d",&(j[i].origin),&(j[i].end),&(j[i].count));
            ans += ticket_cost(j[i].origin, j[i].end, N)*(j[i].count);
        }
        qsort(j,M,sizeof(J),compare_J);
        stack s = newStack(4);
        index = 1;
        stack_push(s,j[0]);
        for (i=0;i<M;i++) {         
            cur_end = j[i].end;
            cur_count = j[i].count;
            while (index<M && j[index].origin<=cur_end) {
                stack_push(s,j[index++]);
            }
            while (cur_count > 0) {
                j_temp = stack_pop(s);
                k = (cur_count<j_temp.count)?cur_count:j_temp.count;
                ans -= ticket_cost(j_temp.origin, cur_end, N)*k;
                cur_count -= k;
                if (j_temp.count > k) {
                    j_temp.count -= k;
                    stack_push(s,j_temp);
                }
            }
        }
        stack_delete(s);
        printf("Case #%d: %d\n",t,ans);
    }
}

Solution

NULL is a reasonable value for realloc to return

realloc will return:

the same location, if it was not moved, but the new size was accommodated
a new block if the data was moved to allow for the new size
NULL if it failed to allocate storage for the new size, and thus the block pointed by ptr was not modified.

In short, you ran out of memory