Как сохранить и удалить динамично, и автоматическая переменная универсального типа данных в custum перечисляют структуру данных?

Я создал реализацию структуры данных Списка для универсального типа данных с каждым узлом, объявленным как после.

struct Node
{
  void *data;
  ....
  ....
}

Таким образом, каждый узел в моем списке будет иметь указатель на фактические данные (универсальный, могло быть что-либо), объект, который должен быть сохранен в списке. У меня есть следующая подпись для добавления узла к списку

AddNode(struct List *list, void* eledata);

проблема состоит в том, когда я хочу удалить узел, я хочу освободить даже блок данных, на который указывают *указатель данных в структуре узла, которая будет освобожденной. при первом освобождении от блока данных, кажется, является прямым

free(data) // forget about the syntax.....

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

 int *x = (int*) malloc(sizeof(int));
 *x = 10;
  AddNode(list,(void*)x); // x can be freed as it was created using malloc

что, если узел создается как после

  int x = 10;
  AddNode(list,(void*)&x); // x cannot be freed as it was not created using malloc

Здесь мы не можем назвать свободным на переменной x!!!!

Как я знаю или реализую функциональность и для динамично выделенных переменных и для статических...., которые передаются моему списку....

Заранее спасибо...

Полноценное внедрение как следует, list.h просто содержит прототипов функции.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include "list.h"

//structure of each node
static struct Node{
    void *Data;
    struct Node * Next;
    struct Node * Prev;
};
//complete list interface
struct List{
    int Size;
    struct Node DummyNode;  //dummy node
    void (*Print)(void *Data);
};

//create new List
struct List * CreateList(void(*Print)(void* Data)){
    struct List *newList = (struct List *)malloc(sizeof(struct List));
    if(newList != NULL){
        newList->DummyNode.Data = NULL;
        newList->DummyNode.Next = newList->DummyNode.Prev = &newList->DummyNode;
        newList->Size = 0;
        newList->Print = NULL;

        if(Print != NULL) newList->Print = Print; // hook to user provided print function
        return newList;
    }
    return NULL;
}

//Node *ptr point to one node before the actual node to be removed
static void _RemoveNode(struct List *list, struct Node *ptr)
{
    struct Node *temp = ptr->Next; //catch hold of node that is to be removed
    ptr->Next = temp->Next; // link previous node's next pointer with the temp node next pointer
    temp->Next->Prev = ptr; // link next node's previous pointer with previous node pointer

    temp->Prev = NULL; // unlink from previous node
    temp->Next = NULL; // unlink from next node

    free(temp->Data);  // free the data ............ !!! need to mode generic before cleaning the resource
    free(temp);        // remove the node itself.

    list->Size--;
}
void RemoveNodeAt(struct List *list,int nodeIndex)
{
    if( list->Size > 0 && (nodeIndex >= 0 && nodeIndex < list->Size)){
        int i=-1; // meaning we are at dummy node
        struct Node *ptr = NULL;
        for(ptr = &list->DummyNode ;i < nodeIndex - 1 ;i++) // traverse up to one node before the actual node
            ptr = ptr->Next;
        _RemoveNode(list,ptr);
    }
}

//Node *ptr point to one node before the actual node to be removed
static void _AddNode(struct List *list, struct Node *ptr,void *data)
{
    //create New Node
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode != NULL){
        newNode->Data = data;

        //shift node at index to right
        newNode->Next = ptr->Next; 
        newNode->Prev = ptr; 
        ptr->Next = newNode;
        newNode->Next->Prev = newNode;

        list->Size++;
    }
}
void AddNodeAt(struct List *list,int nodeIndex,void *data)
{
    //A node can be added just before head and just after tail.
    if( nodeIndex >= 0  && nodeIndex <= list->Size){
        int i=-1; // meaning we are at dummy node
        struct Node *ptr = NULL;
        for(ptr = &list->DummyNode ;i < nodeIndex - 1 ;i++) // traverse up to one node before the actual node
            ptr = ptr->Next;
        _AddNode(list,ptr,data);
    }
}

void RemoveNode(struct List *list)
{
    if(list->Size > 0){  //check if the list is not empty
        struct Node * temp = list->DummyNode.Prev; //catch hold of last node
        temp->Prev->Next = temp->Next;   //establish previous node's next pointer to temp node next pointer
        temp->Next->Prev = temp->Prev;   //establish next node's previous pointer to temp node previous pointer

        temp->Next = NULL; // unlink temp node from next node
        temp->Prev = NULL; // unlink temp node from previous node

        free(temp->Data);  // free the data ............ !!! need to mode generic before cleaning the resource
        free(temp);        // remove the node itself.

        list->Size--;
    }
}
void AddNode(struct List *list,void *data)
{
    struct Node *ptr = list->DummyNode.Prev;

    //create New Node
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode != NULL){
        newNode->Data = data;

        //shift node at index to right
        newNode->Next = ptr->Next; 
        newNode->Prev = ptr; 
        ptr->Next = newNode;
        newNode->Next->Prev = newNode;

        list->Size++;
    }
}
void DeleteAllNodes(struct List *list)
{
    struct Node *ptr = &list->DummyNode;
    while(list->Size > 0){
        _RemoveNode(list,ptr);
        ptr = ptr->Next;
    }
}

void Display(struct List *list)
{
    if(list->Print != NULL){  //If conusmer doesnot provide a print function just give up printing process.
        int i=0;
        struct Node *ptr = &list->DummyNode;
        for(i = 0; i < list->Size; i++){
            ptr = ptr->Next;
            list->Print(ptr->Data);  // let the consumer of the list data structure print the way he wants
        }
    }
}

// must be used before inserting automatic variables are passed in to the list
// because freeing a automatic variable with free function is a crime....!!!! *(~_~)*
// So i want you to create clones of the automatic variables and pass those variables.
//  AddNode(list,Clone(&i,sizeof(i)));
void * Clone(void *data, int size)
{
    void * clone = malloc(size);
    memcpy(clone,data,size);
    return clone;
}
1
задан Vineel Kumar Reddy 1 May 2010 в 16:30
поделиться

4 ответа

Если вы используете такой фрагмент

int x = 10;
AddNode(list, (void *)&x);

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

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

0
ответ дан 3 September 2019 в 00:55
поделиться

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

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

Хорошим компромиссом, позволяющим избежать ненужных копий, может быть то, что список всегда освобождает сами данные, но при вставке пользователь может выбрать, чтобы копирование не происходило. Для этого он может передать значения размера 0 или -1, чтобы указать, что копия не требуется, поскольку данные уже находятся в куче и не будут обрабатываться (освобождаться) кем-либо еще.

2
ответ дан 3 September 2019 в 00:55
поделиться

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

struct Node
{
  void *data;
  int data_on_heap;  // on heap, so should be freed
  ....
  ....
};

Вам нужно будет изменить вашу функцию AddNode, чтобы она принимала эту информацию:

int *x = (int*) malloc(sizeof(int));
*x = 10;
AddNode(list, x, 1); // x can be freed as it was created using malloc

int x2 = 10;
AddNode(list, &x2, 0);

И когда вы хотите освободить ее, вы нужно будет проверить:

if (n->data_on_heap)
    free(n->data);
0
ответ дан 3 September 2019 в 00:55
поделиться

Измените функцию AddNode так, чтобы всегда копировали переданные ему данные, и освобождали данные, когда вы хотите удалить узел .

0
ответ дан 3 September 2019 в 00:55
поделиться
Другие вопросы по тегам:

Похожие вопросы: