[SOLVED] (C) How do you store objects on the fly?

vkumar · 2008-10-25 14:34:33

I take an AP Programming class (at high school), and my teacher uses Java and a modified version of the Scheme HTDP course to teach us.
I love Python for its simple effectiveness, and I love C for its power.
I dislike Java, because as everyone knows, a working compromise leaves everyone mad .

That said, I just finished my "space invaders" project in Java. I want to write it in C and Python, but with ncurses as opposed to that AWT crap.
The python isn't really a problem, but...

Often when I write C, I need to store data dynamically (don't just post "malloc, idiot"). In C++, the vector object is great way to do this. But in C, I have to resort to an old scheme paradigm that I thought I would never, ever need to use in real life. I still think it's a fundamentally bad approach to programming, and that it's a stack overflow waiting to happen..

Take a look, and if you can, please give suggestions on how I may modify my "hacked-out" version of an array;

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

typedef unsigned long int num;

struct list {
    num first;
    struct list* rest;
};

void add(struct list* obj, num val)
{
    if (obj->rest == NULL) {
        obj->rest = malloc(sizeof(list));
        obj->rest->first = val;
    } else {
        add(obj->rest, val);
    }
}

void print(struct list* obj)
{
    if (&obj->first != NULL) {
        printf("> %d\n", obj->first);
        print(obj->rest);
    }
}


int main(void)
{
    struct list* tree = malloc(sizeof(list));
    tree->first = 10;

    add(tree, 9);
    add(tree, 8);
    add(tree, 7);

    print(tree);

    free(tree);

    return 0;
}

Notes;
> I use "num" so that there won't be any negative numbers while I deal with ufo/aup positions on the screen.
> "add()" inserts a "num" to the end of the list.
> "print()" prints out the whole list.
> I am not very comfortable using recursion this way. I don't think it's very safe, I just don't know any better...
This is the output this file produces;

> 10
> 9
> 8
> 7

Last thing (I swear). These are sample functions in my actual vadorz.c code;

// ~~~
inline bool hasHit(struct Sprite* obj) {
    return obj->xpos > xi
        && obj->xpos < xa
        && obj->ypos < yi
        && obj->ypos > ya;
}

void shotMove(struct Shot* shot) {
    if (shot == NULL) {
            return;
    }
    if (shot->isGoingUp) {
        if (shot->first->ypos > 1) {
            shot->first->ypos--;
        } else {
            shot->first = NULL;
        }
    } else if (!shot->isGoingUp) {
        if (shot->first->ypos < rows) {
            shot->first->ypos++;
        } else {
            shot->first = NULL;
        }
    }

    if (shot->rest != NULL) {
        shotMove(shot->rest);
    }
}

void shotRun(struct Shot* shot) {
    if (shot->first != NULL) {
        xi = shot->first->xpos - FIELD;
        xa = shot->first->xpos + FIELD;
        yi = shot->first->ypos + FIELD;
        ya = shot->first->ypos - FIELD;

        if (hasHit(ufo)) {
            endGame("You WON the Game!");
        } else if (hasHit(aup)) {
            endGame("Well. You failed.");
        }

        mvprintw(shot->first->ypos, shot->first->xpos, "^");
    }

    if (shot->rest != NULL) {
        shotRun(shot->rest);
    }
}

void addShot(struct Shot* obj, num xpos, bool up) {
    if (obj->first == NULL) {
        obj->first = malloc(4);
        obj->first->xpos = xpos;
        obj->isGoingUp = up;
        if (up) {
            obj->first->ypos = rows - 1;
        } else {
            obj->first->ypos = 2;
        }
    } else {
        addShot(obj->rest, xpos, up);
    }
}
// ~~~

It's buggy as hell , but it compiles without warnings.

Last edited by vkumar (2008-10-25 19:24:50)

ghostHack · 2008-10-25 15:01:48

If its the recursion in add() that you are worried about then you could try something like this

void add(struct list* obj, num val)
{
    struct list * lp;
    lp = obj; 
    /* find the end of the list */
    if ( lp != NULL )
   {
      while ( lp->rest != NULL )
         lp = lp->rest;
    /* now we have the end of the list, get memory for new item */
    lp->rest = (struct list *)malloc(sizeof(list)); 
    /* check we have been given some memory */
    if ( lp->rest == NULL )
       exit(1);
    /* assign value */
    lp->rest->first = val;
   }
}

You could do a similar thing to your print() function.

Last edited by ghostHack (2008-10-25 15:03:47)

vkumar · 2008-10-25 15:10:00

That's great! I'll definitely use that!

But let me explain the scheme beginner list paradigm;

;; A list in Scheme
(define alon (cons (1 (cons 2 (cons 3 (cons 4 (cons 5 (cons 6 (cons 7 (cons 8 (cons 9 (cons 10 empty)))))))))))
(first alon)
;; 1
(rest alon)
;; (cons 2 (cons 3 (cons 4 (cons 5 (cons 6 (cons 7 (cons 8 (cons 9 (cons 10 empty)))))))))
(first (rest (rest alon)))
;; 3

I would like to code something less evil;

alon = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # in python, range(1, 11)
alon[0]
alon[2]

Last edited by vkumar (2008-10-25 15:16:36)

skymt · 2008-10-25 15:12:38

You really need to read a good book on data structures. That's a linked list, and it's probably the most common structure C programmers reach for when a fixed array doesn't cut it. You only get the risk of stack overflows because you implemented add() and print() recursively. Here are iterative implementations (off the top of my head, so they may not work right):

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

typedef unsigned long int num;

struct list {
    /* Use traditional names */
    num first;
    struct list* rest;
};

void add(struct list* obj, num val)
{
    /* Iterate, don't recurse */
    while ( obj->rest != NULL ) {
        obj = obj->rest;
    }
    obj->rest = malloc(sizeof(list));
    if ( obj->rest == NULL )
       exit(1);
    obj->rest->first = val;
}

void print(struct list* obj)
{
    for ( ; obj == NULL; obj = obj->rest )
        printf("> %d\n", obj->first);
}

int main(void)
{
    struct list* tree = malloc(sizeof(list));
    tree->first = 10;

    add(tree, 9);
    add(tree, 8);
    add(tree, 7);

    print(tree);

    free(tree);

    return 0;
}

EDIT: Read this. It should answer any other questions you have.

Last edited by skymt (2008-10-25 15:15:32)

winch · 2008-10-25 15:13:14

Just to be sure, you do know the "old scheme paradigm" data structure is a linked list?
I think a bit of research into linked lists and typical C implementations would be helpful.

vkumar · 2008-10-25 15:33:16

Thanks!
The wikipedia article explains it very well.

@skymt: 404 for the pdf file...

So, if you free the first list here, is all of the memory subsequent lists point to free?
1. list*
2. 1 -> list*
3. 2 -> list*
etc.

skymt · 2008-10-25 15:44:20

vkumar wrote:

@skymt: 404 for the pdf file...

That's strange, it works for me. Here's another mirror.

vkumar wrote:

So, if you free the first list here, is all of the memory subsequent lists point to free?
1. list*
2. 1 -> list*
3. 2 -> list*
etc.

No, you'd need to iterate down the list and free each one. You can trivially write a function to do that for you.

Last edited by skymt (2008-10-25 15:45:22)

pauldonnelly · 2008-10-25 23:07:31

vkumar wrote:

Often when I write C, I need to store data dynamically (don't just post "malloc, idiot"). In C++, the vector object is great way to do this. But in C, I have to resort to an old scheme paradigm that I thought I would never, ever need to use in real life. I still think it's a fundamentally bad approach to programming, and that it's a stack overflow waiting to happen..

What, recursive functions? Those are great, as long as you can be sure you won't overflow your stack, or if your compiler offers tail call optimization (gcc does, if you ask it).

gnud · 2008-10-26 10:36:53

But tail call optimalizations only kick in in specific circumstances, so you would probably have to inspect the assembly to be sure.

What datastructure to use depends on how you use that data structure
A linked list is fine if you insert values at the beginning, and then iterate through them, and if you need to insert values into the middle frequently.
A doubly-linked list speeds up some operations (to O(1) instead of O(n)).
You could also for example have a list header structure, with a pointer to the head and a pointer to the tail.

If you never insert values at the beginning or in the middle of the list, but need fast random access as well as fast sequential access, you could roll your own vector.

//Just the outline:
typedef struct int_vector_s {
  size_t size;
  size_t capacity;
  int* get;
} int_vector_t;

Then calloc some room at the get[] pointer, and create an add() function that realloc()s that memory if needed. Now you can do vector->get[5]; :-)

Arch Linux

#1 2008-10-25 14:34:33

[SOLVED] (C) How do you store objects on the fly?

#2 2008-10-25 15:01:48

Re: [SOLVED] (C) How do you store objects on the fly?

#3 2008-10-25 15:10:00

Re: [SOLVED] (C) How do you store objects on the fly?

#4 2008-10-25 15:12:38

Re: [SOLVED] (C) How do you store objects on the fly?

#5 2008-10-25 15:13:14

Re: [SOLVED] (C) How do you store objects on the fly?

#6 2008-10-25 15:33:16

Re: [SOLVED] (C) How do you store objects on the fly?

#7 2008-10-25 15:44:20

Re: [SOLVED] (C) How do you store objects on the fly?

#8 2008-10-25 23:07:31

Re: [SOLVED] (C) How do you store objects on the fly?

#9 2008-10-26 10:36:53

Re: [SOLVED] (C) How do you store objects on the fly?

Board footer