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

Como esconder datos en punteros

Resumen   

Introducción   

      Después de escribir la implementación de la lista parametrizable para el lenguaje C descrita en [DiM-1999] traté de implementar una función equivalente al método cl_next(), que avanza un puntero "p" al siguiente nodo de la lista, pero evitando usar como argumento del método a la lista "L".

cl_link* cl_next (const clist *L, cl_link *p) {
    /*==========================================*\
    | Returns the position that comes after "p"  |
    | - After the last position, returns NULL.   |
    \*==========================================*/

    return ( p ==  L->last ? NULL : p->next );
} /*              ~~~                         */

    /* tomado de clist.h y clist.c en [DiM-1999] */

      En el Listado 1 está la implementación de cl_next(), que usa el parámetro "L" para determinar si el puntero "p" denota el último nodo de la lista, en cuyo caso el valor siguiente a retornar debe ser el puntero nulo NULL. La desventaja de usar a "L" como parámetro es que no es posible trasliterar esta implementación a C++, cambiando los punteros de tipo "cl_link" por iteradores similares a los usados en la biblioteca estándar del lenguaje C++, STL [Standard Template Library] [Mus-1994], pues para los iteradores STL siempre debe ser posible calcular el siguiente nodo al que referencia el iterador por medio el operador de incremento "++" (mediante la sobrecarga de "list::iterator::operator++()"), por lo que en la implementación del operador "++" nunca se utiliza como argumento la lista.

template <class T, class A = allocator<T> >
class list {
    class node {
        node *_next, *_prev;
        T     _val; // valor almacenado
        // ...
    }; // node
    class iterator {
        node *_p;
    public:
        iterator& operator++() {    // ++p
            this->_p = _p->_next;
            return *this;
        }
        iterator  operator++(int);  // p++
        // ...
    }; // iterator
    iterator end() { return 0; }
    // ...
}; // list

      En el Listado 2 está el prototipo de la operación "++" de una lista STL, la que tiene el mismo efecto que cl_next() en una lista parametrizable para el lenguaje C. La razón por la que los iteradores de los contenedores STL no necesitan como argumento al contenedor es que, para recorrer un contenedor, se usan dos iteradores, y el segundo denota a un valor que está "fuera" del contenedor ("end()"). Ocurre que los iteradores para las listas STL en realidad son punteros disfrazados [Nel-1995].

container C;
container::iterator p;

for (p=C.begin(); p != C.end(); p++) {
    cout << (*p); // p.operator*()
}

      En el Listado 3 se muestra la forma en que un programador cliente de la biblioteca STL recorre un contenedor "C", para procesar todos los valores en él almacenados. Para el operador de avance "++" no se requiere usar al contenedor "C" como argumento, pues el iterador "end()" denota a un valor que ya no está dentro del contenedor.

 L ──>─┐
       │
       v
┌────────┬───┐   ┌────────┬───┐   ┌────────┬───┐
│ elem_1 │ *─┼──>│ elem_2 │ *─┼──>│ elem_3 │ *─┼─> NIL
└────────┴───┘   └────────┴───┘   └────────┴───┘

      En la Figura 1 se muestra el diagrama, o modelo, de una lista en la que el último nodo apunto al puntero nulo NIL==0. Si el método operator++() del iterador lo que hace es avanzar hacia el siguiente nodo, cuando se está en el último, el valor retornado será 0, el valor que invariablemente retorna list::iterator::end(). En este caso nunca es necesario usar el puntero que contiene la lista "L" para avanzar, con un iterador, al siguiente nodo.

 L->last ───────────────────────────────────────┐
                                                │
