Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

Resumen   

Programación con punteros inteligentes   

      La biblioteca STL de C++ incluye la clase "auto_ptr<X>" en el archivo de encabezado <memory>. La clase "auto_ptr<X>" le permite al programador cliente usar punteros inteligentes que destruyen el objeto que referencian cuando su ámbito de existencia termina; estos punteros son "dueños" del objeto que referencian. Por ejemplo, en el siguiente bloque de código el programador no tiene que preocuparse por retornar la memoria dinámica de la que el puntero "p" es dueña:

{   auto_ptr<BigMatrix> p , q( new BigMatrix( 50*1000 , 100*1000 ) ) ;
    // ...
    q->foo( 15*1000 ); // "q" funciona como un puntero
    p = q; // Ahora "q" es NULL y "p" es el nuevo dueño
    // ...
}   // Aquí el destructor de "p" devuelve la memoria

La clase "auto_ptr<X>" funciona como si la implementación de la asignación de punteros fuera similar a la siguiente [Sha-1999]:

template <class T> // OJO: "q" no es un argumento "const"
auto_ptr<T>& auto_ptr<T>::operator= ( auto_ptr<T>& q ) {
    if ( this != &q ) {
        if ( m_ptr != 0 ) {
            delete m_ptr; // "m_ptr" es el campo que referencia el objeto
        }
        m_ptr = q.m_ptr; // nuevo dueño
        q.m_ptr = NULL; // deja a "q" en NULL
    }
    return *this;
}

      La clase "auto_ptr<X>" tiene algunas desventajas bien conocidas entre la que destaca el que estos punteros inteligentes no se deben usar para almacenar valores en los contenedores de la biblioteca STL porque cada puntero "auto_ptr<X>" siempre es el único dueño del objeto que referencia. La operación de inserción en cualquier contenedor STL siempre almacena una copia profunda del objeto pues se supone que la copia almacenada puede ser modificada sin cambiar el valor original [Str-1998]. En el ejemplo de arriba, la asignación "p = q;" deja al puntero "q" con un valor nulo ("NULL") de manera que el objeto referenciado no sea destruido 2 veces (la primera una vez por el destructor de "p" y la segunda por el de "q").

      La forma de remediar las carencias de la clase "auto_ptr<X>" es usar cuentas de referencia de manera que varios punteros inteligentes puedan compartir la misma instancia. Existen varias implementaciones de las cuentas de referencia, pero la implementación de la clase "lkptr<X>" escogida aquí es la llamada "enlaces de referencia" (reference linking), que tiene las siguientes ventajas:

• No usa memoria dinámica adicional.
• No es "intrusiva" porque no requiere de un contador almacenado en el objeto referenciado.
• Es viable usar contenedores STL para almacenar referencias inteligentes "lkptr<X>".
• Es muy simple de usar pues la implementación completa está en el archivo de encabezado "lkptr.h".
• Es adecuada para aplicaciones en que se usa programación concurrente mediante múltiples hilos o procesos.

Implementación de la clase "lkptr<X>"   

      Los punteros inteligentes "lkptr<X>" tienen la cualidad de que comparten un mismo objeto. Una forma de lograr que varios punteros queden marcados porque referencian el mismo objeto es incluir en el objeto referenciado un contador que indica cuántos punteros le referencian. La cuenta se incrementa si a un puntero inteligente se le asigna el valor de otro y el destructor del puntero inteligente es el responsable de decrementar la cuenta; en este caso, si la cuenta llegara a ser cero, también el destructor del puntero debe destruir el objeto referenciado porque ya ningún otro puntero inteligente la está referenciando.

   +---+
p1 | *-|----->+
   +---+      |
              |     RefCnt
   +---+      +---->+---+----------------------+
p2 | *-|----------->| 3 | Costa Rica Pura Vida |
   +---+      +---->+---+----------------------+
              |
   +---+      |
p3 | *-|----->+
   +---+
                    RefCnt
   +---+            +---+----------------------+
p4 | *-|----------->| 1 | Viva Italia          |
   +---+            +---+----------------------+

