Augmenter un pointeur struct avec la moitié de la taille de la structure

Question

Je viens de recevoir un problème intéressant à régler, et je ne vois pas de moyen facile de le résoudre.

J'ai deux structures de données de base qui représente un graphique complexe, a déclaré quelque chose comme ceci:

typedef struct _node_t node_t; 
typedef struct _graph_t graph_t; 

struct { 
    /* Data fields omitted */ 
    node_t * pNextByLevel; 
    node_t * pNextByProximity; 
    node_t * pNextByRank; 
} node_t; 

struct { 
    /* Data fields omitted */ 
    size_t nNodes; 
    size_t nMaxNodes; 
    node_t * pFirstByLevel; 
    node_t * pFirstByProximity; 
    node_t * pFirstByRank; 
} graph_t; 

Les nœuds réels sont disposés immédiatement après l'en-tête, donc un « graph_t » est normalement créé avec

graph_t * pNewBuffer = calloc(1, sizeof(graph_t) + nMaxNodes * sizeof(node_t)); 
pNewBuffer->nMaxNodes = nMaxNodes; 

et le réseau "brute" de noeuds est accessible avec

node_t * pNewBufferNodes = (node_t *) &pNewBuffer[1]; 

Maintenant, il existe une fonction de support qui fonctionne sur un tampon qui réduit le nombre de nœuds. Il ressemble à ceci:

status_t reduce(graph_t** ppBuffer) 
{ 
    graph_t * pReplacement, * pOld = *ppBuffer; 
    size_t nRequired; 
    node_t * oldBuffer = (node_t *) &pOld[1]; 

    /* complex calculation ultimately computes 'nRequired' */ 

    pReplacement = realloc(pOld, sizeof(graph_t) + nRequired * sizeof(node_t)); 

    if (pReplacement != pOld) 
    { 
     int i; 
     node_t * newBuffer = (node_t *) &pReplacement[1]; 
     ptrdiff_t offset = newBuffer - oldBuffer; 

     for (i = 0; i < requiredNodes; i++) 
     { 
      newBuffer[i].pFirstByLevel += offset; 
      newBuffer[i].pFirstBySimilarity += offset; 
      newBuffer[i].pFirstByRank += offset; 
     } 
     *ppBuffer = pReplacement; 
    } 
} 

Maintenant, cela a fonctionné magnifiquement pendant longtemps. Toute erreur dans ce qui précède vient du fait que j'écris de mémoire, j'essaie juste d'expliquer l'idée. Ce qui me déroute en ce moment, c'est que lorsque j'utilise la fonction de réduction d'un nouveau module, l'entrée n'est pas "correctement" alignée. Lorsque j'examine les adresses, je note les propriétés suivantes:

((char *) newBuffer - (char *) oldBuffer) % sizeof(graph_t) == 0 
((size_t) newBuffer) % sizeof(node_t) == 0 
((size_t) oldBuffer) % sizeof(node_t) == 0 
((char *) newBuffer - (char *) oldBuffer) % sizeof(node_t) == sizeof(node_t)/2 

qui, bien sûr, fait un peu de problème puisque la valeur « décalage » est incorrecte, mais il est pas évident puisque toute autre utilisation des données les structures fonctionnent (il n'y a pas de problème d'alignement "réel").

Ce qui revient à ma question - Voyez-vous une façon intéressante d'incrémenter les pointeurs lorsque le décalage ne peut pas être exprimé en nombre entier d'éléments?

points de bonus pour trouver un moyen qui ne recourt pas à la coulée excessive :)

Answer 1

Sur ptrdiff_t. « Ceci est le type retourné par l'opération de soustraction entre deux pointeurs Ceci est un type intégral signé, et en tant que telle peut être converti en types de données fondamentaux compatibles.Une soustraction de deux pointeurs est seulement accordée pour avoir une valeur définie valide pour les pointeurs vers les éléments du même tableau (ou pour l'élément juste après le dernier dans le tableau). le comportement dépend des caractéristiques du système et de l'implémentation du compilateur. "