┌────────────┐   ┌────────────┐   ┌───────────┐ │
│            v   │            v   │           v v
│ ┌────────┬───┐ │ ┌────────┬───┐ │ ┌────────┬───┐
│ │ elem_1 │ ├─┼─┘ │ elem_2 │ ├─┼─┘ │ elem_3 │ ├─┼─┐
│ └────────┴───┘   └────────┴───┘   └────────┴───┘ │
│            ^               next              ^   │
│            │                                 │   │
│          first                             last  v
└───────<───────────────<────────────────<─────────┘

      En la Figura 2 se muestra cómo está implementada la lista circular descrita en [DiM-1999]: el último nodo apunta al primero, y la lista contiene un puntero al último nodo. De esta manera es posible insertar valores, tanto al principio de la lista como al final, en una cantidad constante de tiempo O(1). Sin embargo, si un puntero "p" denota algún nodo de la lista, no hay forma de saber cuándo "p" denota el último nodo, lo que hace imposible usar esta lista como base para una implementación de una lista STL, de acuerdo a la especificación del Listado 2, pues no es posible implementar el operador de avance "++".

      Para implementar el operador de avance del iterador, es necesario incluir un campo adicional en cada nodo de la lista, para que el iterador pueda examinarlo y determinar si ha llegado o no al final de la lista.

template <class T, class A = allocator<T> >
class list {
    class node {
        node *_next, *_prev;
        T     _val;
        bool  _marked;  // ¿puntero final?
        // ...
    }; // node
    class iterator {
        node *_p;
    public:
        iterator& operator++() {    // ++p
            _p = (_p->_marked ? 0 : _p->_next);
            return *this;
        }
        // ...
    }; // iterator
    iterator end() { return 0; }
    // ...
}; // list

      En el Listado 4 se muestra que al nodo se le ha agregado el campo "_marked", que indica si el nodo está marcado como el nodo final. Para implementar la operación de avance del iterador basta verificar si el nodo apuntado está marcado, en cuyo caso lo que procede es retornar el puntero nulo "0". Esta solución es efectiva, pero requiere engrosar el tamaño del nodo con un campo booleano adicional.

      Como los nodos "list::node" siempre están alineados en frontera de palabra, su dirección siempre será una dirección par, de manera que todos los punteros que apuntan a un nodo siempre tendrán un cero en su último bit. En ese bit se puede almacenar un valor booleano si se tiene el cuidado de restablecerlo a cero antes de derreferenciar el puntero. Por eso, otra solución más eficiente en términos de espacio es almacenar dentro del puntero "_p" que contiene cualquier iterador el valor booleano "_marked". Para saber si el iterador apunta al último nodo, bastará invocar la operación "_p.marked()".

La solución ptrbit   

      Así como un iterador en la mayoría de los casos encapsula un puntero, pues en su interfaz ofrece las operaciones de punteros, para crear un puntero que mantiene almacenado un valor booleano en su bit menos significativo hay que usar una clase, en la que por sobrecarga estén disponibles las operaciones que caracterizan a los punteros.

template <class T> class pointer {
    T *_p;  // el puntero
public:
    pointer()                      {};
    pointer(T* p)       : _p(p)    {};
    pointer(pointer &o) : _p(o._p) {};
    pointer& operator++()      { ++_p;  return *this; } // ++p 
    pointer& operator--()      { --_p;  return *this; } // --p
    pointer  operator++(int)   { pointer<T> o = *this;  // p++
             this->operator++();        return o; }
    pointer  operator--(int)   { pointer<T> o = *this;  // p--
             --(*this);                 return o; }
    pointer& operator+=(int i) { _p+=i; return *this; }
    pointer& operator-=(int i) { _p-=i; return *this; }
    pointer& operator=(pointer p) { _p = p._p;
                                        return *this; }
    friend int operator==(pointer, pointer);
    friend int operator!=(pointer, pointer);
    friend unsigned long operator-(pointer, pointer);
    T& operator*() { return *_p; }  // derreferencia
    operator int() { return _p!=0; }
}; // pointer

      En el Listado 5 se muestran las operaciones que caracterizan a un puntero: inicialización, incremento, asignación, comparación, diferencia, derreferencia y conversión. La clase "pointer" está definida como una plantilla para facilitar su uso. Para que el bit menos significativo de un puntero almacene un valor booleana hay que cambiar la implementación de cada una de estas operaciones.

