forked from sysprog21/lab0-c
-
Notifications
You must be signed in to change notification settings - Fork 0
/
queue.c
209 lines (187 loc) · 5.73 KB
/
queue.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "harness.h"
#include "queue.h"
/* Notice: sometimes, Cppcheck would find the potential NULL pointer bugs,
* but some of them cannot occur. You can suppress them by adding the
* following line.
* cppcheck-suppress nullPointer
*/
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
struct list_head *q_new()
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return NULL;
INIT_LIST_HEAD(&e->list); // prev and next point to itself
return &e->list;
}
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
// value is a pointer, so if you only free struct, you just clean the
// address, value still there use container_of to find the element_t
if (!l)
return;
struct list_head *p = l->next;
element_t *e = container_of(p, element_t,
list); // head is the "list" in the "element_t"
while (p != l) // last one's next is head
{
p = p->next;
q_release_element(e);
// free(e->value);
// free(e);
}
}
/*
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false; // q is null
element_t *new_node = malloc(sizeof(element_t));
new_node->value =
malloc(sizeof(char) * (strlen(s) + 1)); // sizeof char = 1
memcpy(new_node->value, s, strlen(s) + 1); // include last '\0'
list_add(&new_node->list, head); // add element after head
// not sure, i try to change the head to new_node
// and i found that the head is queue head, head->next is the list head
/*
struct list_head **pp = &head;
*pp = new_node
*/
return true; // succeed
}
/*
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false; // q is null
element_t *new_node = malloc(sizeof(element_t));
new_node->value =
malloc(sizeof(char) * (strlen(s) + 1)); // sizeof char = 1
memcpy(new_node->value, s, strlen(s) + 1); // include last '\0'
list_add_tail(&new_node->list, head); // add element after head
return true;
}
/*
* Attempt to remove element from head of queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
*
* NOTE: "remove" is different from "delete"
* The space used by the list element and the string should not be freed.
* The only thing "remove" need to do is unlink it.
*
* REF:
* https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
*/
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
struct list_head *p = head->next;
element_t *e = container_of(p, element_t, list);
memcpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(p); // it mean remove, not delete
return e;
}
/*
* Attempt to remove element from tail of queue.
* Other attribute is as same as q_remove_head.
*/
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
struct list_head *p = head->prev;
element_t *e = container_of(p, element_t, list);
memcpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(p); // it mean remove, not delete
return e;
}
/*
* WARN: This is for external usage, don't modify it
* Attempt to release element.
*/
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(struct list_head *head)
{
return -1;
}
/*
* Delete the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return true if successful.
* Return false if list is NULL or empty.
*/
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
return true;
}
/*
* Delete all nodes that have duplicate string,
* leaving only distinct strings from the original list.
* Return true if successful.
* Return false if list is NULL.
*
* Note: this function always be called after sorting, in other words,
* list is guaranteed to be sorted in ascending order.
*/
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
return true;
}
/*
* Attempt to swap every two adjacent nodes.
*/
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
/*
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
*/
void q_reverse(struct list_head *head) {}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head) {}