Serializar struct con punteros a NSData

Question

Necesito agregar algún tipo de funcionalidad de archivo a una implementación de Objective-C Trie (NDTrie en github), pero tengo muy poca experiencia con C y sus estructuras de datos.

struct trieNode 
{ 
    NSUInteger key; 
    NSUInteger count, 
    size; 
    id object; 
    __strong struct trieNode ** children; 
    __strong struct trieNode * parent; 
}; 

@interface NDTrie (Private) 
- (struct trieNode*)root; 
@end 

Lo que necesito es crear una NSData con la estructura de árbol de la raíz - o serializar/deserializar el árbol entero de alguna otra manera (? Conforme a NSCoding), pero no tengo ni idea de cómo trabajar con NSData y una estructura C que contiene punteros.

El rendimiento en la deserialización del objeto resultante sería crucial, ya que este es un proyecto de iPhone y tendré que cargarlo en segundo plano cada vez que se inicie la aplicación.

¿Cuál sería la mejor manera de lograrlo?

Gracias!

Answer 1

Asumiendo que requiere para seguir con C recta, porque así es como las cosas ya están configurados, lo que necesita hacer es realmente bastante simple .

Simplemente escriba una función C para escribir su árbol en el disco, con algunas suposiciones sobre el pedido (por ejemplo, escríbalo primero nuestra profundidad, de izquierda a derecha). Para cualquier objeto Objective-C, codifíquelos en NSData y escriba el tamaño y los bytes de estos como parte de la secuencia.

Cuando vuelva a leer los datos, simplemente reconstruya el árbol en función de los supuestos de su pedido y configure los punteros a los niños. Desarchive cualquiera de los objetos integrados Objective-C según corresponda.

Probablemente pueda hacer esto con NSCoder de alguna manera, pero podría ser más fácil hacer la reconstrucción de árbol fuera de eso, ya que puede recurse por el árbol pasando los argumentos que desee, lo cual no es realmente fácil con NSCoding.

Tengo un código (Desktop OS X) que hace algo muy similar a esto, sin los objetos incrustados, pero es bastante complicado, y no puedo publicarlo.

Una optimización en ese código es leer los datos en un búfer interno, en fragmentos de MB (en lugar de un pequeño número de bytes a la vez, para cada estructura), y luego leer los datos de ese búfer, aunque No estoy seguro de que haya sido alguna vez referenciada, y en cualquier caso puede o no hacer una diferencia significativa en el iPhone. Parece que también hay una optimización similar para la escritura, que es más probable que sea una victoria, según tengo entendido (las escrituras de iPhone son caras, o al menos eso he escuchado).

Answer 2

Usted siempre debe tratar de la manera más fácil primero:

// serializing: 
[myTrie writeToFile:myPath atomically:NO]; 

// deserializing 
NDTrie* myTrie = [NDTrie trieWithContentsOfFile:myPath]; 

Si eso no es realmente lo suficientemente rápido, se puede mirar en la serialización de forma manual las estructuras subyacentes.

Editar:

Se hizo evidente que la cantidad de datos requiere una implementación optimizada.

Propongo reescribir la estructura trieNode y acceder a métodos para usar índices en lugar de punteros para los campos parent y children. Los índices apuntan hacia una gran matriz C de estructuras trieNode, desde donde se asignan todos los nodos.

Esta matriz C se podría mantener en un objeto NSData en el objeto NDTrie de envoltura. Serialización y deserialización simplemente significaría guardar/cargar el objeto NSData (problemas de endiabilidad a un lado).

Answer 3

Vuelva a implementar la estructura del nodo trie como una clase Objective C. p.ej.

@interface TrieNode 
{ 
    NSUinteger key; 
    NSUInteger count; 
    //NSUInteger size; // not needed if you use an NSArray for the children. 
    id object; 
    NSArray* children; 
    TrieNode* parent; 
} 
// methods 
@end 

Luego puede usar el mecanismo estándar Objective-C para archivar y desarchivar estos objetos.

Si después de implementar el anterior y perfilando su código, observa que el rendimiento es un problema, puede comenzar a optimizar. Por ejemplo, accediendo a ivars usando C struct pointer stuff, p.

aTrieNode->parent; 

o sustituyendo el NSArray con una matriz C, etc.

Answer 4

Creo que debe implementar el protocolo NSCoding: en su initWithCoder: cree un NSArray con todos children y realloc una matriz de este tipo en encodeWithCoder:.

De esta forma, podrá utilizar la matriz original de struct en el resto del proyecto.