/* ptrbit.h      v1.0  (C) 2000 adolfo@di-mare.com */

#ifndef   PTRBIT_H
#define   PTRBIT_H

class ptrbit {
public:
    ptrbit() {}
    ptrbit(      void*   x) : _p(x)    {}
    ptrbit(const ptrbit& x) : _p(x._p) {}

    void* operator=(void* x) { return (_p = x); }

    void* ai() const { return _p; } // ai() ==> As Is
    void* vp() const {              // vp() ==> Void Pointer 
        return (void*) ((unsigned long)_p & ~1UL); }

    void set(void* p) { _p = p; }

    int  marked() { return (int)((unsigned long)_p & 1UL); }
    void mark()   { (unsigned long)_p |=  1UL;  }
    void unmark() { (unsigned long)_p &= ~1UL; }

    static int aligned(const void *p)
        { return 0 == ((unsigned long)p & 1UL); }
private:
    void operator*()  {}             // forbid dereferencing
    operator void*()  { return _p; } // forbid conversion
private: // ptrbit member fields
    void *_p;
}; // ptrbit

inline int operator==(const ptrbit& x, const ptrbit& y) {
    return x.ai() == y.ai(); }
inline int operator!=(const ptrbit& x, const ptrbit& y) {
    return !(x == y); }

// This implementation requires long to hold a pointer
class ptrbit_check_that_long_holds_a_void_pointer__ {
    char _[sizeof(unsigned long) == sizeof(void*)];
};

#endif /* PTRBIT_H */

/* EOF:   ptrbit.h */

      El Listado 6 es la clase "ptrbit", la que provee las operaciones necesarias para, que en el bit menos significativo del puntero que contiene, se pueda almacenar un valor booleano. Por brevedad, a la clase "ptrbit" sólo tiene los operadores necesarios para implementar la lista circular "clistfT<T>". Tampoco se han usado plantillas, para mostrar otra forma de hacer las cosas, pero es sencillo derivar de "ptrbit" una plantilla general similar a la de la clase "pointer<T>" del Listado 5.

      El método "ai()" ("As Is") sirve para obtener, desde una clase cliente, el valor almacenado en el puntero sin borrar a cero el bit menos significativo, en contraposición al método "vp()" que sí pone el cero el bit, lo que se logra usando el operador C++ de bits "|" con la máscara binaria "~1" que tiene unos binarios menos en el bit menos significativo. El método "set()" sirve para cambiar el valor del puntero. Los métodos "mark()" "unmark()" "marked()" sirven para obtener el valor booleano almacenado en el puntero. Se supone que el valor "V" al que apunta un variable "ptrbit" siempre está alineada, o sea, que su dirección hace verdadera la expresión ptrbit::aligned(&V).

      A diferencia de las listas tradicionales, como las usadas en la biblioteca STL, la lista circular clistfT<T> tiene la particularidad de que todas las instancias de la lista siempre usan el mismo código objeto en su implementación (salvo para las operaciones "inline"). Por eso la clase "clistfT<T>" está implementada en dos archivos: el de encabezado clistf.h que es tradicional en C++, y también un archivo de implementación clistf.cpp que contiene los algoritmos más importantes de la lista. En esta implementación se usan las ideas expuestas en [DiM-1999] de implementar la lista uniendo campos de enlace, en lugar de unir sus nodos. El diagrama de la Figura 2 se muestra esto.

#include "ptrbit.h"

class clistf {     // circular list
public:
    class list_link;
    class itr : public ptrbit {
    public:
        friend class clistf; friend class list_link;
    clistf() : _last(0) {};
        itr() {}
        itr(itr       &o) : ptrbit (         o ) {}
        itr(list_link *o) : ptrbit ( (void*) o ) {}

