英文:
Double linked list improvements
问题
ll_create function appears to have a potential memory leak because it allocates memory for a linked_list_p structure (which is essentially a pointer to a linked list) but does not initialize the head, tail, and size members of the linked list within that structure. If the function is called with an already existing linked_list_p that is not NULL, it returns -1 without properly cleaning up the previously allocated memory.
Here's why it can lead to a memory leak:
-
If
ll_createis called with a non-NULLlist, it doesn't free any memory allocated for the previous linked list structure (if any) before allocating a new one. This means that ifll_createis called multiple times with a non-NULLlist, it could keep allocating new structures without freeing the old ones, leading to a memory leak. -
Additionally, if
ll_createis called with a NULLlist, it allocates memory for a new linked list structure but doesn't initialize its members (head,tail, andsize) to proper values. This could lead to undefined behavior when attempting to use the linked list later in the program.
To avoid the memory leak and ensure proper initialization, you should modify ll_create to either properly initialize a newly allocated linked list structure or return an error if a non-NULL list is passed.
Here's a possible modification:
int ll_create(linked_list_p *list, void (*print_data)(uint8_t)) {
if (list == NULL || *list != NULL) {
// Return an error if list is NULL or if it's already initialized.
return -1;
}
*list = calloc(1, sizeof(linked_list_t));
if (*list == NULL) {
// Handle memory allocation failure.
return -1;
}
(*list)->head = NULL;
(*list)->tail = NULL;
(*list)->size = 0;
(*list)->print_data = print_data;
return 0;
}
This modified function takes a pointer to a linked_list_p as its first argument and properly initializes the linked list structure if it's created or returns an error if a non-NULL list is passed.
英文:
I'm trying to improve my double linked list API.
int ll_create(linked_list_p list, void (*print_data)(uint8_t)) {
if (list == NULL) {
list = calloc(1, sizeof(linked_list_p));
return 0;
}
return -1;
}
int ll_destroy(linked_list_p list) {
if (list == NULL) {
return -1;
}
linked_list_node_p node_ptr = list->tail;
for(int i = list->size-1; i > 0; i--) {
if (node_ptr->next) {
free(node_ptr->next);
node_ptr->next = NULL;
}
node_ptr = node_ptr->previous;
if (node_ptr->next->previous) {
node_ptr->next->previous = NULL;
}
free(node_ptr->next);
node_ptr->next = NULL;
}
free(list->head);
list->head = NULL;
list->size = 0;
return 0;
}
int ll_get(linked_list_p list, uint32_t index, uint8_t *data){
if (list == NULL) {
return -1;
}
if (index >= list->size) {
return -1;
}
linked_list_node_p node_ptr = list->head;
for (int i = 0; i < index; i++){
if (node_ptr == NULL) {
return -1;
}
node_ptr = node_ptr->next;
}
*data = node_ptr->data.data;
return 0;
}
int ll_remove(linked_list_p list, uint32_t index) {
if (list == NULL) {
return -1;
}
if (index > list->size-1) {
return -1;
}
linked_list_node_p node_to_delete;
if (index == 0) {
node_to_delete = list->head;
list->head = list->head->next;
free(list->head->previous);
list->head->previous = NULL;
free(node_to_delete->next);
node_to_delete->next = NULL;
node_to_delete = NULL;
free(node_to_delete);
list->size --;
return 0;
}
if (index == list->size-1) {
node_to_delete = list->tail;
list->tail = list->tail->previous;
free(list->tail->next);
list->tail->next = NULL;
free(node_to_delete->previous);
node_to_delete->previous = NULL;
free(node_to_delete);
node_to_delete = NULL;
list->size --;
return 0;
}
linked_list_node_p node_ptr = list->head;
for (int i = 0; i < index-1; i++) {
node_ptr = node_ptr->next;
}
node_to_delete = node_ptr->next;
node_ptr->next->next->previous = node_ptr;
node_ptr->next = node_ptr->next->next;
node_to_delete->next = NULL;
node_to_delete->previous = NULL;
free(node_to_delete->next);
free(node_to_delete->previous);
list->size--;
return 0;
}
This is the main : I've tried to test it myself but not sure if its the right way to do it.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linked_list.h"
static void print_data(uint8_t data){
printf("%d", data);
}
int main(int argc, char *argv[]){
static linked_list_t list;
ll_create(&list, print_data);
ll_add_first(&list, 2);
ll_insert(&list, 13, 0);
ll_remove(&list, 32);
ll_add_last(&list, 3);
ll_add_last(&list, 4);
ll_print(&list);
ll_destroy(&list);
ll_print(&list);
ll_add_last(&list, 5);
ll_add_last(&list, 6);
ll_add_first(&list, 7);
ll_print(&list);
ll_print_backward(&list);
ll_insert(&list, 8, 4);
printf("list size : %ld\n", list.size);
ll_insert(&list, 8, list.size);
ll_print(&list);
//TODO use every API functions
// ll_get
uint8_t get_data = 0;
ll_get(&list, 95, &get_data);
printf("got data : %d\n\n", get_data);
// ll_remove
ll_remove(&list, 5);
ll_print(&list);
// ll_insert
ll_insert(&list, 10, 2);
ll_print(&list);
// ll_contains
uint8_t data_to_find = 96;
printf("The data %d is in the list : %s", data_to_find, ll_contains(&list, data_to_find) ? "true\n" : "false\n");
data_to_find = 10;
printf("The data %d is in the list : %s", data_to_find, ll_contains(&list, data_to_find) ? "true\n" : "false\n");
printf("\n");
// ll_first_index
data_to_find = 10;
printf("The data %d is at node [%d]\n", data_to_find, ll_first_index(&list, data_to_find));
data_to_find = 96;
printf("The data %d is at node [%d]\n", data_to_find, ll_first_index(&list, data_to_find));
// ll_indexes
ll_add_last(&list, 25);
ll_add_first(&list, 25);
ll_insert(&list, 25, list.size);
ll_print(&list);
uint32_t *indexes = NULL;
uint32_t indexes_size = 0;
if (ll_indexes(&list, 25, &indexes, &indexes_size) == 0) {
for (int i = 0; i < indexes_size; i++) {
printf("%d ", indexes[i]);
}
printf("\n");
}
free(indexes);
if (ll_indexes(&list, 6, &indexes, &indexes_size) == 0) {
for (int i = 0; i < indexes_size; i++) {
printf("%d ", indexes[i]);
}
printf("\n");
}
free(indexes);
if (ll_indexes(&list, 7, &indexes, &indexes_size) == 0) {
for (int i = 0; i < indexes_size; i++) {
printf("%d ", indexes[i]);
}
printf("\n");
}
free(indexes);
ll_destroy(&list);
ll_destroy(&list);
return 0;
}
This is the header file structs and typedef
/**
* No modification required here
*/
typedef struct data_s{
uint8_t data;
} data_t;
/**
* To be implemented : double linked list
*/
struct linked_list_s;
struct linked_list_node_s;
typedef struct linked_list_s linked_list_t;
typedef linked_list_t *linked_list_p;
typedef struct linked_list_node_s linked_list_node_t;
typedef linked_list_node_t *linked_list_node_p;
struct linked_list_node_s{
linked_list_node_p next;
linked_list_node_p previous;
data_t data;
};
struct linked_list_s{
linked_list_node_p head;
linked_list_node_p tail;
size_t size;
void (*print_data)(uint8_t);
};
Why does the ll_create function have a memory leak? In the main, the list was created without nodes. Thus if we call this function, we won't enter the if statement. So how will this have a memory leak?
答案1
得分: 1
在改进您的API质量之前，您首先需要检查您的代码并消除错误。
例如，即使您提供的代码中的第一个函数ll_create也没有意义，而且还会导致内存泄漏。
int ll_create(linked_list_p list, void (*print_data)(uint8_t)) {
if (list == NULL) {
list = calloc(1, sizeof(linked_list_p));
return 0;
}
return -1;
}
因为在函数退出后，分配的内存的地址丢失了。
而且，在主函数中调用该函数时，返回值是-1。
另外，函数的第二个参数没有被使用。
而且，calloc函数的调用的第二个参数也是不正确的。
或者另一个例子。不清楚为什么在主函数的结尾两次调用函数ll_destroy。
ll_destroy(&list);
ll_destroy(&list);
这会导致未定义的行为，因为函数内部的指针tail没有设置为NULL。
而且，似乎函数内部的这个if语句也没有意义。
if (node_ptr->next) {
free(node_ptr->next);
node_ptr->next = NULL;
}
英文:
Before improving the quality of your API you need at first to check your code and remove bugs.
For example even the first function ll_create in the provided by you code does not make sense and moreover produces a memory leak
int ll_create(linked_list_p list, void (*print_data)(uint8_t)) {
if (list == NULL) {
list = calloc(1, sizeof(linked_list_p));
return 0;
}
return -1;
}
because the address of the allocated memory is lost after exiting the function.
And for this call of the function in main
ll_create(&list, print_data);
returns -1.
Also the second parameter of the function is not used.
And moreover the second parameter of the call of calloc
list = calloc(1, sizeof(linked_list_p));
^^^^^^^^^^^^^
is also incorrect.
Or another example. It is unclear why the function ll_destroy is called twice in the end of main.
ll_destroy(&list);
ll_destroy(&list);
that results in undefined behavior because the pointer tail within the function does not set to NULL.
And it seems this if statement within the function
if (node_ptr->next) {
free(node_ptr->next);
node_ptr->next = NULL;
}
does not make sense.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论