Mastering Algorithms With C - Kyle Loudon [34]
frame_number = *data;
free(data);
}
}
return frame_number;
}
/*****************************************************************************
* *
* ------------------------------ free_frame ------------------------------ *
* *
*****************************************************************************/
int free_frame(List *frames, int frame_number) {
int *data;
/*****************************************************************************
* *
* Allocate storage for the frame number. *
* *
*****************************************************************************/
if ((data = (int *)malloc(sizeof(int))) == NULL)
return -1;
/*****************************************************************************
* *
* Put the frame back in the list of available frames. *
* *
*****************************************************************************/
*data = frame_number;
if (list_ins_next(frames, NULL, data) != 0)
return -1;
return 0;
}
Description of Doubly-Linked Lists
Doubly-linked lists , as their name implies, are composed of elements linked by two pointers. Each element of a doubly-linked list consists of three parts: in addition to the data and the next pointer, each element includes a pointer to the previous element, called the prev pointer. A doubly-linked list is formed by composing a number of elements so that the next pointer of each element points to the element that follows it, and the prev pointer points to the element preceding it. To mark the head and tail of the list, we set the prev pointer of the first element and the next pointer of the last element to NULL.
To traverse backward through a doubly-linked list, we use the prev pointers of consecutive elements in the tail-to-head direction. Thus, for the cost of an additional pointer for each element, a doubly-linked list offers greater flexibility than a singly-linked list in moving about the list. This can be useful when we know something about where an element might be stored in the list and can choose wisely how to move to it. For example, one flexibility that doubly-linked lists provide is a more intuitive means of removing an element than singly-linked lists.
Interface for Doubly-Linked Lists
Name
dlist_init
Synopsis
void dlist_init(DList *list, void (*destroy)(void *data));
Return Value
None.
Description
Initializes the doubly-linked list specified by list. This operation must be called for a doubly-linked list before the list can be used with any other operation. The destroy argument provides a way to free dynamically allocated data when dlist_destroy is called. It works in a manner similar to that described for list_destroy. For a doubly-linked list containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
dlist_destroy
Synopsis
void dlist_destroy(DList *list);
Return Value
None.
Description
Destroys the doubly-linked list specified by list. No other operations are permitted after calling dlist_destroy unless dlist_init is called again. The dlist_destroy operation removes all elements from a doubly-linked list and calls the function passed as destroy to dlist_init once for each element as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of elements in the doubly-linked list.
Name
dlist_ins_next
Synopsis
int dlist_ins_next(DList *list, DListElmt *element, const void *data);
Return Value
0 if inserting the element is successful, or -1 otherwise.
Description
Inserts an element just after element in the doubly-linked list specified by list. When inserting into an empty list, element may point anywhere, but should be NULL to avoid confusion. The new element contains a pointer to data, so the memory referenced by data should remain valid as long as the element remains in the list. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (1)
Name
dlist_ins_prev
Synopsis
int dlist_ins_prev(DList *list, DListElmt