        itr& operator++();     // ++i
        itr  operator++(int) { // i++
            itr tmp = *this;
            this->operator++(); // ++*this;
            return tmp;
        }
        itr prev();
    protected:
        list_link * ai() { return (list_link*) (ptrbit::ai()); }
        list_link * um() { return (list_link*) (ptrbit::vp()); }
        void operator=(list_link *x) { set( (void*) x); }
        void operator=(itr       &x) { set ( x.ai()  ); }
    }; // itr

    class list_link {
        itr next;
    public:
        list_link() {}
        friend class clistf; friend class itr;
    };

    unsigned count();
    int empty() { return _last == end(); }
    int valid(itr);

    void link_after(  itr where, list_link &what);
    itr  unlink_after(itr where);

    void push_front(list_link &what) { link_after(0, what); }
    void push_back( list_link &what) { link_after(_last, what); }

    itr last()  { return _last; }
    itr begin();
    itr end()   { return 0; }
    itr nth(unsigned n);

    unsigned pos(itr i);
private:
    clistf(const clistf&) : _last(0) {}   // forbid copy
    void   operator=(const clistf&)  {}

private:       // member fields
    itr _last; // points to last, last points to first
}; // clistf

      La clase clistf, que se muestra en el Listado 7 tiene las operaciones más importantes de la lista, como inserción y borrado, y también operaciones para avanzar y retroceder entre los valores de la lista usando iteradores. La clase "itr" provee iteradores similares a los usados en la biblioteca STL. La clase privada "list_link" es el nodo de la lista.

inline clistf::itr clistf::begin() {
    return (_last.ai() == 0 ? 0 : _last.um()->next.um());
}

inline clistf::itr& clistf::itr::operator++() { // ++i
    set (ai()->next.ai());
    if (this->marked()) {
        set(0);
    }
    return *this;
}

      En el Listado 8 está la implementación de la operación "++itr" de los iteradores, que sirve para avanzar un iterador al siguiente nodo de la lista. Aquí se usa el método "ptrbit::set()" para cambiar el valor del puntero que contiene el iterador, de manera que apunte al siguiente nodo de la lista. Como la operación de incremento se ejecuta únicamente cuando el iterador todavía apunta a un nodo de la lista, entonces el puntero que el iterador contiene nunca es un puntero marcado como el último puntero de la lista. Por eso, al obtener el valor del puntero, se usa el método "ptrbit::ai()" que no trata de borrar el último bit del puntero, el que necesariamente no puede estar prendido.

      En esta implementación de la lista hay que tomar en cuenta que el último puntero de la lista, que a su vez apunta al primer nodo, es un puntero especial, "marcado". Como ese puntero está marcado, al avanzar hacia el siguiente nodo siempre es posible determinar si se ha llegado al final de la lista: si el puntero no tiene el bit menos significativo prendido, entonces el iterador corresponde a un nodo intermedio de la lista, pues sólo el campo "next" del último nodo contiene un puntero marcado.

      Como la lista es circular (ver Figura 2), si el iterador apuntaba al último nodo, al avanzar hacia el nodo siguiente se obtendrá un puntero al primer nodo, más ese puntero sí estará marcado en su último bit. Por eso, si al avanzar el puntero del iterador se obtiene un puntero marcado, esto indica que ya ha se cruzado desde el último nodo al primero, por lo que el operador de avance del iterador debe retornar, no un puntero al primero nodo de la lista, sino el valor "0" que es lo que "clistf::end()" siempre retorna.

#include <stddef.h> // offsetof()

template <class T>
class clistfT : public clistf {
private:
    struct node {
       T         e;  // element
       list_link lk; // link field for the list

       node(T& n) : e(n), lk() {}
    }; // node

public:
    class iterator : public itr {
        friend class clistfT;
    public:
        iterator()             : itr ( ) {}
        iterator(itr &o)       : itr (o) {}
        iterator(list_link *o) : itr (o) {}
        void operator=(itr &x)  { itr::operator=(x); }

private:
       node* np() {  // Node Pointer
           return ((node*)((char*)vp() - offsetof(node, lk)));
       }
public:
        T& operator*() { return np()->e; }
    }; // iterator

public:
    ~clistfT() {
        while (!empty()) {
            iterator i = unlink_after(0);
            delete i.um();
        }
    }
}; // clistfT<T>

      La clase clistf no es una plantilla, pues ha sido construida de manera que cualquier lista, independientemente del tipo de datos que almacene, use el mismo código objeto para implementar sus operaciones. La implementación de las operaciones de la lista está en el archivo "clistf.cpp", y es común a todas las listas. En el Listado 9 se muestra la clase clistfT<T>, derivada de clistf, que en realidad es una envoltura alrededor de la clase clistf. Lo mismo ocurre con la clase clistfT<T>::iterator, que está derivada de clistfT<T>::itr. El nodo de clistfT<T> contiene el campo de enlace "lk" que se necesita para enlazar todos los valores de una clistf, y además exporta el método "T& iterator::operator*()" que sirve para tomar un iterador y, mediante el operador de derreferencia "*", obtener el valor almacenado en la lista. Para hacer esto, es necesario ajustar el puntero que contiene el iterador, que apunta la campo de enlace, y trasladarlo para que apunte al principio del nodo de clistfT<T>. Este trabajo lo hace la operación "np()" (Node Pointer) usando la macro "offsetof()".

 ┌────────┬───┐
 │  1999  │ ├─┼─> next
 └────────┴───┘
 ^          ^
 │          │
pInt      pHere

      Las versiones de la lista se obtienen al instanciar la plantilla clistfT<T>. La forma en que se logra que todas las versiones de la lista compartan la misma implementación de las operaciones es implementar las operaciones de manera que manipulen los campos de enlace de la lista, en lugar de que manipulen nodos completos. La operación "np()" lo que hace es transformar un puntero a un campo de enlace, en un puntero al nodo: por eso tiene que restarle al puntero del iterador el desplazamiento al que se encuentra el campo de enlace desde el principio del nodo, como se muestra en la Figura 3. En [DiM-1999] se encuentra una discusión detallada de como lograr compartir la implementación de los métodos de la lista.

¿Cuántos bits aprovechar?   

      Como la mayor parte de los objetos que residen de la memoria dinámica quedan alineados en frontera de doble palabra, y como la mayoría de los computadores actuales tiene procesadores de 32 bits o más, es lógico tratar de usar los dos últimos bits de un puntero para almacenar dos valores booleanos independientes.

class ptrbit {
    // ...
public:
    void* vp() const { return (void*) ((long)_p & ~(1L+2L)); }

    int  marked() { return (int)((unsigned long)_p & 1UL); }
    void mark()   { (unsigned long)_p |=  1UL;  }
    void unmark() { (unsigned long)_p &= ~1UL; }  // bit 0

    int  checked() { return (((unsigned long)_p & 2L)?1:0); }
    void check()   { (unsigned long)_p |=  2L;  }
    void uncheck() { (unsigned long)_p &= ~2L; }  // bit 1
    int bit(int n) {
        return ( n==0 ? marked() : checked() );
    }
    void bit(int n, int v) {
        (n == 0 ? ( v==0 ? unmark()  : mark()  )
                : ( v==0 ? uncheck() : check() ) ); }

    static int aligned(const void *p)
        { return 0 == ((unsigned long)p & (1L+2L)); }
    // ...
}; // ptrbit

      En el Listado 10 se muestran una parte de la implementación de la clase ptrbit para almacenar dos valores booleanos al final de un puntero. Si un programador quiera usar más bits del puntero debe ser cuidadoso, pues muchas veces los punteros apuntan a campos que se encuentran dentro de un objeto, los que no necesariamente están en frontera de palabra de 32 bits. En general es complicado programar usando punteros, y será más difícil hacerlo si se usan punteros "decorados". Pero en algunas ocasiones vale la pena hacer el esfuerzo adicional, como se ocurre al implementar la lista circular que se ha mostrado en este artículo.

Otra aplicación: Árboles Roji-Negros   