lkptr<Chunche> foo() {
     lkptr<Chunche> p1, p2, p3;
     p3.reset( new Chunche( "Costa Rica Pura Vida" ) );
     p1 = p2 = p3; // los 3 comparten la instancia
     {    lkptr<Chunche> p4 (new Chunche( "Viva Italia" ) );
          // ...
     } // aquí "p4" es destruido

     return p2; // p1, p2, p3 son destruidos
}    //         ... el objeto referenciado persiste

      En la Figura 1 los punteros "p1", "p2" y "p3" comparten el mismo objeto "Costa Rica Pura Vida" mientras que el único dueño de "Viva Italia" es "p4". Si el puntero "p4" dejara de existir, lo que en este caso ocurre cuando el control del programa deja el bloque en que está definido "p4", su valor referenciado también es destruido porque su cuenta de referencia llega a cero. Esto no es lo que ocurre cuando los otros 3 punteros son destruidos porque para retornar el valor de "p2" el compilador debe invocar al constructor de copia de la clase "lkptr<X>" para retornar una copia de "p2", y eso aumenta la cuenta de referencia a 4. A pesar de que el destructor de los 3 punteros decrementa el contador de referencias 3 veces, a fin de cuentas tiene valor 1 == 4-3 y, en consecuencia, el valor compartido no es destruido y sí es correctamente retornado al programa invocador.

   +---+
p1 | *-|-->+
   +---+   |
           |   RefCnt
   +---+   +-->+---+---+   +----------------------+
p2 | *-|------>| 3 | *-|-->| Costa Rica Pura Vida |
   +---+   +-->+---+---+   +----------------------+
           |
   +---+   |
p3 | *-|-->+
   +---+
               RefCnt
   +---+       +---+---+   +----------------------+
p4 | *-|------>| 1 | *-|-->| Viva Italia          |
   +---+       +---+---+   +----------------------+

      El problema que tiene la implementación de punteros con cuentas de referencia es que hay que incluir en el objeto referenciado un campo para almacenar ahí la cantidad de punteros que referencian el objeto. Otra forma de lograr lo mismo es poner esa cuenta en otro objeto externo como se muestra en la Figura 2. Este esquema no siempre es deseable porque requiere crear un objeto intermedio en memoria dinámica lo que en algunas aplicaciones puede ser inconveniente, como en aplicaciones de sistemas de tiempo real en donde crear objetos en memoria dinámica puede ser muy oneroso.

<=================================>     <=============>
|      p1        p2       p3      |     |      p4     |
|    +-+-+     +-+-+     +-+-+    |     |    +-+-+    |
<===>|*|*|<===>|*|*|<===>|*|*|<===>     <===>|*|*|<===>
     +-+-+     +-+-+     +-+-+               +-+-+
     | * |     | * |     | * |               | * |
     +-|-+     +-|-+     +-|-+               +-|-+
       |         |         |                   |
      \|/       \|/       \|/                 \|/
     +----------------------+      +----------------------+
     | Costa Rica Pura Vida |      | Viva Italia          |
     +----------------------+      +----------------------+

      La otra manera de realizar la implementación es poner en una lista doblemente enlazada a todos los punteros que comparten un valor; se sabe que un puntero es la última referencia si está solo en la lista, como ocurre con "p4" en la Figura 3. La desventaja de esta solución es que requiere tres veces más almacenamiento por puntero, pues además de la referencia al valor compartido es necesario incluir los 2 punteros necesarios para mantener la lista doblemente enlazada. Sin embargo, en la mayor parte de las aplicaciones este incremento en la cantidad de memoria es poco relevante porque serán relativamente pocos los punteros que existan simultáneamente en un programa. La implementación "lkptr<X>" que se discute en este trabajo usa la lista enlazada en lugar de las cuentas de referencia porque es la que tiene mayores ventajas y menos inconvenientes. No importa cuál es el primero o el último de la lista, pues lo que importa es que la asignación de un puntero a otro resulta también en el enlace en la lista de referencias.

Construcción de una clase con punteros inteligentes   

      Una de las desventajas que tiene C++ cuando se le compara con Java es que es relativamente más caro retornar objetos grandes en C++. Por ejemplo, si se usa la clase "Matrix" descrita en [DiM-2004], la forma natural de implementar los operadores aritméticos es la siguiente:

/// Calcula y retorna \c (A * B).
Matrix operator* ( const Matrix& A, const Matrix& B ) {
    Matrix Resultado...
    // ... algoritmo de multiplicación de matrices
    return Resultado;
}

      Como la variable "Resultado" es una variable local, el compilador genera código para copiar con el constructor de copia esa variable local al área de retorno en la rutina invocadora, lo que en este caso implica hacer la copia de un objeto bastante grande, pues la cantidad de memoria que usa una matriz es proporcional a la multiplicación de sus dimensiones. Lo natural sería crear la matriz en memoria dinámica, y retornar un puntero a la matriz:

