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

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

2 голосов
/ 10 июля 2009

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

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

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

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

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

Бонусные баллы за поиск пути, который не прибегает к чрезмерному кастингу:)

Ответы [ 3 ]

2 голосов
/ 10 июля 2009

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

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

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

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

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

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

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

1 голос
/ 11 июля 2009

Ваш синтаксис испорчен. Имя тега структуры идет перед определением структуры; все, что после - это декларация.

Или 

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[] имел ноль элементов.

1 голос
/ 10 июля 2009

Если вы не хотите разыгрывать: 

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