Lorsque vous utilisez realloc, vous n'êtes pas dans ce cas. Donc, votre décalage ne sera pas un int. Cela explique votre problème.

La solution sans points bonus consiste à lancer vos pointeurs sur char * pour calculer le décalage. Vous obtiendrez un décalage en octets. Vous pouvez ensuite ajouter le décalage d'octets à l'aide de moulages. Pour minimiser la diffusion, vous pouvez écrire une fonction d'assistance qui définit la valeur correcte pour vos pointeurs de nœud.

Si vous voulez utiliser realloc, je ne vois pas d'autre solution, car le tableau initial a été libéré par realloc. L'offset des octets semble le seul moyen.

Vous pouvez appeler votre tableau réduit, copier les noeuds, puis libérer l'ancien tableau. Mais vous perdez l'avantage de Realloc lorsque la réallocation est faite en place.

D'autres solutions vous forcent à modifier votre structure de données. Vous pouvez allouer vos nœuds indépendamment avec malloc et la réduction est plus simple. Vous n'avez plus qu'à libérer les nœuds dont vous n'avez plus besoin.Cela semble le moyen le plus propre, mais vous devez refactoriser ...

J'espère que cela aide. Dites-moi si je l'ai mal compris ...

Answer 2

Si vous ne voulez pas jeter:

newBuffer[i].pFirstByLevel = newBuffer[i].pFirstByLevel - oldBuffer + newBuffer;    
newBuffer[i].pFirstBySimilarity = newBuffer[i].pFirstBySimilarity - oldBuffer + newBuffer;    
newBuffer[i].pFirstByRank = newBuffer[i].pFirstByRank - oldBuffer + newBuffer; 

Answer 3

Votre syntaxe est foiré. Le nom de l'étiquette de structure précède la définition de la structure; tout ce qui suit est une déclaration.

Soit

typedef struct _node_t { 
    /* Data fields omitted */ 
    node_t * pNextByLevel; 
    node_t * pNextByProximity; 
    node_t * pNextByRank; 
} node_t; 

ou

typedef struct _graph_t graph_t; 
struct _graph_t { 
    /* Data fields omitted */ 
    size_t nNodes; 
    size_t nMaxNodes; 
    node_t * pFirstByLevel; 
    node_t * pFirstByProximity; 
    node_t * pFirstByRank; 
}; 

serait ce que vous vouliez écrire.

---

Cette solution de contournement est relativement courante, mais nécessite une restructuration de votre code existant.

/* same node_t as before */ 
typedef struct _node_t {...} node_t; 
/* same graph_t as before */ 
typedef struct _graph_header_t {...} graph_header_t; 
/* new type */ 
typedef struct _graph_t { 
    graph_header_t header; 
    node_t nodes[1]; 
} graph_t; 

graph_t pNewBuffer = calloc(1, sizeof(graph_t) + (nMaxNodes-1) * sizeof(node_t)); 

Il permet d'accéder à pNewBuffer->nodes[i] pour 0 <= i < nMaxNodes, pas coulée nécessaire partout. Maintenant, ce serait plus agréable si vous pouviez déclarer node_t nodes[0], en évitant les off-on lors du calcul des tailles d'allocation, mais même si certains compilateurs sont satisfaits, je ne crois pas que cela soit accepté par la norme.

C99 présente « membres du groupe » flexibles

typedef struct _graph_t { 
    graph_header_t header; 
    node_t nodes[]; 
} graph_t; 

qui est à peu près la même chose, mais définie par une norme réelle. Quelques exceptions: les membres de tableau flexibles ne peuvent être placés qu'à la fin d'une structure, et sizeof(pNewBuffer->nodes) n'est pas valide (bien que GCC renvoie 0). Sinon, sizeof(graph_t) est égal à n'importe quelle taille si le tableau node_t[] avait zéro élément.