domingo, 13 de marzo de 2011

miniSL parte 11 - Operaciones sobre el montículo

Ya hemos descrito el montículo en la parte octava. Ahora vamos a realizar dos tipos de operaciones sobre él. El primer grupo es el de las operaciones de reserva de memoria, mientras que el segundo grupo son las operaciones de liberado de memoria. En este post veremos las del primer grupo.
Inicialmente tenemos la creación de una celda genérica con dos referencias.

CELL& Script::CreateCell(CELL_TYPE ct, CELL* first, CELL* second)
{
 CELL* p;
 if(m_FirstUnused==NULL)
 {
  CELL c;
  m_Cells.push_back(c);
  p=&m_Cells.back();
 }
 else
 {
  p=m_FirstUnused;
  m_FirstUnused=p->next_unused;
 }
 p->mark=false;
 p->type=ct;
 p->head=first;
 p->tail=second;
 return *p;
}

Somos astutos y antes de reservar memoria (con el push_back) vemos si tenemos alguna celda libre ya reservada. Esto es algo ineficiente porque la celda que reservemos no vuelve a liberarse realmente, sólo se apunta como liberada. Todo sea por ser simples en la implementación.
Para crear celdas de otros tipos, primero creamos una celda genérica con Script::CreateCell y luego cambiamos sus campos específicos. Por ejemplo, para una cadena no interna.

CELL& Script::CreateString(STRING const& val)
{
 CELL& c=CreateCell(STRING_LIT);
 c.string_val=new STRING(val);
 return c;
}

En el caso de una cadena interna hemos de recurrir a las técnicas comentadas en la parte séptima. En concreto, usaremos el mapa m_InternedStrings para comprobar si ya tenemos o no la cadena internada. Si es así, la usamos. Si no, la creamos y la guardamos en el m_InternedStrings.

CELL& Script::CreateName(STRING const& val)
{
 STRING_MAP::const_iterator i=m_InternedStrings.find(val);
 if(i==m_InternedStrings.end())
 {
  CELL& c=CreateCell(NAME_CODE);
  i=m_InternedStrings.insert(std::make_pair(val, &c)).first;
  c.string_val=&i->first;
 }
 return *i->second;
}

Aquí se ve el truco comentado en la parte séptima: se usa la propia clave del mapa como la cadena interna. Esto nos fuerza a realizar la inserción en dos partes. Primero la celda de tipo NAME_CODE sin ningún puntero iniciado y, luego, se inicia el puntero string_val a la dirección de la clave i->first.

Para crear un entorno necesitamos crear adicionalmente su tabla de símbolos.

CELL& Script::CreateEnvir(CELL* parent)
{
 CELL& c=CreateCell(ENVIR_VAL);
 c.envir_table=new ENVIR_TABLE;
 c.parent_envir=parent;
 return c;
}

Y más sencillo aún son las funciones nativas porque son trozos de código que no se elimina nunca. En este caso necesitamos una función especial meramente porque el tipo es NATIVE y no CELL.

CELL& Script::CreateNative(NATIVE native)
{
 CELL& c=CreateCell(NATIVE_VAL);
 c.native=native;
 return c;
}

Con esto está la creación de celdas completada. En el siguiente apartado veremos cómo se usa el recolector de basura (garbage collector) del cual ya adelantamos algo en la parte octava.

0 comentarios:

Publicar un comentario en la entrada