ptrbit <class Key, class Ty, class Kf, class P, class A>

class tree {
    typedef typename
        A::rebind<void>::other::pointer Genptr;
    enum redblack { Red, Black }; // bit values

    struct Node {
        Genptr   Left;
        Genptr   Parent;  // the pointers
        Genptr   Right;
        redblack Color;   // node color
        Ty       Value;   // info field
    };
   // more stuff deleted...
}; // tree

      También se puede usar la clase ptrbit para mejorar la implementación de los contenedores asociativos de la biblioteca STL, cuya implementación generalmente se hace usando un árbol roji-negro. Los nodos de este tipo de árbol deben estar decorados por un valor, que se implementa usando un campo de tipo "Color" en el que se almacena uno de dos valores: red o black [Sha-1998], como se muestra en el extracto de la clase "tree" en el Listado 11. Como este campo sólo puede tomar dos valores, se puede implementar usando una variable booleana. Una forma de reducir el tamaño del nodo es eliminar el campo "redblack", y en consecuencia hay que almacenar su valor en alguno de punteros del nodo.

      Para eliminar el campo "redblack" no se puede cambiar el campo "Value" del nodo, pues es campo lo usa el programador cliente de la clase y en él no se puede almacenar ningún valor. Por eso no queda otra que codificar el color del nodo en el bit menos significativo del puntero que apunta al nodo, en el campo "Left" o "Right".

      Los algoritmos de manipulación de los nodos del árbol deben ser modificados, para que tomen el color del nodo, que antes estuvo almacenado en el campo "redblack", del bit menos significativo del puntero que apunta al nodo. Aunque hacer esta modificación en los algoritmos no es difícil, sí es tedioso. Para ajustar los algoritmos, ayuda trabajar con una clase derivada de "ptrbit" que permita usar verificación fuerte de tipos, la que se puede obtener derivando de "ptrbit" una clase similar a la clase "pointer<T>" del Listado 5.

Conclusión   

      Es posible almacenar datos en los bits menos significativos de un puntero, lo que puede ayudar a mejorar la eficiencia de algunos algoritmos. El programador debe sopesar el incremento en eficiencia del uso de espacio con el aumento en la complejidad de los algoritmos que usar punteros decorados con valores booleanos comporta.

Reconocimientos   

      Esta investigación se realizó dentro del proyecto de investigación 326-98-391 "Polimorfismo uniforme más eficiente", inscrito ante la Vicerrectoría de Investigación de la Universidad de Costa Rica. La Escuela de Ciencias de la Computación e Informática también ha aportado fondos para este trabajo.

Bibliografía   

Índice   

[-]	Resumen
[-]	Introducción
[-]	La solución ptrbit
[-]	¿Cuántos bits aprovechar?
[-]	Otra aplicación: Árboles Roji-Negros
[-]	Conclusión
[-]	Reconocimientos
	Bibliografía
	Índice
	Acerca del autor
	Acerca de este documento
	Principio Índice Final

Acerca del autor   

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

Acerca de este documento   

Reference:	Di Mare, Adolfo: Como esconder datos en punteros, Revista de Ingeniería, Facultad de Ingeniería, Universidad de Costa Rica, pp [81-91], 2000.       http://www.di-mare.com/adolfo/p/ptrbit.htm
Internet:	http://www.di-mare.com/adolfo/p/ptrbit.htm http://www.inii.ucr.ac.cr/base_revistas/index.php/ingenieria/article/download/257/189 http://www.di-mare.com/adolfo/p/src/ptrbit.h http://www.di-mare.com/adolfo/p/src/clistf.h http://www.di-mare.com/adolfo/p/src/clistf.cpp http://www.di-mare.com/adolfo/p/src/pointer.h
Autor:	Adolfo Di Mare <adolfo@di-mare.com>
Contacto:	Apdo 4249-1000, San José Costa Rica Tel: (506) 207-4020       Fax: (506) 438-0139
Revisión:	ECCI-UCR, Abril 2000
Visitantes: