1 /*
2 * Biloba
3 * Copyright (C) 2004-2008 Guillaume Demougeot, Colin Leroy
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
18 */
19
20 /**
21 * Biloba - Q1 2005
22 * Game by Guillaume Demougeot <dmgt@wanadoo.fr>
23 * Code by Colin Leroy <colin@colino.net>
24 *
25 * Our single-linked-list implementation, done to
26 * avoid a dependancy to another library.
27 */
28
29 #include <assert.h>
30 #include <stdlib.h>
31 #include "llist.h"
32
33 /**
34 * Append a pointer to a list
35 *
36 * @param[in] list the list
37 * @param[in] data the data to append
38 *
39 * @return the pointer to the updated list (which can be different than the
40 * original one.
41 */
llist_append(LList * list,void * data)42 LList *llist_append(LList *list, void *data)
43 {
44 LList *result = malloc(sizeof(LList));
45 LList *orig = list;
46 result->data = data;
47 result->next = NULL;
48 if (list) {
49 while(list->next)
50 list = list->next;
51 list->next = result;
52 return orig;
53 }
54
55 return result;
56 }
57
58 /**
59 * Copy a list to another one
60 *
61 * @param[in] list the list
62 *
63 * @return the pointer to the copied list
64 */
llist_copy(LList * list)65 LList *llist_copy(LList *list)
66 {
67 LList *copy = NULL;
68 LList *o_cur;
69 #ifdef DEBUG
70 LList *c_cur;
71 #endif
72
73 for (o_cur = list; o_cur != NULL; o_cur = o_cur->next)
74 copy = llist_prepend(copy, o_cur->data);
75
76 copy = llist_reverse(copy);
77 #ifdef DEBUG
78 for (o_cur = list, c_cur = copy; o_cur != NULL;
79 o_cur = o_cur->next, c_cur = c_cur->next)
80 assert(o_cur->data == c_cur->data);
81
82 assert(o_cur == NULL);
83 assert(c_cur == NULL);
84 #endif
85 return copy;
86 }
87
88 /**
89 * Reverse a list order
90 *
91 * @param[in] list the list
92 *
93 * @return the pointer to the modified list
94 */
llist_reverse(LList * list)95 LList *llist_reverse(LList *list)
96 {
97 LList *rev = NULL;
98
99 for (; list != NULL; list = list->next)
100 rev = llist_prepend(rev, list->data);
101
102 llist_free(list);
103 return rev;
104 }
105
106 /**
107 * Prepend a pointer to a list
108 *
109 * @param[in] list the list
110 * @param[in] data the data to prepend
111 *
112 * @return the pointer to the updated list (which will be different than the
113 * original one.
114 */
llist_prepend(LList * list,void * data)115 LList *llist_prepend(LList *list, void *data)
116 {
117 LList *result = malloc(sizeof(LList));
118 result->data = data;
119 result->next = list;
120 return result;
121 }
122
123 /**
124 * Remove a pointer from a list
125 *
126 * @param[in] list the list
127 * @param[in] data the data to remove
128 *
129 * @return the pointer to the updated list (which can be different than the
130 * original one.
131 */
llist_remove(LList * list,void * data)132 LList *llist_remove(LList *list, void *data)
133 {
134 LList *result = list;
135 if (!list)
136 return NULL;
137
138 if (list->data == data) {
139 result = list->next;
140 free(list);
141 return result;
142 }
143
144 while (list) {
145 if (list->next && list->next->data == data) {
146 LList *tmp = list->next;
147 list->next = list->next->next;
148 free(tmp);
149 return result;
150 }
151 list = list->next;
152 }
153 return result;
154 }
155
156 /**
157 * Find a pointer in list
158 *
159 * @param[in] list the list
160 * @param[in] data the data to look for
161 *
162 * @return the list item containing the data, or NULL if it isn't
163 * there.
164 */
llist_find(LList * list,void * data)165 LList *llist_find(LList *list, void *data)
166 {
167 while(list) {
168 if (list->data == data)
169 return list;
170 list = list->next;
171 }
172 return NULL;
173 }
174
175 /**
176 * Free a list
177 *
178 * @param[in] list the list to free
179 */
llist_free(LList * list)180 void llist_free(LList *list)
181 {
182 while (list) {
183 LList *next = list->next;
184 free(list);
185 list = next;
186 }
187 }
188
189 /**
190 * Get the length of a list
191 *
192 * @param[in] list the list
193 *
194 * @return the number of items the list contains.
195 */
llist_length(LList * list)196 int llist_length(LList *list)
197 {
198 int cnt = 0;
199 while (list) {
200 cnt++;
201 list = list->next;
202 }
203 return cnt;
204 }
205