template de pila de id software

[O2]

Hola:

Estába rehaciendo unos templates viejos y mirando códigos para coger ideas y he visto como implementaban los de id diversos templates de pilas, listas, colas, etc... y no termino de entenderlos del todo.

No veo que reserven memoria por ningún sitio, parece que usan algún truco que al menos yo nunca habia visto.

Os pongo el código de una pila

Código [Seleccionar] Expand


#define idStack( type, next ) idStackTemplate<type, (int)&(((type*)NULL)->next)>

template< class type, int nextOffset >
class idStackTemplate {
public:
idStackTemplate( void );

void Add( type *element );
type * Get( void );

private:
type * top;
type * bottom;
};

#define STACK_NEXT_PTR( element ) (*(type**)(((byte*)element)+nextOffset))

template< class type, int nextOffset >
idStackTemplate<type,nextOffset>::idStackTemplate( void ) {
top = bottom = NULL;
}

template< class type, int nextOffset >
void idStackTemplate<type,nextOffset>::Add( type *element ) {
STACK_NEXT_PTR(element) = top;
top = element;
if ( !bottom ) {
bottom = element;
}
}

template< class type, int nextOffset >
type *idStackTemplate<type,nextOffset>::Get( void ) {
type *element;

element = top;
if ( element ) {
top = STACK_NEXT_PTR(top);
if ( bottom == element ) {
bottom = NULL;
}
STACK_NEXT_PTR(element) = NULL;
}
return element;
}

Supongo que el truco está en el par de defines idStack y STACK_NEXT_PTR, pero aún así no consigo comprender donde "meten" los valores que quedan entre "top" y "bottom".

Si alguien puede arrojar un poco de luz, os lo agradecería mucho, ya que me da bastante rabia no entenderlo y además me parece interesante.

Saludos!

[ethernet]

Lo ideal es que mires un ejemplo de uso dentro del propio código, pero por lo que parece la estructura que debes definir debe tener un puntero a next, esto es:

struct MyStruct { Data myData; MyStruct * mynext; };

Luego:


typedef idStack(MyStruct,mynext) MyStructList;

En la implementación de las listas enzadas del kernel de linux hacen algo similar, aunque la implementación de listas que más me ha gustado a sido la del código (que dejan) del unreal.

[Pogacha]

En realidad si, son listas enlazadas.
Los defines son por que el template no les alcanzaba y en vez de restringirse a que la estructura type sea una estructura que tenga que tener como condición obligatoria un puntero llamado "next" al proximo elemento, tan solo le pasan el offset de la variable que hace esta funcion dentro de la estructura, esto permite que la variable se llame ->nextBspNode en una estructura y ->nextElement en otra y que de todas formas pudieramos usar el template.
Esto permite tener también varios tipos de vinculación para un mismo template en una misma estructura, como por ejemplo

Código [Seleccionar] Expand

struct Node {
 int a, b, c;
 Node * NextNodeAboutA;
 Node * NextNodeAboutB;
 Node * NextNodeAboutC;
};
Y de esta manera pueda tener varios Stacks con distintos ordenes segun distintos criterios.

Código [Seleccionar] Expand

idStack( Node, NextNodeAboutA ) StackAboutA;
idStack( Node, NextNodeAboutB ) StackAboutB;
idStack( Node, NextNodeAboutC ) StackAboutC;


Saludos.

[ethernet]

Esa solución está bien, pero desde luego se podría haber implementado de forma similar usado listas enlazadas tradicionales, esto es,std::list. Curioso y parece que eficiente :I.

[AK47]

A mi las std me dan todo el amor que necesito  :lol:
Que por cierto, también está el std::stack :D

[O2]

Sí que es curioso, aunque creo que usaré la forma tradicional, con listas enlazadas. Tengo el código del unreal a mano osea que le echaré un vistazo.

Gracias por contestar.
Saludos!

[gdl]

No tiene ningún misterio. Es una implementación intrusiva pero con offset variable. Las implementaciones de STL son no intrusivas y requieren reservar trocitos pequeños de memoria para los enlaces. Además, en STL pasar un nodo de una lista/pila a otra puede no ser fácil (STL siempre copia, y casi nunca mueve). Con este sistema sí se puede hacer eso.

[Pogacha]

implementación intrusiva con offset variable

Nunca mas clara una definicion, no conocia tales terminos.

[seryu]

lo de no intrusiva es un palabro de esos, simplemente se refiere a que la memoria no se comparte si no que siempre se reserva nueva.

[Pogacha]

Ya me he instruido sobre los terminos acerca de los arreglos:

Por Valor: que se copia en una estructura nueva (eleccion de la STD).

Por referencia: pero como lo podemos hacer de todas formas pasando un puntero por valor mucho no se implementa.

Intrusiva: que la estructura debe tener reservado memoria (estar preparada) para contener información de conexion (su dependencia con su contenedor).

[Diferencial]

Sí que es curioso, aunque creo que usaré la forma tradicional, con listas enlazadas. Tengo el código del unreal a mano osea que le echaré un vistazo.

Gracias por contestar.
Saludos!

Tienes el codigo del unreal, podrias decirme de donde puedo descargarmelo es por curiosidad.

[ethernet]

puedes bajarlo de cualquiera de estos links:

http://www.google.es/search?hs=xOs&hl=es&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=unreal+sorce+code&btnG=B%C3%BAsqueda&meta=

Ten en cuenta que no es todo el ódigo, solo .h (unas 26 mil líneas) + .lib

[ethernet]

Por casualidad he encontrado un enlace en la que explican las listas enlazadas en el kernel de linux que son bastante similares en concepto a las del quake:

http://isis.poly.edu/kulesh/stuff/src/klist/