resueltos - ¿Se puede implementar una lista vinculada XOR en C++ sin causar un comportamiento indefinido?

listas enlazadas en c++ codigo fuente

Question

Una lista vinculada XOR es una versión modificada de una lista doblemente enlazada normal en la que cada nodo almacena solo un "puntero" en lugar de dos. Ese "puntero" se compone del XOR de los punteros siguiente y anterior. Para recorrer la lista, se necesitan dos punteros: uno para el nodo actual y uno para el nodo siguiente o anterior. Para avanzar, la dirección del nodo anterior es XORed con el "puntero" almacenado en el nodo actual, revelando el verdadero puntero "siguiente".

El estándar C ++ hace que un conjunto de operaciones en punteros y enteros den como resultado un comportamiento indefinido; por ejemplo, no se puede garantizar que establecer un bit en particular en un número no provoque que el hardware active una interrupción, por lo que en algunos casos los resultados del bit twiddling puede ser indefinido.

Mi pregunta es la siguiente: ¿hay una implementación en C ++ de una lista vinculada XOR que no dé como resultado un comportamiento indefinido?

Answer 1

Mi pregunta es la siguiente: ¿hay una implementación en C ++ de una lista vinculada XOR que no dé como resultado un comportamiento indefinido?

Si por "hay una implementación" quiere decir "ya se ha escrito", entonces no sé. Si quiere decir "¿es posible escribir uno?", Entonces sí, pero puede haber algunas advertencias sobre la portabilidad.

Puede convertirlo en dos uintptr_t si convierte ambos punteros a uintptr_t antes de comenzar y almacena ese tipo en el nodo en lugar de un puntero. Las operaciones bit a bit en tipos sin firmar nunca resultan en un comportamiento indefinido.

Sin embargo, uintptr_t es un tipo opcional, por lo que no es totalmente portátil. No hay ningún requisito de que una implementación C ++ en realidad tenga un tipo entero capaz de representar una dirección. Si la implementación no tiene uintptr_t , el código puede compilar con un diagnóstico, en cuyo caso su comportamiento está fuera del alcance del estándar. No estoy seguro si considera que una infracción de "sin UB" o no. Quiero decir, en serio, ¿un compilador que permite código que usa tipos indefinidos? ;-)

Para evitar uintptr_t , creo que podrías hacer tus uintptr_t bits en una matriz de caracteres sin signo sizeof(node*) lugar. Los punteros son tipos POD y, por lo tanto, pueden copiarse, centrifugarse y mutilarse siempre que la representación del objeto se restaure a su estado original antes de usarse como puntero.

Tenga en cuenta también que si su implementación C ++ tiene un recolector de elementos no utilizados, entonces convert-to-integer / xor / xor-back-again / convert-to-puntero no necesariamente detiene el objeto que se recopila (porque da como resultado un "derivado inseguro" puntero"). Por lo tanto, para la portabilidad también debe asegurarse de que los punteros resultantes sean válidos. Dos formas de hacer esto:

1. llama declare_reachable en ellos.
2. Utilice una implementación con seguridad de puntero relajado (está definida en la implementación si este es el caso, y puede probarla con get_pointer_safety() teniendo en cuenta que una implementación relajada puede afirmar falsamente que es estricta).

Podrías pensar que hay una tercera vía (aunque una que derrota el propósito de la lista vinculada de XOR, a menos que de todos modos la tengas):

• mantener un contenedor separado de todos los valores del puntero

Esto no está garantizado para funcionar . Un puntero derivado inseguro no es válido incluso si resulta ser igual a un puntero derivado de forma segura (3.7.4.3/4). Yo también estaba sorprendido.