/// Calcula y retorna un puntero a \c (A * B).
Matrix* operator* ( const Matrix& A, const Matrix& B ) {
    Matrix * Resultado = new Matrix (...)
    // ...
    return Resultado;
}

      Esta solución es adecuada pero obliga al invocador a destruir el objeto retornado, lo que puede resultar en fugas de memoria ("memory leaks") y, además, es un tanto incómodo de implementar y de usar. La alternativa es retornar un puntero inteligente "lkptr<X>" como se muestra en la siguiente implementación del operador de suma:

/// Calcula y retorna \c A+B
lkptr<Matrix> operator + ( const lkptr<Matrix>& A, const lkptr<Matrix>& B ) {
    lkptr<Matrix> Res ( new Matrix(*A) ); Res->add(*B); return Res;
}

      En la práctica es incómodo modificar una clase ya existente, pues al hacer cambios es posible introducir errores. Una manera de evitar esta situación es construir una nueva clase derivada de la clase original, de manera que sea en la clase derivada adonde se hagan los cambios. Surge así la clase de plantillas "RefMatrix" derivada de la clase "Matrix". En la implementación "RefMatrix.h" se han agregado únicamente las operaciones aritméticas que se quieren mejorar al hacerlas retornar referencias "lkptr<X>" en lugar de copias completas del objeto calculado:

• Los constructores y el destructor.
• Los operadores aritméticos " { + - * } ".
• La operación de "clone()" que retorna un puntero a una copia de la instancia.

      La implementación de los constructores y el destructor de la clase "RefMatrix" es una redefinición directa de los de la clase "Matrix". Por ejemplo, el constructor de copia queda implementado en un sólo renglón:

RefMatrix(const RefMatrix& o) : Matrix<E>(o) { }

template <class E>
class RefMatrix : public Matrix<E> {
    /// Constructor de copia
    RefMatrix(const RefMatrix& o) : Matrix<E>(o) { }
// ...
    /// Retorna un puntero a una copia de la instancia.
    RefMatrix<E>* clone() const { return new RefMatrix<E>(*this); }

    ///< Calcula y retorna \c A+B
    friend lkptr<RefMatrix> operator + (const lkptr<RefMatrix>& A, const lkptr<RefMatrix>& B) }
        lkptr<RefMatrix> Res ( A->clone() ); Res->add(*B); return Res;
    }
// ...
};

      El método "RefMatrix::clone()" usa el constructor de copia de la clase base "Matrix" para obtener una copia profunda. Lo mismo puede lograrse con la siguiente función genérica:

/// Retorna un puntero a una nueva instancia que contiene un duplicado del valor del \c "obj".
/// - La copia se hace invocando al constructor de copia.
/// \see http://www.di-mare.com/adolfo/binder/c04.htm#sc06
template <class E>
inline E* clone( const E& obj ) { return new E( obj ); }

      La receta para lograr retornar grandes objetos usando los punteros inteligentes "lkptr<X>" es muy simple: basta crear una nueva clase de empaque con base en la clase original, lo que se puede lograr usando herencia, e implementar de nuevo únicamente aquellas operaciones que requieran retornar objetos grandes.

Uso de referencias en programas C++   

      Las variables "lkptr<X>" funcionan como punteros, por lo que al usarlas hay que usar la sintaxis C++ para punteros. En algunos casos es molesto anteponer el asterisco "*" para derreferenciar el puntero, pero en la mayoría de los casos la notación de la flecha "lk->campo" es adecuada y elegante, como se muestra en el siguiente bloque C++ que usa 3 matrices cuyo valor es accesado con "lkptr<unsigned>":

/// Ejemplo de uso de referencia \c lkptr< RefMatrix<unsigned> >.
void use_lkptr( unsigned M, unsigned N ) {
    lkptr< RefMatrix<unsigned> > A ( new RefMatrix<unsigned>(M,N) );
    unsigned k = 0;
    for (unsigned i=0; i < A->rows(); ++i) {
        for (unsigned j=0; j < A->cols(); ++j) {
            A->at(i,j) = k++; // (*A)(i,j) = k++;
        }
    }

    lkptr< RefMatrix<unsigned> > B, C ( A ); // A y C comparten el valor
    assert( B == (void*)0 ); // B es un objeto nulo
    B = C; // A B y C comparten el valor
    B->reSize( B->cols(), B->rows() ); // todos fueron modificados
    assert( B == A );   // comparación de punteros
    assert( *B == *A ); // comparación de matrices
    B.reset( A->clone() ); // B tiene una copia de A
    B->reSize(N,M); // solo B cambia
    C = (C - C);
    assert( A->at(0,0) == 0 ); // porque C borró todo
    C = B + B - B;
    B->reSize( B->cols(), B->rows() ); // solo B cambia
    A = C * B; // ya ninguno comparte memoria
    assert( *A != *B && *B != *C && *C != *A ); // comparación de matrices
}

      Al examinar este código se pueden sacar las siguientes conclusiones:

• En lugar de usar la notación de acceso al miembro "A.m()" es necesario usar "A->m()".
• Para obtener una copia del objeto referenciado hay que clonarlo, invocando tanto al operador "new" para obtener memoria dinámica como al constructor de copia de la clase base.
• Para obtener una copia del objeto referenciado no se puede usar el operador de asignación, por al hacerlo lo que se lograr en que 2 punteros "lkptr<X>" compartan el mismo objeto.

      A diferencia de los programadores Java, los programadores C++ están entrenados para saber que los punteros objetos son diferentes a lo que referencian. Por eso, para un programador C++ no es problema distinguir entre el objeto "X" y una referencia "lkptr<X>". Sin embargo, si se usan los punteros "lkptr<X>" para incorporar programadores Java a un proyecto C++ es necesario mostrarles las diferencias pues de lo contrario quedarían limitados en su capacidad para escribir programas correctos. En otras palabras, si alguien puede programar en C++ con "lkptr<X>" de seguro podrá programar en Java.

El árbol binario implementado con referencias   

      Los punteros "lkptr<X>" tienen un comportamiento que permite construir programas como si se contara con un recolector de basura para el lenguaje. Un buen ejemplo lo constituye el árbol binario "Bin_Tree" implementado en "Bin_Tree.h" en donde se usan referencias "lkptr<X>" que son en realidad árboles completos.

template <class E>
class Bin_Tree_Node {
public:
    typedef E value_type; friend class Bin_Tree<E>;

private:
    value_type                 m_data;
    lkptr< Bin_Tree_Node <E> > m_father;
    lkptr< Bin_Tree_Node <E> > m_left;
    lkptr< Bin_Tree_Node <E> > m_right;
private:
    Bin_Tree_Node( const value_type& d )
    : m_data( d ), m_father(0), m_left(0), m_right(0) {}
public: ~ Bin_Tree_Node() {}
};

template <class E>
class Bin_Tree {
private:
    lkptr< Bin_Tree_Node <E> > m_root; ///< Raíz del árbol.
// ...
    Bin_Tree left() const;
};

      En la Figura 4 está la definición del nodo del árbol binario. Un árbol binario contiene únicamente su puntero inteligente a la raíz "m_root", de tipo "lkptr<X>". El nodo del árbol es una clase opaca porque el programador cliente nunca necesita usar nodos pues las operaciones del árbol manipulan y retornan árboles. Por ejemplo, al invocar "left()" el resultado será obtener otro árbol que contiene la referencia "lkptr<X>" que referencia el subárbol izquierdo. En otras palabras, esta implementación corresponde a la abstracción de un árbol en la que no se menciona a los nodos. Una especificación más completa de los árboles se encuentra descrita en [DiM-2005].

      Como ocurre con otras implementaciones, en esta los nodos contienen el valor almacenado y los punteros a los hijos. Como el programador cliente del árbol no tiene que lidiar con nodos sino que todas la operaciones se hacen directamente sobre árboles, cualquier constructor para la clase "Bin_Tree_Node" debe ser privado. Los nodos son creados únicamente en los métodos de la clase "Bin_Tree"; el destructor de la clase "Bin_Tree_Node" sí debe ser público para que otros módulos puedan destruir árboles ya construidos. Parece contradictorio que el destructor sea público mientras que el constructor es privado: esto es una técnica usual en programación C++ cuando en una implementación es necesario usar clases externas; habría sido más conveniente definir la clase "Bin_Tree_Node" como una clase anidada dentro de "Bin_Tree" pero, desafortunadamente, algunas construcciones sintácticas C++ funcionan solo si no se usan plantillas.

template <class E>
class Bin_Tree {
private:
    lkptr< Bin_Tree_Node <E> > m_root; ///< Raíz del árbol.
// ...
private:
    /// Constructor a partir de un nodo.
    Bin_Tree( lkptr< Bin_Tree_Node<E> >& other ) : m_root(other) { }
// ...
public:
    /// Acceso al hijo izquierdo.
    /// - Si el sub-árbol no tiene hijo izquierdo retorna el árbol vacío.
    Bin_Tree Bin_Tree left() const {
        if ( m_root == 0 ) { return Bin_Tree(); }
        else { return Bin_Tree( m_root->m_left ); }
    }
};

      En la Figura 5 está la implementación completa del método "left()". El trabajo que hay que hacer es muy simple, pues basta retornar una copia del puntero "m_root" para lo que se usa un constructor privado del árbol que sirve para crear un nuevo árbol con base en una referencia "lkptr<X>".

/** Convierte a \c "T" en su sub-árbol espejo.
   - Recursivamente, sus hijos quedan en orden inverso del
     orden en el que aparecían originalmente en \c "T".
   \code
           a                  a
          / \                / \
         /   \              /   \
        b     e            e     b
       / \   / \          / \   / \
      f   h i   k        k   i h   f
               / \      / \
              l  m      m   l
                / \    / \
               n   o  o   n
    \endcode
*/
template <class E>
void mirror( Bin_Tree<E> & T ) {
     if ( T.isEmpty() ) {
        return; // se sale si el árbol está vacío
    }
    // intercambia los hijos
    Bin_Tree<E> Left  = T.left();  // sostiene a cada hijo
    Bin_Tree<E> Right = T.right();
    T.makeLeftChild( Right ); // Pone el hijo derecho a la izquierda
    T.makeRightChild( Left ); // Pone el hijo izquierdo a la derecha
    mirror( Left  );
    mirror( Right ); // recursivamente modifica los hijos
}

      Como se muestra en la Figura 6, el efecto de sostener a un sub-árbol con una referencia "lkptr<X>" facilita mucho la implementación de funciones como "mirror()", en la que el intercambio de sub-árboles se hace sin problema, pues mientras un hijo queda desligado la referencia a él impide que sea borrado. Esta forma de programación es la que es usual encontrar al implementar contenedores en Java. Es importante destacar que esta implementación "no se le mete al Rep" pues usa únicamente los métodos públicos de la clase "Bin_Tree" [DiM-2007].

Peligro de usar referencias cíclicas   

      Las referencias cíclicas o circulares pueden producir problemas si se usan punteros inteligentes, pues la destrucción del objeto referenciado puede producir un llamado recursivo infinito.

#include "lkptr.h"

class AutoRef {
    static int m_cont;
    lkptr<AutoRef> m_otro;
public:
    AutoRef() { m_cont++; }
    ~AutoRef() { m_cont--;
        {{/* m_otro.weak_release(); */}}
    }
    void set( AutoRef * P ) {
        m_otro.reset( P );
    }
    static int cont() {
        return m_cont;
    }
};

int AutoRef::m_cont = 0;

#include <cassert>

int main() {
    {
        assert( AutoRef::cont() == 0 );
        lkptr<AutoRef> paco ( new AutoRef() );
        assert( AutoRef::cont() == 1 );
        lkptr<AutoRef> lola ( new AutoRef() );
        assert( AutoRef::cont() == 2 );

        paco->set( lola );
        lola->set( paco );
    }   // BOOOM !!!
    assert( AutoRef::cont() == 0 );
}

  paco       lola  
 +---+      +---+ 
 | * |      | * | 
 +---+      +---+ 
   |         |   
   v         v   
+-----+    +-----+
|  *--|--->|     |
|     |<---|--*  |
+-----+    +-----+
AutoRef    AutoRef

      Cuando el puntero "paco" de la Figura 7 es destruido su destructor invocará al destructor de "lola", el que a su vez invocará al destructor de "paco", lo que creará una cadena infinita de llamados mutuos recursivos. Esto es consecuencia de que un puntero inteligente es dueño del objeto que referencia y, al ser destruido, debe desligarse de su objeto pero, si es el último valor que referencia al objeto, también debe destruirlo. En el caso de "paco" y "lola" ellos son los únicos dueños del objeto del otro por lo que cada uno de ellos trata de destruir al otro y el resultado es el ciclo recursivo infinito.

      Una forma de evitar estas referencias circulares es sustituirlas por referencias a un tercer objeto de intersección [Elcel-2007]. Por ejemplo, si los objetos "A" y "B" contienen punteros inteligentes que se referencian mutuamente A↔B, la idea es introducir un tercer objeto "C" de manera que la relación quede así: A→C←B (sin el ciclo).

      Otra manera de manejar referencias circulares es liberar punteros usando el método lkptr<>::weak_release() que elimina el acople entre el puntero inteligente y su objeto apuntado, de manera que se evita la destrucción mutuamente recursiva cuando es necesario usar ciclos de punteros. Por eso, la especificación de estos métodos es la siguiente:

template <class X> void lkptr<X>::release()
Elimina el acople entre el puntero inteligente y su objeto apuntado.

• Antes: Si esta es la última referencia, también destruye el objeto referenciado.
• Después: El puntero queda anulado en "NULL".
• Después: Tiene un efecto similar a "reset(0)".

---

template <class X> void lkptr<X>::weak_release()
Elimina el acople entre el puntero inteligente y su objeto apuntado.

• Antes: Si esta es la última referencia, no borra el objeto.
• Después: El puntero queda anulado en "NULL".
• Después: Tiene un efecto similar a "reset(0)" (pero no destruye al objeto).
• Diferencia: Nunca destruye el objeto referenciado.

Peligro de destrucción múltiple   

      En algunas ocasiones parece necesario usar el puntero que un "lkptr<X>" administra para darle valor a otro "lkptr<X>"; por ejemplo, puede ocurrir que una función o método retorne un puntero que es usado luego para darle valor a un "lkptr<X>". Este es un error porque varios objetos "lkptr<X>" son dueños del objeto referenciado pero están desligados. Como todos estos punteros inteligentes no están relacionados pero sí apuntan la mismo objeto referenciado, al ser destruido cada uno de estos "lkptr<X>" destruirá el objeto referenciado con el resultado de que el mismo objeto será destruido varias veces.

#define   lkptr_MERGE_IS_PUBLIC
#include "lkptr.h"
//...
void multiDestroy() {
    int * pInt = new int(12);
    lkptr<int> tik ( pInt );  assert( *tik == 12 );
    lkptr<int> tak;
    tak.reset( tik.get() ); // [ERROR] tik && tak apuntan al mismo objeto

    if (true) { // con lktpr<>::merge() se evita la destrucción múltiple
        tik.merge( tak );
        assert( tik.use_count() == 2 ); // tik && tak están atados
        assert( tak.use_count() == 2 );
        assert(    tik == tak        ); // ambos comparten el mismo objeto
        assert(   *tik == *tak       );
    }
    else {
        assert( tik.use_count() == 1 ); // tik no está relacionado a tak
        assert( tak.use_count() == 1 );
        assert(    tik == tak        ); // ambos apuntan al mismo objeto
        assert(   *tik == *tak       ); // no comparten el mismo objeto
        // Error: double destrucción de pInt por tik && tak
    }
}

      La clase "lkptr<X>" incluye el método "merge()" que se encarga de juntar 2 "lkptr<X>" siempre y cuando ya referencian el mismo objeto. Este método es privado porque lo natural es que este método nunca deba usarse. Sin embargo, si el programador alguna vez lo necesitara, puede forzar a que quede declarado como público definiendo la macro "lkptr_MERGE_IS_PUBLIC" antes de usar el archivo de encabdezado "lkptr.h". Aún mejor es siempre usar métodos o funciones que retornan objetos "lkptr<X>" en lugar de punteros. En la Figura 8 se muestra cómo relacionar 2 objetos "lkptr<int>" que individualmente son dueños el mismo objeto.

Almacenamiento en contenedores STL   

      Algunos métodos de la biblioteca STL hacen copias de los objetos suponiendo que tanto el original como la copia persisten (y que por supuesto son también iguales). Por eso, si se usa la clase "auto_ptr<X>" en los contenedores STL pueden presentarse problemas cuando sólo la copia del puntero "auto_ptr<X>" mantiene su valor. Por ejemplo, al usar un algoritmo de ordenamiento "sort()" en un vector STL que contiene punteros "auto_ptr<X>", durante el ordenamiento se hacen varias copias del mismo objeto y, en consecuencia, podría el vector quedar vacío. Este problema no existe con los punteros "lkptr<X>" pues tanto el original como todas sus copias mantienen su valor (de hecho lo comparten). Por eso no habrá problemas mezclando las clases y contenedores STL con valores referenciados por "lkptr<X>".

Control de concurrencia   

      En un ambiente en que varios procesos o hilos de ejecución pueden modificar el mismo objeto es necesario incorporar algún tipo de control de concurrencia que evite que lo que hace uno afecte al otro. La forma más simple de administrar el acceso a los campos sensitivos de la clase es prender un semáforo antes de cambiar los campos. Para eso, basta incluir las primitivas de sincronización en los métodos "fast_release()" y "acquire()" que se encargan de enlazar y desenlazar las referencias "lkptr<X>". Lo natura es implementar el semáforo como una variable estática de la clase lo que disminuye la contención únicamente entre los punteros "lkptr<X>" para valores de la clase "X". Lo usual es que hay pocos punteros para una misma clase "X", por lo que el gasto en control de concurrencia es muy bajo.

#include <MySemaphore.h>

template <class X>
class lkptr {
   // ...
private:
   /// Asegura que sólo 1 proceso puede modificar.
   static Semaphore m_semaphore : Semaphore() { /* ... */ }
   // ...

void fast_release() {
    m_Semaphore.wait(); // bloquea a los demás
    if ( m_prev == this ) {
        if ( m_ptr!=0 ) {
            delete m_ptr;
        }
    }
    else {
        m_prev->m_next = m_next;
        m_next->m_prev = m_prev;
    }
    m_Semaphore.signal(); // otros pueden modificar
}

void acquire(lkptr* r) throw() {
    m_Semaphore.wait(); // bloquea a los demás
    m_ptr = r->m_ptr;
    m_next = r->m_next;
    m_next->m_prev = this;
    m_prev = r;
    r->m_next = this;
    m_Semaphore.signal(); // otros pueden modificar
}
}; // class lkptr<X>

      El control de concurrencia que se muestra en la Figura 9 sirve para que no haya problemas al cambiar los campos de la clase "lkptr<X>", pero no garantiza el control de concurrencia para el objeto referenciado. Sin embargo, una vez que se han cambiado los campos, el programador cliente puede dereferenciar el puntero inteligente "lkptr<X>" sin necesidad de bloquearlo porque el objeto rereferenciado no será destruido mientras exista al menos una referenciar "lkptr<X>" hacia él.

      En cada plataforma de desarrollo C++ se usan bibliotecas diferentes para el manejo de la concurrencia. Por eso no se ha escogido ninguna en específico para implementar "lkptr<X>".

template <class X>
class lkptr {
// ...
public:
    /// Copy constructor.
    lkptr( const lkptr& r ) throw() {
        acquire( const_cast<lkptr*>( &r ) );
    }
    /// Copy operator.
    lkptr& operator=( const lkptr& r ) {
        if (this != &r) {
            fast_release();
            acquire( const_cast<lkptr<X>*>( &r ) );
        }
        return *this;
    }
};  // lkptr<X>

      Existe un detalle importante que hay que tomar en cuenta si se usan punteros "lkptr<X>" en memorias de sólo lectura ("ROM"). Al copiar uno de estos valores es necesario cambiar el puntero del que se copia, de manera que ambos queden enlazados en la misma lista doblemente enlazada. Por eso, la asignación "p = q;" modifica el valor de "p", el de "q" y el de otro 2 valores a los que antes estuvo "p" enlazado. Eso quiere decir que en realidad el operador de asignación sí modifica su argumento en contraposición a lo que dice su especificación. En la Figura 10 se muestra que en la implementación de estos métodos es necesario usar "const_cast" para modificar el argumento de entrada. Esta modificación sólo cambia los campos de enlace de la lista doblemente enlazada pero nunca cambia el puntero "m_ptr" hacia el objeto referenciado.

Conclusión   

      El costo de implementación de los punteros inteligentes es "lkptr<X>" es de 3 punteros por referencia, y de 5 asignaciones de punteros cuando se comparten valores, más 2 asignaciones cuando el puntero se desliga de los demás. Este costo es bajo en comparación con los beneficios que retribuye su uso:

• Para usar "lkptr<X>" basta incluir un único archivo de encabezado "lkptr.h" en contraposición a utilizar una biblioteca o ambiente complete que se encargue de la recolección de basura.
• El estilo de programación que "lkptr<X>" soporta permite utilizar el código C++ existente sin necesidad de hacerle cambios profundos.
• No se requiere aprender un nuevo paradigma de programación para poder usar objetos grandes con comodidad si se manipulan a través de punteros inteligentes "lkptr<X>".
• La existencia de un objeto compartido por referencias "lkptr<X>" no va más allá de la última referencia activa hacia el objeto, lo que garantiza una recuperación eficiente de la memoria dinámica que ya no está en uso.
• Debido a que "lkptr<X>" no es un recolector de basura, no impone retardos asincrónicos con la aplicación y tampoco introduce un componente aleatorio en la duración de la ejecución.
• Los programas que usan "lkptr<X>" son deterministas porque bajo las mismas condiciones su tiempo de ejecución siempre es el mismo.
• Para la programación de sistemas incrustados o de tiempo real conviene usar "lkptr<X>" porque la implementación no usa memoria dinámica para almacenar cada referencia.
• La implementación de "lkptr<X>" no levanta excepciones porque no necesita adquirir memoria dinámica. El único caso en que una excepción puede ocurrir es si el destructor de la clase referenciada levanta una excepción, en cuyo caso el manejo usual de excepciones de C++ permite lidiar con el problema.
• En ambientes de programación concurrente por multiproceso o por el uso de múltiples hilos, es posible sincronizar efectiva y eficientemente el acceso a través de los punteros "lkptr<X>" utilizando un semáforo, que es un mecanismo simple y barato para el control de acceso.

      Es prematuro afirmar que C++ se puede usar con la misma facilidad que Java para desarrollar aplicaciones, pero los punteros inteligentes "lkptr<X>" definitivamente contribuyen a que más aplicaciones Java sean implementadas en C++. Sí se puede afirmar que cada vez quedan menos espacios en donde resulta mejor una implementación Java en lugar de una implementación C++.

