Увеличьте указатель структуры с половиной размера структуры

Question

У меня просто возникла интересная проблема, о которой я забочусь, и я не вижу аккуратного способа ее решения.

У меня есть две структуры базы данных, которая представляет собой сложный график, заявил что-то вроде этого:

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; 

Фактические узлы раскладывают сразу после заголовка, так «graph_t» обычно создается с

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

и "сырой" массив узлов доступа с

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

Теперь существует функция поддержки, которая работает с буфером, который уменьшает количество узлов. Это выглядит примерно так:

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; 
    } 
} 

Теперь это прекрасно работает в течение длительного времени. Любые ошибки в вышесказанном возникают из-за того, что я пишу из памяти, я просто пытаюсь объяснить эту идею.

Что меня сейчас озаряет, так это то, что при использовании функции сокращения от нового модуля вход не выравнивается «правильно». Когда я анализирую адреса, отмечу следующие свойства:

((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 

, который, конечно же, вызывает немного проблемы, так как «смещение» значение становится неправильным, но это не так очевидно, так как все другое использование данных (нет «реальной» проблемы выравнивания).

Это сводится к моему вопросу. Вы видите аккуратный способ увеличения указателей, когда смещение не может быть выражено как целое число элементов?

Бонусные баллы для нахождения пути, не прибегать к чрезмерному отливке :)

Answer 1

На ptrdiff_t: «. Это тип, возвращаемый операцией вычитания между двумя указателями Это знаковое интегрального типа, и как таковой могут быть отлиты к совместимым основным типам данных. Вычитание двух указателей предоставляется только для того, чтобы иметь действительное определенное значение для указателей на элементы одного и того же массива (или для элемента, расположенного за последним в массиве). поведение зависит от характеристик системы и реализации компилятора ».

Поскольку вы используете realloc, вы не в этом случае. Таким образом, ваше смещение не будет int. Это объясняет вашу проблему.

Решение бонусных очков не должно указывать ваши указатели на char * для вычисления смещения. В итоге вы получите смещение в байтах. вы можете добавить смещение байта при помощи бросков. Чтобы свести к минимуму кастинг, вы можете написать вспомогательную функцию, которая задает правильное значение вашим указателям на узлы.

Если вы хотите использовать realloc, я не вижу другого решения, так как исходный массив был освобожден realloc. Смещение байта кажется единственным способом.

Вы можете вызвать ваш уменьшенный массив, скопировать узлы, а затем освободить старый массив. Но при перераспределении вы теряете преимущество realloc.

Другие решения заставляют вас изменить структуру данных. Вы можете самостоятельно распределять свои узлы с помощью malloc, и сокращение проще. Вам просто нужно освободить узлы, которые вам больше не нужны.Это кажется самым чистым способом, но вам нужно реорганизовать ...

Надеюсь, это поможет. Скажите мне, если я не понял ...

Answer 2

Если вы не хотите, чтобы бросить:

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

Ваш синтаксис перепутались. Имя тега структуры предшествует определению структуры; все после объявления.

Либо

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

или

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; 
}; 

будет то, что вы имели в виду писать.

---

Это несколько распространенное решение, но требует некоторой реструктуризации существующего кода.

/* 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)); 

Он обеспечивает доступ к pNewBuffer->nodes[i] для 0 <= i < nMaxNodes, не требуется литье в любом месте.

Теперь это было бы лучше, если бы вы могли объявить node_t nodes[0], избегая при этом выключения при вычислении размеров размещения, но даже если некоторые компиляторы довольны этим, я не считаю, что это принято стандартом.

C99 представляет «гибкие элементы массива»

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

, который в значительной степени то же самое, но определенные фактическим стандартом. Некоторые исключения: гибкие элементы массива могут быть размещены только в конце структуры, а sizeof(pNewBuffer->nodes) недействителен (хотя GCC возвращает 0). В противном случае sizeof(graph_t) будет равен размеру, если бы массив node_t[] имел нулевые элементы.