diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/luaproc/list.c | 241 |
1 files changed, 241 insertions, 0 deletions
diff --git a/libraries/luaproc/list.c b/libraries/luaproc/list.c new file mode 100644 index 0000000..0088695 --- /dev/null +++ b/libraries/luaproc/list.c | |||
@@ -0,0 +1,241 @@ | |||
1 | /*************************************************** | ||
2 | |||
3 | Copyright 2008 Alexandre Skyrme, Noemi Rodriguez, Roberto Ierusalimschy | ||
4 | |||
5 | Permission is hereby granted, free of charge, to any person obtaining a copy | ||
6 | of this software and associated documentation files (the "Software"), to deal | ||
7 | in the Software without restriction, including without limitation the rights | ||
8 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | ||
9 | copies of the Software, and to permit persons to whom the Software is | ||
10 | furnished to do so, subject to the following conditions: | ||
11 | |||
12 | The above copyright notice and this permission notice shall be included in | ||
13 | all copies or substantial portions of the Software. | ||
14 | |||
15 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | ||
16 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | ||
17 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | ||
18 | AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | ||
19 | LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | ||
20 | OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | ||
21 | THE SOFTWARE. | ||
22 | |||
23 | ***************************************************** | ||
24 | |||
25 | [list.c] | ||
26 | |||
27 | ****************************************************/ | ||
28 | #include <stdio.h> | ||
29 | #include <stdlib.h> | ||
30 | |||
31 | #include "list.h" | ||
32 | |||
33 | /* linked list node */ | ||
34 | struct stnode { | ||
35 | void *data; | ||
36 | struct stnode *next; | ||
37 | struct stnode *prev; | ||
38 | }; | ||
39 | |||
40 | /* linked list */ | ||
41 | struct stlist { | ||
42 | node head; | ||
43 | node tail; | ||
44 | int nodes; | ||
45 | }; | ||
46 | |||
47 | /* create new (empty) list */ | ||
48 | list list_new( void ) { | ||
49 | list lst; | ||
50 | lst = (list )malloc( sizeof( struct stlist )); | ||
51 | if ( lst == NULL ) { | ||
52 | return lst; | ||
53 | } | ||
54 | lst->head = NULL; | ||
55 | lst->tail = NULL; | ||
56 | lst->nodes = 0; | ||
57 | return lst; | ||
58 | } | ||
59 | |||
60 | /* create new node */ | ||
61 | node list_new_node( void *data ) { | ||
62 | node n; | ||
63 | n = (node )malloc( sizeof( struct stnode )); | ||
64 | if ( n == NULL ) { | ||
65 | return n; | ||
66 | } | ||
67 | n->data = data; | ||
68 | n->next = NULL; | ||
69 | n->prev = NULL; | ||
70 | return n; | ||
71 | } | ||
72 | |||
73 | /* add node to list */ | ||
74 | node list_add( list lst, node n ) { | ||
75 | |||
76 | /* void list or node */ | ||
77 | if (( lst == NULL ) || ( n == NULL )) { | ||
78 | return NULL; | ||
79 | } | ||
80 | |||
81 | /* list is empty */ | ||
82 | if ( lst->head == NULL ) { | ||
83 | lst->head = n; | ||
84 | lst->tail = n; | ||
85 | } | ||
86 | |||
87 | /* list is _not_ empty */ | ||
88 | else { | ||
89 | lst->tail->next = n; | ||
90 | n->prev = lst->tail; | ||
91 | lst->tail = n; | ||
92 | } | ||
93 | |||
94 | lst->nodes++; | ||
95 | return n; | ||
96 | } | ||
97 | |||
98 | /* search for a node */ | ||
99 | node list_search( list lst, void *data ) { | ||
100 | |||
101 | node nitr; | ||
102 | |||
103 | /* check if list is null or empty */ | ||
104 | if (( lst == NULL ) || ( lst->head == NULL )) { | ||
105 | return NULL; | ||
106 | } | ||
107 | |||
108 | /* look for node between first and last nodes (first and last are included) */ | ||
109 | for ( nitr = lst->head; nitr != NULL; nitr = nitr->next ) { | ||
110 | if ( nitr->data == data ) { | ||
111 | /* node found, return it */ | ||
112 | return nitr; | ||
113 | } | ||
114 | } | ||
115 | |||
116 | /* node not found */ | ||
117 | return NULL; | ||
118 | } | ||
119 | |||
120 | /* remove node from list */ | ||
121 | void list_remove( list lst, node n ) { | ||
122 | |||
123 | node nitr; | ||
124 | |||
125 | /* check if list or node are null and if list is empty */ | ||
126 | if (( lst == NULL ) || ( n == NULL ) || ( lst->head == NULL )) { | ||
127 | return; | ||
128 | } | ||
129 | |||
130 | /* check if node is list's head */ | ||
131 | if ( lst->head == n ) { | ||
132 | lst->head = n->next; | ||
133 | /* if so, also check if it's the only node in the list */ | ||
134 | if ( lst->tail == n ) { | ||
135 | lst->tail = n->next; | ||
136 | } | ||
137 | else { | ||
138 | lst->head->prev = NULL; | ||
139 | } | ||
140 | free( n ); | ||
141 | lst->nodes--; | ||
142 | return; | ||
143 | } | ||
144 | |||
145 | /* look for node between first and last nodes (first and last are excluded) */ | ||
146 | for ( nitr = lst->head->next; nitr != lst->tail; nitr = nitr->next ) { | ||
147 | if ( nitr == n ) { | ||
148 | n->prev->next = n->next; | ||
149 | n->next->prev = n->prev; | ||
150 | free( n ); | ||
151 | lst->nodes--; | ||
152 | return; | ||
153 | } | ||
154 | } | ||
155 | |||
156 | /* check if node is list's tail */ | ||
157 | if ( lst->tail == n ) { | ||
158 | lst->tail = n->prev; | ||
159 | n->prev->next = n->next; | ||
160 | free( n ); | ||
161 | lst->nodes--; | ||
162 | return; | ||
163 | } | ||
164 | |||
165 | return; | ||
166 | } | ||
167 | |||
168 | /* list_destroy */ | ||
169 | void list_destroy( list lst ) { | ||
170 | |||
171 | /* empty list */ | ||
172 | if ( lst == NULL ) { | ||
173 | return; | ||
174 | } | ||
175 | |||
176 | /* non-empty list */ | ||
177 | while ( lst->head != NULL ) { | ||
178 | list_remove( lst, lst->head ); | ||
179 | } | ||
180 | |||
181 | free( lst ); | ||
182 | } | ||
183 | |||
184 | /* return list's first node */ | ||
185 | node list_head( list lst ) { | ||
186 | if ( lst != NULL ) { | ||
187 | return lst->head; | ||
188 | } | ||
189 | return NULL; | ||
190 | } | ||
191 | |||
192 | /* return node's next node */ | ||
193 | node list_next( node n ) { | ||
194 | if ( n != NULL ) { | ||
195 | return n->next; | ||
196 | } | ||
197 | return NULL; | ||
198 | } | ||
199 | |||
200 | /* return a node's data */ | ||
201 | void *list_data( node n ) { | ||
202 | if ( n != NULL ) { | ||
203 | return n->data; | ||
204 | } | ||
205 | return NULL; | ||
206 | } | ||
207 | |||
208 | /* pop the head node from the list */ | ||
209 | node list_pop_head( list lst ) { | ||
210 | node ntmp; | ||
211 | if (( lst == NULL ) || ( lst->head == NULL )) { | ||
212 | return NULL; | ||
213 | } | ||
214 | |||
215 | ntmp = lst->head; | ||
216 | if ( lst->head == lst->tail ) { | ||
217 | lst->head = NULL; | ||
218 | lst->tail = NULL; | ||
219 | } else { | ||
220 | lst->head = ntmp->next; | ||
221 | ntmp->next->prev = NULL; | ||
222 | } | ||
223 | ntmp->next = NULL; | ||
224 | ntmp->prev = NULL; | ||
225 | lst->nodes--; | ||
226 | return ntmp; | ||
227 | } | ||
228 | |||
229 | /* destroy a node */ | ||
230 | void list_destroy_node( node n ) { | ||
231 | free( n ); | ||
232 | } | ||
233 | |||
234 | /* return a list's node count */ | ||
235 | int list_node_count( list lst ) { | ||
236 | if ( lst != NULL ) { | ||
237 | return lst->nodes; | ||
238 | } | ||
239 | return LIST_COUNT_ERROR; | ||
240 | } | ||
241 | |||