Agradecimientos   

      David Chaves y Alejandro Di Mare aportaron varias observaciones y sugerencias importantes para mejorar este trabajo. Francisco Arroyo sugirió las ideas principales para el manejo de concurrencia y Sebastián León ayudó en la construcción de "lkptr<>::merge()".

Código fuente   

lkptr.zip: Todos los fuentes [.zip]

http://www.di-mare.com/adolfo/p/lkptr/lkptr.zip

---

lkptr.h: simple reference LinKed PoinTeR [.html] [.h] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/index.html

test_lkptr.cpp: Test data for class lkptr [.html] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/classtest__lkptr.html

---

test_inheritance.cpp: Shows that class lkptr<X> handles inheritance correctly [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/test_inheritance.cpp

figures.h: Jerarquía de clases de figuras usadas en test_lkptr.cpp [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/figures.h

AutoRef: Clase que se auto-referencia [.html] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/structAutoRef.html

---

Bin_Tree.h: Arbol binario implementado con referencias lkptr<X> [.html] [.h] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/classBin__Tree.html

Bin_Tree_Lib.h: Funciones de apoyo para la clase Bin_Tree<E> [.html] [.h] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/Bin__Tree__Lib_8h.html

test_Bin_Tree.cpp: Prueba de caja negra de la clase Bin_Tree<E> [.html] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/classtest__Bin__Tree.html

---

Matrix.h: Declaraciones y definiciones para la clase Matrix [.html] [.h] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/classMx_1_1Matrix.html

Matrix_Lib.h: Algunas propiedades para la clase Matrix [.html] [.h] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/Matrix__Lib_8h.html

RefMatrix.h: Muestra cómo implementar una matriz usando referencias lkptr<X> [.html] [.h] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/classMx_1_1RefMatrix.html

test_RefMatrix.cpp: Prueba de caja negra de la clase RefMatrix [.html] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/lkptr/test__RefMatrix_8cpp.html

---

Disponibilidad Doxygen:

ftp://ftp.stack.nl/pub/users/dimitri/doxygen-1.5.4-setup.exe

Notas de pie de página   

Bibliografía   

Indice   

[-]	Resumen
[-]	Programación con punteros inteligentes
[-]	Implementación de la clase "lkptr<X>"
[-]	Construcción de una clase con punteros inteligentes
[-]	Uso de referencias en programas C++
[-]	El árbol binario implementado con referencias
[-]	Peligro de usar referencias cíclicas
[-]	Peligro de destrucción múltiple
[-]	Almacenamiento en contenedores STL
[-]	Control de concurrencia
[-]	Conclusión
[-]	Agradecimientos
[-]	Código fuente
	Bibliografía
	Indice
	Acerca del autor
	Acerca de este documento
	Principio Indice Final

Acerca del autor   

Adolfo Di Mare <adolfo@di-mare.com>

Acerca de este documento   

Referencia:	Di Mare, Adolfo: lkptr.h: Programación por Referencia Java para C++ , XVI Congreso Iberoamericano de Educación Superior en Computación (CIESC-2008), realizado del 8 al 12 de setiembre 2008, Santa Fé, Argentina, ISBN 978-950-9770-02-7, pp163-172, setiembre 2008.
Internet:	http://www.di-mare.com/adolfo/p/lkptr.htm       Google™ Translate
Versión CLEI-2008:	http://www.di-mare.com/adolfo/p/lkptr-CLEI-2008.pdf       Google™ Translate http://www.di-mare.com/adolfo/p/lkptr-CLEI-2008-ppt.pdf       Google™ Translate http://www.clei2008.org.ar/
Autor:	Adolfo Di Mare <adolfo@di-mare.com>
Contacto:	Apdo 4249-1000, San José Costa Rica Tel: (506) 2511-8000       Fax: (506) 2438-0139
Revisión:	ECCI-UCR, Junio 2007
Visitantes: