gbadev.org forum archive

Hello everyone! While this may not be GBA specific, I hope that I can receive some help.

My problem is that I want to be able to create a system where I can easily insert and display a lot of sprites on the screen without having to actually specify where in memory they should be placed. For example,

Code:

sprite_mem[0].x = 1;
sprite_mem[0].y = 1;

I want to be able to "spawn" hundreds of sprites and be able to individually move them.

So far, the following code works is able to create a lot of sprites on screen. The only problem is that I have no idea how to be able to move each sprite separately.

Here is the code:

Code:

unsigned short
AddPolygonToList(struct vdp1_sort_node *db)
{
unsigned short n;

for (n = 0; n < max_size; n++) {
   if (((index + 1) < max_size) && (db[index].id == 0)) {
      index++;
      db[index - 1].id = index - 1;

      if (removed_nodes > 0)
         removed_nodes--;
      break;
   }
   /* Else, the size has exceeded the maximum amount of nodes. */
}

return index - 1;
}

void
DrawPolygon(struct vdp1_sort_node *db, struct mth_vertex vert[4], unsigned short color, unsigned char mesh, unsigned long color_calc)
{
struct vdp1_cmd_table *table;
unsigned short    id;

/*
* Get the "ID." This will simply set the address as to where this
* sprite will be placed in memory.
*/

id = AddPolygonToList(db);

table = GetTableAddress(id);

table->control = 0x4;
table->mode = 0xc0 | (mesh << 8) | (color_calc & 0x7);
table->link = 0;
table->color = color;
table->character_base = 0;
table->size = 0;
table->xa = vert[0].x;
table->ya = vert[0].y;
table->xb = vert[1].x;
table->yb = vert[1].y;
table->xc = vert[2].x;
table->yc = vert[2].y;
table->xd = vert[3].x;
table->yd = vert[3].y;
table->gouraud_base = color_calc >> 16;
table->dummy = id;
}

Here is an example as to how to display two sprites and move them both.

Code:

/* This function pretty much sets the max_size global variable. */
yl_vdp1_cmd_init_list(&db, 10);

while (1) {
   Vblank();

   yl_vdp1_cmd_init_list(&db, 10);

   vert[0].x++;
   vert[1].x++;
   vert[2].x++;
   vert[3].x++;

   DrawPolygon(db, vert, yl_video_rgb_555( 0, 0, 31), 0, 0);
   DrawPolygon(db, vert, yl_video_rgb_555( 0, 0, 31), 0, 0);

   DestroyList();
}

_________________
http://mrkotfw.ribrdb.com/

Last edited by Piratero on Sat Mar 31, 2007 8:22 pm; edited 1 time in total

Polygons? Sort nodes? yl_vdp1_cmd_polygon? What?

Try a simpler example, written in a style that's meant for communication with other people. If you have a function that adds a polygon to a list, how about naming it addPolygonToList?

BTW, a polygon is not a sprite.

sajiimori wrote:

Polygons? Sort nodes? yl_vdp1_cmd_polygon? What?

Try a simpler example, written in a style that's meant for communication with other people. If you have a function that adds a polygon to a list, how about naming it addPolygonToList?

BTW, a polygon is not a sprite.

The VDP1 is a video processor for another console. The idea with "OAM" entries is the same.

The function "yl_vdp1_cmd_add_table" adds a value onto the "db" list. The Polygon function "yl_vdp1_cmd_polygon" pretty much sets up a function and receives the value from "yl_vdp1_cmd_add_table."

I can certainly rewrite the code for a different or better solution to my problem. Any ideas?

By the way, I said sprite because there are other types of "command tables." I chose to display polygons first because they're the easiest to set up and see on the screen.

Thanks!
_________________
http://mrkotfw.ribrdb.com/

He is just saying that you have an irregular naming scheme that makes it very difficult to be able to make sense of some lines without looking at the code of the function and figuring it out from there. That is never a good thing; if a method adds polygons, call it addPolygon.

keldon wrote:

He is just saying that you have an irregular naming scheme that makes it very difficult to be able to make sense of some lines without looking at the code of the function and figuring it out from there. That is never a good thing; if a method adds polygons, call it addPolygon.

Gotcha. I'll be renaming them.

Edit: Are there any alternatives to what I need to do?
_________________
http://mrkotfw.ribrdb.com/

It sounds like all you want is a container.

Code:

std::vector<Sprite> spriteList;
spriteList.push_back(oneSprite);
spriteList.push_back(anotherSprite);

...or a hand-written equivalent if you don't want to use C++.

sajiimori wrote:

It sounds like all you want is a container.

Code:

std::vector<Sprite> spriteList;
spriteList.push_back(oneSprite);
spriteList.push_back(anotherSprite);

...or a hand-written equivalent if you don't want to use C++.

I'll try to write myself a "container." What exactly do you mean by push_back?
_________________
http://mrkotfw.ribrdb.com/

http://www.google.com/search?&q=push%5fback

sajiimori wrote:

http://www.google.com/search?&q=push%5fback

I see, that makes sense.
_________________
http://mrkotfw.ribrdb.com/

Is there any information out on the web on the container algorithm? I haven't found much other than links explaining how to use a container...
_________________
http://mrkotfw.ribrdb.com/

There are two types of containers; ordered and unordered. Lists, queues, arrays, and vectors are ordered whereas sets, bags and maps are not ordered. The container sajimori was talking about was a list type. Different methods are used depending on your choice of implementation. You could use arrays, linked lists or doubly linked lists to store your data; but I really think you should read up a little on this aswell. It is very late right now (over here) but someone should be able to give you some links if you need them.

In fact http://en.wikipedia.org/wiki/Standard_Template_Library#Containers

You have different operations for different types of containers. For lists you would make use of:
- get( elementNumber )
- getSize ()
- add ( element )
- insert ( element, position )
- remove (position)
- remove ( element )
- addAll ( container )
- removeAll ( container )
- retainAll ( container ) // remove everything in this list apart from those in the passed container

With sets you would generally have:
- add ( element )
- remove ( element )
- getIterator ()
- addAll ( container )
- removeAll ( container )
- retainAll ( container ) // remove everything in this list apart from those in the passed container

Thank You!! That list is very useful.

Edit: I forgot to mention that I don't plan on using malloc/free to allocate memory as the "container" will have a fixed size of 2,048 entries.
_________________
http://mrkotfw.ribrdb.com/

When you have a fixed-size buffer, one easy solution is to run a linked list through it.

Code:

struct Link
{
Link* next;
Object object;
};

Link pool[NUM_LINKS];
Link* firstFree;

void init()
{
for(int i = 0; i < NUM_LINKS - 1; ++i)
pool[i].next = &pool[i + 1];

firstFree = &pool[0];
}

Object* alloc()
{
assert(firstFree != 0);
Object* result = firstFree;
firstFree = firstFree->next;
}

I'll leave the free() function as an exercise.

So the "free" function from that snip of code you pasted should point have the previous node point to the next node? In this case, would setting the "freed" node to zero be good enough or just simply have it point to the next node?

A very different approach:

Code:

#include <stdio.h>

#define MAX_ELEMENTS 2048

typedef struct cmd_table_t {
unsigned short control;
unsigned short link;
unsigned short mode;
unsigned short color;
unsigned short character_base;
unsigned short size;
signed short xa;
signed short ya;
signed short xb;
signed short yb;
signed short xc;
signed short yc;
signed short xd;
signed short yd;
unsigned short gouraud_base;
unsigned short dummy;
} element_t;

typedef struct container_t {
element_t elements[MAX_ELEMENTS];
} container_t;

static int container_size = 0;

int
empty(element_t element)
{
if (element.control == 0xffff)
   return 1;
else
   return 0;
}

element_t
get(container_t container, int element_number)
{

return container.elements[element_number];
}

int
get_size(container_t container)
{

return (sizeof(container) >> 5) - container_size;
}

void
house_cleaning(container_t *container)
{
int n;

for (n = 0; n < get_size(*container); n++) {
   container->elements[n].control = 0xffff;
   container->elements[n].link = 0xffff;
   container->elements[n].mode = 0xffff;
   container->elements[n].color = 0xffff;
   container->elements[n].character_base = 0xffff;
   container->elements[n].size = 0xffff;
   container->elements[n].xa = 0xffff;
   container->elements[n].ya = 0xffff;
   container->elements[n].xb = 0xffff;
   container->elements[n].yb = 0xffff;
   container->elements[n].xc = 0xffff;
   container->elements[n].yc = 0xffff;
   container->elements[n].xd = 0xffff;
   container->elements[n].yd = 0xffff;
   container->elements[n].gouraud_base = 0xffff;
   container->elements[n].dummy = 0xffff;
}
}

void
add(element_t element)
{
}

void
insert(container_t *container, element_t element, int position)
{
if (position < get_size(*container)) {
   if (empty(container->elements[position])) {
      printf("inserting into position: %d\n", position);
      container->elements[position] = element;
      container_size++;
   } else {
      printf("position %d is used\n", position);
   }
} else
   printf("reached the total amount of elements, use remove_all()\n");
}

void
remove_pos(int position)
{
}

void
remove_element(element_t element)
{
}

void
add_all(container_t container)
{
}

void
remove_all(container_t container)
{
}

element_t
add_polygon(unsigned short color)
{
element_t write;

write.control = 0;
write.color = color;

return write;
}

int
main(void)
{
container_t container;
element_t element;

/* Ignore this! */
house_cleaning(&container);

element = add_polygon(0x801f);

insert(&container, element, 0);
insert(&container, element, 1);
insert(&container, element, 2);

return 0;
}

_________________
http://mrkotfw.ribrdb.com/

Assorted exercises:

In my example, if you called alloc() exactly NUM_LINKS times, what would be the value of firstFree?

What would happen if you called alloc() one more time after that?

The goal of the free() function is to take an Object* that was previously returned by alloc() and make it available to alloc() again.

What are the advantages of your approach and my approach? How would you decide which one to use?

Pass large structures (larger than an int) by reference, not by value. Passing by value causes them to be copied.

Make a clearer definition of a container's "size". You have two different concepts that are both named size: the container_size variable, and the get_size(container_t) function.

get_size is fairly magical. How does shifting right by 5 have to do with the size of a container?

Why is 'container_size' global when 'container' is local?

Remember that you can use array indices instead of pointers:

Code:

#define MAX_NODES 20 // whatever makes sense
#define NO_FREE_NODE -1
#define FREE_NODE 1
#define USED_NODE 0

typedef struct node_t
{
data_t data; // This node's data.
int prev;    // The index of the previous node.
int next;    // The index of the next node.
int free;    // Is this node free, or in use?
} node_t;

node_t myLinkedList[MAX_NODES];

int getFreeNode(node_t *pLinkedList, int pSize)
{
int i;

for (i = 0; i < pSize; i++)
   if (FREE_NODE == pLinkedList->free)
      return i;
// else
   return NO_FREE_NODE;
}

node_t *getNode(node_t *pLinkedList, int pNodeId)
{
return &(pLinkedList[pNodeId]);
}

void insertAfterNode(node_t *pLinkedList, int pSize, int pLocation, int pNodeId)
{
node_t *prevNode = getNode(pLinkedList, pLocation);
node_t *nextNode = getNode(pLinkedList, prevNode->next);
node_t *insertNode = getNode(pLinkedList, pNodeId);

// link the new node to old nodes
insertNode->prev = pLocation;
insertNode->next = prevNode->next;

// mark new node as not free
insertNode->free = USED_NODE;

// link old nodes to new node
prevNode->next = pNodeId;
nextNode->prev = pNodeId;
}

void deleteNode(node_t *pLinkedList, int pSize, int pNodeId)
{
node_t *targetNode = getNode(pLinkedList, pNodeId);
node_t *prevNode = getNode(pLinkedList, targetNode->prev);
node_t *nextNode = getNode(pLinkedList, targetNode->next);

// link old nodes to new node
prevNode->next = targetNode->next;
nextNode->prev = targetNode->prev;

// mark target node as free
targetNode->free = FREE_NODE;
}

There is probably a clearer way to write all of this.

You could even pull the struct apart and have an array of data and an array of links. This way the link struct could be used with any kind of data:

Code:

#define MAX_DATA 32

typedef struct link_t
{
int prev;
int next;
int free;
} link_t;

data_t data[MAX_DATA]; // <- data lives here
link_t myLinkedList[MAX_DATA]; // same number of links, one for each data member

-Brendan

sgeos, thanks for the code, I'm looking at it now.

sajiimori wrote:

Assorted exercises:

In my example, if you called alloc() exactly NUM_LINKS times, what would be the value of firstFree?

0

sajiimori wrote:

What would happen if you called alloc() one more time after that?

Segmentation Fault.

sajiimori wrote:

The goal of the free() function is to take an Object* that was previously returned by alloc() and make it available to alloc() again.

What are the advantages of your approach and my approach? How would you decide which one to use?

sajiimori wrote:

Pass large structures (larger than an int) by reference, not by value. Passing by value causes them to be copied.

Make a clearer definition of a container's "size". You have two different concepts that are both named size: the container_size variable, and the get_size(container_t) function.

get_size is fairly magical. How does shifting right by 5 have to do with the size of a container?

I'll fix that, thanks. The code did change so I did fix that. The get_size() has changed. I'll post the new code.

sajiimori wrote:

Why is 'container_size' global when 'container' is local?

Good question. I guess you can say that container is allocated and container_size keeps track of the amount of objects i have inserted.
container_size will probably give me trouble when I want to remove anything.

Here is the new code

Code:

#include <vdp1.h>

static unsigned short container_size = 0, current_pos = 0, max_size = 0;

static __inline__ unsigned char
element_empty(struct vdp1_cmd_table command_table)
{

return ((command_table.cmdctrl != 0xffff) ? 0 : 1);
}

void
add_element(struct container *container, struct vdp1_cmd_table command_table)
{
if (current_pos < (max_size - get_size())) {
   if (_container_element_empty(container[current_pos].command_table))
      container_size++;

   container[current_pos].command_table = command_table;
}

current_pos++;
}

void
draw_objects(struct container *container)
{
struct vdp1_cmd_table *table;
unsigned short    dma_mode;
unsigned short    n;

dma_mode = (1 << 14) | (1 << 12) | (1 << 11) | (1 << 9) | (1 << 3) | (1 << 0);
table = (struct vdp1_cmd_table *)VDP1_CMD_TABLE_BASE;

/* Copy the entire list. */
for (n = 0; n < container_size; n++)
   sh2_dmac_ch0(&table[n], &container[n].command_table, 8, dma_mode);
}

struct vdp1_cmd_table
get_element(struct container *container, unsigned short pos)
{
if (pos < (max_size - get_size()))
   return container[pos].command_table;

return container->command_table;
}

unsigned short
get_size(void)
{
return ((container_size < max_size) ? container_size : 0);
}

void
init_list(struct container **container, unsigned long max)
{
unsigned short n;

*container = (struct container *)0x2020000;
max_size = VDP1_MAX_CMD_TABLES;

for (n = 0; n < (max_size - get_size()); n++) {
   container[n]->next = &container[0][n + 1];

   yl_vdp1_cmd_disable(&container[0][n].command_table);
}
}

void
insert_element(struct container *container, struct vdp1_cmd_table command_table, unsigned short pos)
{
if (pos < (max_size - get_size())) {
   if (element_empty(container[pos].command_table))
      container_size++;

   container[pos].command_table = command_table;
}
}

_________________
http://mrkotfw.ribrdb.com/

Depending on how you want to use the nodes you could have a link list of free nodes and the link list of "used" nodes so when you want a free node you just grad the first node in the list. This just means when you "de-allocate" a node you need to insert it into the free list. This is generally the approach I take for static or controlled allocation.

You could also use the concept of an allocation table (like what FAT disks use) where you have one bit for each possible node and you turn the bit off if its free and turn the bit on if it is not.

There are lots of approaches to you could use, you just have to find one that fits you knowledge and overall design the best.

gmiller wrote:

Depending on how you want to use the nodes you could have a link list of free nodes and the link list of "used" nodes so when you want a free node you just grad the first node in the list. This just means when you "de-allocate" a node you need to insert it into the free list. This is generally the approach I take for static or controlled allocation.

You could also use the concept of an allocation table (like what FAT disks use) where you have one bit for each possible node and you turn the bit off if its free and turn the bit on if it is not.

There are lots of approaches to you could use, you just have to find one that fits you knowledge and overall design the best.

Thanks for the ideas. This seems like a good idea because if I were to want to insert a free node, I'd have to search for one. This way, I know that I can just simply fetch one and insert.
_________________
http://mrkotfw.ribrdb.com/

here is an example of the FAT method without the list list code. I use this in the class I teach (Machine Architecture).

NOTE:: Of course this code is just testing the implementation of the function so the main code does not really do much other than test over allocation, under allocation, empty and fully allocated. also this was implemented in C not C++ using malloc and free not new and delete. I like the free and used link lists better for small sets.

Code:

/*

test

Use bit map to track sprite allocation. The sprite data is
allocated in an array and tracked using a bit map. A one
on in the bit map shows that the sprite is in use. A zero
on indicates that the sprite data is free and not in use.

*/

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

#define DEBUG 1
#define TRACE 1

static char const ident[] =
"$Id: msprite.c,v 1.3 2005/09/27 20:28:57 gmiller Exp gmiller $";

#include "debug.h"

const int SHIFT_SIZE[17] =
{ 0, 3, 4, 0, 5, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 7 };

// macros

#define ELEMENT_BITS ((sizeof(int)*8))
#define ELEMENT_MASK (ELEMENT_BITS - 1)
#define ELEMENT_SHIFT (SHIFT_SIZE[sizeof(int)])
#define ALL_ELEMENTS_USED (~0)

//
/*
sample line:
// increment variable. (WHAT not HOW)
fubar_variable = - (~fubar_valiable);

*/

typedef enum
{ NO_ERROR = 0,
BAD_SPRITE_PTR = -1,
BAD_SPRITE_NO = -2,
BAD_SPRITE_IS_FREE = -3,
BAD_SPRITE_IS_USED = -4,
BAD_SPRITE_ALL_USED = -5,
BAD_ALL_SPRITES_FREE = -6
} sprite_error;

typedef struct _sprites_
{
int x; // Current Sprite location x,y
int y;
int rows, cols; // Size of Sprite Row x Col
char *elements; // Data to display (size is Row x Col)
int life_value; // Life force
int sprite_number; // Sprite number in set, zero based
} sprite;

typedef struct _allocation_data_
{
int number_of_elements; // number of possible sprites
int first_free; // first element with free bit
int shift_amt; // shift for entry index
int bit_mask; // mask to isolate bit number
int max_entry; // maximum entry in array of bits
int *bit_table; // bits for each possible sprite
int free_cnt; // number of free sprites
int used_cnt; // number of used sprites
} allocation_data;

typedef struct _sprite_tbl_
{
allocation_data salloc; // allocation data
sprite *sprites; // sprite data
} sprite_tbl;

/*

Allocate space to manage a group of "number_of_sprites"
using the defined structures. Allocate space, initalize
memory and return pointer. Return != NULL if no error otherwise
return NULL

Sample usage:

sprite_tbl tbl_ptr;

tbl_ptr = allocate_sprite_table( 1024 );
if ( tbl_ptr == NULL ) {
printf("Table allocation failed.\n");
exit( -1 );
}

*/
sprite_tbl *
allocate_sprite_table (int number_of_sprites)
{
static char my_fn[] = "allocate_sprite_table";
sprite_tbl sample, *tmp_s;
int i;
int last_element_no = number_of_sprites - 1;

enter (my_fn);

// Check size of int on this platform
if ((sizeof (int) + 1) > (sizeof (SHIFT_SIZE) / sizeof (int))) {
printf ("Shift table size exceeded, modify code for this machine.\n");
exit (-1);
}

// Check for number of sprites
if (number_of_sprites <= 0)
rtnval (NULL);

// Allocate space for for table area
tmp_s = (sprite_tbl *) malloc (sizeof (sprite_tbl));
if (tmp_s == NULL)
rtnval (NULL);

// Clear data area
memset (tmp_s, 0, sizeof (sprite_tbl));
// Allocate space for sprites
tmp_s->sprites = calloc (number_of_sprites, sizeof (sprite));
if (tmp_s->sprites == NULL) {
free (tmp_s);
rtnval (NULL);
}

// Initalize sprite numbers
for (i = 0; i < number_of_sprites; i++)
tmp_s->sprites[i].sprite_number = i;

// Set table initial values
tmp_s->salloc.number_of_elements = number_of_sprites;
tmp_s->salloc.shift_amt = ELEMENT_SHIFT; // Shift amount for each "int"
tmp_s->salloc.bit_mask = ELEMENT_MASK; // mask to clear unused bits
// Allocate bit table
//TODO::
tmp_s->salloc.bit_table = (int *) calloc (((number_of_sprites +
(ELEMENT_BITS -
1)) >> ELEMENT_SHIFT),
sizeof (int));
// Allocate the correct number of bits
if (tmp_s->salloc.bit_table == NULL) {
free (tmp_s);
rtnval (NULL);
}

// Set count of free sprites to number of sprites
tmp_s->salloc.free_cnt = number_of_sprites;

//
tmp_s->salloc.max_entry = (last_element_no >> ELEMENT_SHIFT);

// Check bit usage in last element
//
if ((last_element_no & ELEMENT_MASK) != (ELEMENT_BITS - 1)) {
int tmp_bit = ((~0) << ((last_element_no & ELEMENT_MASK) + 1));
/*

last bit used (zero based) and add one to get next power of 2, shift
an all one value to the left to clear the number of bit positions and
then use that to set the last position in the table.

*/

// Fix last element for bits allocated after last element
tmp_s->salloc.bit_table[tmp_s->salloc.max_entry] = (tmp_bit);

}

rtnval (tmp_s);

}

/*

Return a pointer to a free sprite in the passed table. If no
free sprites are found return a NULL, otherwise mark the sprite
as "inuse" and return a pointer to the structure.

Sample usage:

sprite * sp_ptr;

sp_ptr = get_free_sprite( tbl_ptr, &err_flag );
if ( err_flag != NO_ERROR ) {
printf("Get free sprite failed with error %d\n", err_flag);
exit( -1 );
}

*/
sprite *
get_free_sprite (sprite_tbl * stbl, sprite_error * err)
{
static char my_fn[] = "get_free_sprite";
int i, *tmp, mask;

enter (my_fn);

if (stbl == NULL) { // bad ptr
*err = BAD_SPRITE_PTR;
rtnval (NULL);
}

if (stbl->salloc.free_cnt == 0) { // none free
*err = BAD_SPRITE_ALL_USED;
rtnval (NULL);
}

//
tmp = stbl->salloc.bit_table + stbl->salloc.first_free; // point a first bit mask
for (i = stbl->salloc.first_free; i <= stbl->salloc.max_entry; i++, tmp++) { // loop through bit masks
if (*tmp != (~0)) { // All bits on, then all used, otherwise some free
//
int bit_array_index = (i << stbl->salloc.shift_amt); // get bit number of first bit
int bit_offset; // count bits
int mask = 1; // mask for first bit

/*
Loop through all possible bit positions, count bits and shifting mask.
*/

for (bit_offset = 0; bit_offset < ELEMENT_BITS; // loop through bits
//
bit_offset++, mask = mask << 1) { // looking for 0 bits
if (((*tmp) & mask) == 0) { // bit off ??
bit_array_index += bit_offset; // get bit number
*tmp = (*tmp) | mask; // mark bit used
stbl->salloc.used_cnt++; // one more used
stbl->salloc.free_cnt--; // one less free
*err = NO_ERROR;
rtnval (stbl->sprites + bit_array_index); // return pointer to bit data
}
}
*err = BAD_SPRITE_ALL_USED;
rtnval (NULL); // all used .... this means free count is fubar.
}
}

*err = BAD_SPRITE_ALL_USED;
rtnval (NULL); // all used .... this means free count is fubar.
}

/*

Mark a "inuse" sprite as free in the passed table. If the sprite
is not "inuse" or any other error return a nonzero value that
indicates the error.

Sample usage:

sprite_error sp_error;

sp_error = free_sprite( tbl_ptr, 5 );
if ( sp_error != NO_ERROR ) {
printf("Free of sprite failed with error %d\n", sp_error );
exit( -1 );
}

*/
sprite_error
free_sprite (sprite_tbl * stbl, int sprite_number)
{
static char my_fn[] = "free_sprite";
int bit_array_index; // get bit array index
int bit_mask; // get bit mask

enter (my_fn);

if (stbl == NULL) // bad ptr
rtnval (BAD_SPRITE_PTR);

if (stbl->salloc.used_cnt == 0) // none used
rtnval (BAD_ALL_SPRITES_FREE);

if ((sprite_number >= stbl->salloc.number_of_elements) || // out of range
(sprite_number < 0)) // out of range
rtnval (BAD_SPRITE_NO);

// Get mask to isolate correct bit
//
bit_array_index = (sprite_number >> stbl->salloc.shift_amt);
bit_mask = (1 << (sprite_number & (stbl->salloc.bit_mask)));

// Check for bit on
//
if ((stbl->salloc.bit_table[bit_array_index] & bit_mask) != 0) {
//
stbl->salloc.bit_table[bit_array_index] &= ~bit_mask; // turn bit off
stbl->salloc.used_cnt--; // one less used
stbl->salloc.free_cnt++; // one more free
if (bit_array_index < stbl->salloc.first_free) // reset first free if needed
stbl->salloc.first_free = bit_array_index;
rtnval (NO_ERROR);
}

rtnval (BAD_SPRITE_IS_FREE);

}

/*

Get the pointer to an "inuse" sprite in the passed table. If the
sprite is not "inuse" or some other error return a NULL.

Sample usage:

sprite * sp_ptr;
sprite_error err_flag;

sp_ptr = get_used_sprite( tbl_ptr, 5, &err_flag );
if ( err_flag != NO_ERROR ) {
printf("Get pointer to used sprite failed with error %d\n", err_flag );
exit( -1 );
}

*/
sprite *
get_used_sprite (sprite_tbl * stbl, int sprite_number, sprite_error * err)
{
static char my_fn[] = "get_used_sprite";
int bit_array_index; // get bit array index
int bit_mask; // get bit mask

enter (my_fn);

if (stbl == NULL) { // bad ptr
*err = BAD_SPRITE_PTR;
rtnval (NULL);
}

if (stbl->salloc.used_cnt == 0) { // none used
*err = BAD_ALL_SPRITES_FREE;
rtnval (NULL);
}

if ((sprite_number >= stbl->salloc.number_of_elements) || // out of range
(sprite_number < 0)) { // out of range
*err = BAD_SPRITE_NO;
rtnval (NULL);
}

// Get mask to isolate correct bit
//
bit_array_index = (sprite_number >> stbl->salloc.shift_amt);
bit_mask = (1 << (sprite_number & (stbl->salloc.bit_mask)));

// Check for bit on
//
if ((stbl->salloc.bit_table[bit_array_index] & bit_mask) != 0) { // bit on ??
*err = NO_ERROR;
rtnval (stbl->sprites + sprite_number);
}

*err = BAD_SPRITE_IS_FREE;
rtnval (NULL);
}

int
main (int argc, char **argv)
{

static char my_fn[] = "msprite";
sprite_tbl *my_sprites;
sprite *tmp_s;
int i, number;
sprite_error err;
sprite_error *err_ptr = &err;

enter (my_fn);
set_debug ();
Log_debug ("This is the start of the program");

if (argc < 2) {
printf ("%s n\n", argv[0]);
printf (" n - count of sprites\n");
exit (-1);
}

number = atoi (argv[1]);

my_sprites = allocate_sprite_table (number);
if (my_sprites == NULL) {
printf ("Unable to allocate sprite table\n");
exit (-1);
}

for (i = 0; i < (my_sprites->salloc.number_of_elements + 2); i++) {
if ((tmp_s = get_free_sprite (my_sprites, err_ptr)) == NULL)
printf ("Get free failed on try %d with error %d\n", i, err);
}

printf ("After get_free, used = %d, free = %d\n",
my_sprites->salloc.used_cnt, my_sprites->salloc.free_cnt);

for (i = 0; i < (my_sprites->salloc.number_of_elements + 2); i++) {
if ((tmp_s = get_used_sprite (my_sprites, i, err_ptr)) == NULL)
printf ("Get used failed on try %d with error %d\n", i, err);
}

printf ("After get_used, used = %d, free = %d\n",
my_sprites->salloc.used_cnt, my_sprites->salloc.free_cnt);

for (i = 2; i < (my_sprites->salloc.number_of_elements); i++) {
if ((err = free_sprite (my_sprites, i)) != 0)
printf ("Free for sprite %d failed with error %d\n", i, err);
}

printf ("After free_sprite, used = %d, free = %d\n",
my_sprites->salloc.used_cnt, my_sprites->salloc.free_cnt);

for (i = 0; i < 2; i++) {
if ((tmp_s = get_used_sprite (my_sprites, i, err_ptr)) == NULL)
printf ("Get used failed on try %d with error %d\n", i, err);
}

printf ("After 2nd get_free, used = %d, free = %d\n",
my_sprites->salloc.used_cnt, my_sprites->salloc.free_cnt);

rtnval (0);
}

Thanks for all the help guys! I really appreciate it! It looks I'll try gmiller's ideas and see what I can come up with.

So far it looks like I'll be needing at least 32k of memory to pull this off.

gmiller, the way I see it is that I can pretty much set these two up like stacks.

For example, if I want to draw a sprite: "pop" from the "free list" and "push" into the "used list"

If I want to disable a sprite: "pop" from the "used list" and "push" into the "free list"

That sound good?
_________________
http://mrkotfw.ribrdb.com/

Yes that is the idea. I use this method to keep from reallocating buffers in systems that must run for a long time. When I startup I allocate a configured number of buffers and use them poping off the free into link lists and then pushing them back when I free up the node. This worked for static and heap allocated things as long as they are either the same size or the largest type is used to allocate the the initial free type.

gmiller wrote:

you could have a link list of free nodes and the link list of "used" nodes

Fantastic idea.

gmiller wrote:

you have one bit for each possible node and you turn the bit off if its free and turn the bit on if it is not.

Same thing. The memory just lives in a different place and it is packed.

Pushing and popping will work.

-Brendan

So 32 bits would mean 32 possible nodes?
_________________
http://mrkotfw.ribrdb.com/

Yes 32 bits is 32 possible nodes but I usually implement the "used/free" table as an arry of int's so I can make the number of nodes as big as I want. If the size of an int is 32 bits then the number of possible nodes is 32 * (sizeof(array)/sizeof(array[0]). Or the more size independent (sizeof(int)*8) * (sizeof(array)/sizeof(array[0]). These calculation would be done at compile time not run time so the divide is not an ARM issue. To find the subscript in the array you just right shift the node number by 5 (for 32 bit int) and the bit number is the node number 'and'ed (binary) with 31.

This is the way the FAT storage allocation table works with a bit for every "cluster" on the disk. The bit is on if the cluster is allocated and off if it is free. The table is size limited so this does not work for large disks but it does work. The sample code I posted uses this to track a limited number of nodes that are not linked together so the used and free list concept does not completely apply. You could link the free and not the used or whatever ...

It actually seems to work like a charm!

Code:

used stack: bit mask, 10 elements
0x000003ff,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
--------------------|-------------------
free stack | used stack
--------------------|-------------------
0x25c00140 | 0x25c00000
0x25c00160 | 0x25c00020
0x25c00180 | 0x25c00040
0x25c001a0 | 0x25c00060
0x25c001c0 | 0x25c00080
0x25c001e0 | 0x25c000a0
0x25c00200 | 0x25c000c0
0x25c00220 | 0x25c000e0
0x25c00240 | 0x25c00100
0x25c00260 | 0x25c00120
0x25c00280 <-- 10 | 0x00000000

Code:

0x25c00000 = sprite #1
0x25c00020 = sprite #2
0x25c00040 = sprite #3
...

_________________
http://mrkotfw.ribrdb.com/

Looks like I have a problem removing an element from the "used" list. For every time I "push" an element into the "used" list, I send the "used" element in the "free" list at the bottom:

Code:

----------------------------|-------------------
free stack | used stack
----------------------------|-------------------
0. 0x25c00040 <- next up | 0x25c00000
1. 0x25c00060 | 0x25c00020
2. 0x25c00080 | 0x00000000
3. 0x25c000a0 | 0x00000000
4. 0x25c000c0 | 0x00000000
5. 0x25c000e0 <- end | 0x00000000
6. 0x25c00000 <- used | 0x00000000
7. 0x25c00020 <- used | 0x00000000

Not really sure how to resolve this. Should I just not touch anything in the "free" list and just set the element as "used" or "free?"
_________________
http://mrkotfw.ribrdb.com/

If you have a used linked list and a free linked list then you just need to link the nodes into the appropriate list. Of course either list could have no elements in it so you need to handle that. If you implemented a stack for the free nodes (rather than a linked list) then you just need to unlink them from the used link list and then push them onto the free list. Of course the pushing and popping should be pointers/indexes to the free nodes not the nodes themselves.

The following code snippets show what I do in a live application using my generic link list code in C. The link list can be any type as long as the structure you are linking is declared like the following:

Code:

#define dList_LINKS(a) \
struct a *next; \
struct a *prior

typedef struct _OUT_QUEUE_
{
dList_LINKS (_OUT_QUEUE_);
...
}
out_queue_t;

The sList_LINKS MUST be the first part of the structure so the generic routines can manipulate them with knowledge of the rest of the fields.

Using the free list concept then is what I do to allocate nodes:

Code:

dList_INIT (resource_entry_free_list);

for (i = 0; i < (CALL_MAX * 100); i++) {
queued_resource_entry *qr;

qr = (queued_resource_entry *) s_malloc (sizeof (queued_resource_entry));
if (qr == NULL) {
em_exit (RTC_FAIL, "Free resource queue entry allocation failure");
}
memset (qr, 0, sizeof (queued_resource_entry));
dList_INIT (qr);
if (dList_APPEND (resource_entry_free_list, qr) == NULL) {
em_exit (RTC_FAIL, "Free resource queue append failure");
}

}

Then when I need a node i do:

Code:

// Get a resource queue entry
if (dList_IS_EMPTY (resource_entry_free_list)) {
qr = (queued_resource_entry *) s_malloc (sizeof (queued_resource_entry));
if (qr == NULL) {
Log_error ("");
rtnval (result);
}
memset (qr, 0, sizeof (queued_resource_entry));
dList_INIT (qr);
Log_debug ("Needed a new free entry for the resource queue %08o",
rq->resource_type);
}
else {
qr = resource_entry_free_list->next;
dList_DETACH (qr);
Log_debug ("Got a free entry for the resource queue");
}

And when I am done with the node I put it back in the free list:

Code:

dList_DETACH (ttmp_qr);
if (dList_APPEND (resource_entry_free_list, ttmp_qr) == NULL) {
Log_error ("Unable to add free resource entry to free queue");
s_free (ttmp_qr);

If you are using a stack with a fixed maximum size, why not just implement it as an array and counter that keeps track of the number of used members?

Code:

#define MAX_SIZE 32

type_t gStack[MAX_SIZE];
int gUsedNodes;

int push(type_t *pData, int pSize)
{
if (pSize <= gUsedNodes)
return OVERFLOW_ERROR;
copyType_t( &(gStack[gUsedNodes]), pData );
gUsedNodes++;
return OK;
}

int pop(type_t *pData)
{
if (gUsedNodes <= 0)
return UNDERFLOW_ERROR;
gUsedNodes--;
copyType_t( pData, &(gStack[gUsedNodes]) );
return OK;
}

-Brendan

sgeos wrote:

If you are using a stack with a fixed maximum size, why not just implement it as an array and counter that keeps track of the number of used members?

Code:

#define MAX_SIZE 32

type_t gStack[MAX_SIZE];
int gUsedNodes;

int push(type_t *pData, int pSize)
{
if (pSize <= gUsedNodes)
return OVERFLOW_ERROR;
copyType_t( &(gStack[gUsedNodes]), pData );
gUsedNodes++;
return OK;
}

int pop(type_t *pData)
{
if (gUsedNodes <= 0)
return UNDERFLOW_ERROR;
gUsedNodes--;
copyType_t( pData, &(gStack[gUsedNodes]) );
return OK;
}

-Brendan

So, then copyType_t() pretty much does something like:

Code:

void
copyType_t(type_t *from, type_t *to)
{
to->element1 = from->element1;
to->element2 = from->element2;
/* And so on... */
}

Thanks for all your help guys! I really appreciate it. The code is starting to work :)
_________________
http://mrkotfw.ribrdb.com/

If it's a straight bitwise copy, you can just do *to = *from.

The way his code works (if your assumtion for copyType_t is correct) you have data movement that is not really needed if you implement push and pop correctly. The push should just link the add the node pointer being pushed to the free pool/list and pop should remove the node pointer from the free pool/list. If there are no free nodes left (free list is empty) then you should get a null pointer. Once you have a node pointer you are free to do what you want with it (other than discard it). When you are done with the node you just need to unlink the node from any link lists and then push the pointer back into the free list.

Everything seems to work great! I can finally delete polygons from the list! It seems to work great so far. I'll try to implement other features that'll make life easier.

Here is a little teaser:
[Images not permitted - Click here to view it]

512 single-colored triangles displayed.
_________________
http://mrkotfw.ribrdb.com/

sajiimori wrote:

If it's a straight bitwise copy, you can just do *to = *from.

I tried that and it gave me an error.

gmiller, I see what you mean. I did have a hard time implementing something similar to that. Instead, I just set the free list as simply a list of address offset values and the actual "used" list as a stack where I push values in. I don't really move things around other than copying a value from the "free" list.
_________________
http://mrkotfw.ribrdb.com/

The movement is not "wrong" just uneeded if implemented different. This movement take CPU cycles that you do not need to use so I would just consider it wasteful.

I don't understand. You're saying that my method that I described sounds like I'm using up a lot of CPU cycles? Or are you talking about the method you've explained to me earlier.
_________________
http://mrkotfw.ribrdb.com/

gmiller wrote:

The movement is not "wrong" just uneeded if implemented different. This movement take CPU cycles that you do not need to use so I would just consider it wasteful.

I was trying to illustrate a stack that does not use pointers. If you are using a memory pool as an array, indices work just well.

The copy in my example code can (and probably should be) be optimized out. Instead of writing to a node in memory you could get a free node and then push it, or call push to get a free node. There are a bunch of ways to handle this.

The copy does have an advantage. You can do something like this:

Code:

type_t newItem; // <- local variable

initItem(BLUE_VERSION); // <- do funny stuff
modifyItem(CHOCOLATE); // <- do funny stuff

pushItem(gItemStack, STACK_SIZE, newItem); // <- push item

If push adds a node and then returns it, you would instead do this:

Code:

type_t newItem = pushItem(gItemStack, STACK_SIZE); // <- get item

initItem(BLUE_VERSION); // <- do funny stuff
modifyItem(CHOCOLATE); // <- do funny stuff

The copy method may be "correct" if you store stock nodes in ROM:

Code:

// itemlib.h
#define BLUE_CHOCOLATE &(gItemLibrary[0])

// itemlib.c
type_t gItemLibrary[] =
{
{ /* BLUE_CHOCOLATE defined here */},
// other stock items
}

// inside of some function
pushItem(gItemStack, STACK_SIZE, BLUE_CHOCOLATE);

You can make anything. What you should make depends on what you need to do.

-Brendan

sgeos wrote:

gmiller wrote:

The movement is not "wrong" just uneeded if implemented different. This movement take CPU cycles that you do not need to use so I would just consider it wasteful.

I was trying to illustrate a stack that does not use pointers. If you are using a memory pool as an array, indices work just well.

The copy in my example code can (and probably should be) be optimized out. Instead of writing to a node in memory you could get a free node and then push it, or call push to get a free node. There are a bunch of ways to handle this.

The copy does have an advantage. You can do something like this:

Code:

type_t newItem; // <- local variable

initItem(BLUE_VERSION); // <- do funny stuff
modifyItem(CHOCOLATE); // <- do funny stuff

pushItem(gItemStack, STACK_SIZE, newItem); // <- push item

If push adds a node and then returns it, you would instead do this:

Code:

type_t newItem = pushItem(gItemStack, STACK_SIZE); // <- get item

initItem(BLUE_VERSION); // <- do funny stuff
modifyItem(CHOCOLATE); // <- do funny stuff

The copy method may be "correct" if you store stock nodes in ROM:

Code:

// itemlib.h
#define BLUE_CHOCOLATE &(gItemLibrary[0])

// itemlib.c
type_t gItemLibrary[] =
{
{ /* BLUE_CHOCOLATE defined here */},
// other stock items
}

// inside of some function
pushItem(gItemStack, STACK_SIZE, BLUE_CHOCOLATE);

You can make anything. What you should make depends on what you need to do.

-Brendan

Thanks. That clears things up a bit. I did in fact use indices for the stack.
_________________
http://mrkotfw.ribrdb.com/

gbadev.org forum archive

Coding > Inserting and deleting nodes (objects) in a list?

#123836 - Piratero - Sat Mar 31, 2007 6:40 pm

#123842 - sajiimori - Sat Mar 31, 2007 7:56 pm

#123843 - Piratero - Sat Mar 31, 2007 8:04 pm

#123844 - keldon - Sat Mar 31, 2007 8:07 pm

#123845 - Piratero - Sat Mar 31, 2007 8:21 pm

#123855 - sajiimori - Sat Mar 31, 2007 10:22 pm

#123863 - Piratero - Sun Apr 01, 2007 12:17 am

#123864 - sajiimori - Sun Apr 01, 2007 12:26 am

#123865 - Piratero - Sun Apr 01, 2007 12:38 am

#123867 - Piratero - Sun Apr 01, 2007 12:45 am

#123869 - keldon - Sun Apr 01, 2007 1:14 am

#123871 - Piratero - Sun Apr 01, 2007 1:23 am

#123877 - sajiimori - Sun Apr 01, 2007 2:18 am

#123879 - Piratero - Sun Apr 01, 2007 2:55 am

#123941 - sajiimori - Sun Apr 01, 2007 9:25 pm

#123962 - sgeos - Mon Apr 02, 2007 4:25 am

#124040 - Piratero - Mon Apr 02, 2007 6:35 pm

#124048 - gmiller - Mon Apr 02, 2007 8:11 pm

#124049 - Piratero - Mon Apr 02, 2007 8:25 pm

#124051 - gmiller - Mon Apr 02, 2007 8:27 pm

#124059 - Piratero - Mon Apr 02, 2007 9:45 pm

#124065 - gmiller - Mon Apr 02, 2007 11:57 pm

#124098 - sgeos - Tue Apr 03, 2007 2:52 am

#124113 - Piratero - Tue Apr 03, 2007 6:00 am

#124135 - gmiller - Tue Apr 03, 2007 1:38 pm

#124182 - Piratero - Tue Apr 03, 2007 10:22 pm

#124233 - Piratero - Wed Apr 04, 2007 7:53 am

#124256 - gmiller - Wed Apr 04, 2007 2:29 pm

#124265 - sgeos - Wed Apr 04, 2007 4:33 pm

#124280 - Piratero - Wed Apr 04, 2007 9:10 pm

#124287 - sajiimori - Wed Apr 04, 2007 9:40 pm

#124288 - gmiller - Wed Apr 04, 2007 9:42 pm

#124321 - Piratero - Thu Apr 05, 2007 2:31 am

#124323 - Piratero - Thu Apr 05, 2007 2:36 am

#124324 - gmiller - Thu Apr 05, 2007 2:42 am

#124331 - Piratero - Thu Apr 05, 2007 3:41 am

#124336 - sgeos - Thu Apr 05, 2007 4:26 am

#124347 - Piratero - Thu Apr 05, 2007 7:47 am