1 // This list structure implementation is adapted from the list implementation
2 // on the Linux kernel.
3
4 // Original source:
5 // http://git.kernel.org/?p=linux/kernel/git/stable/linux-2.6.25.y.git;a=blob_plain;f=include/linux/list.h;hb=HEAD
6
7 #ifndef _LINUX_LIST_H
8 #define _LINUX_LIST_H
9
10 /*
11 * Simple doubly linked list implementation.
12 *
13 * Some of the internal functions ("__xxx") are useful when
14 * manipulating whole lists rather than single entries, as
15 * sometimes we already know the next/prev entries and we can
16 * generate better code by using them directly rather than
17 * using the generic single-entry routines.
18 */
19
20 #include <stddef.h>
21 #include <stdlib.h>
22
23 #include "rk_aiq_comm.h"
24
25 #ifndef offsetof
26 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
27 #endif
28
29 #ifndef container_of
30 #define container_of(ptr, type, member) ({ \
31 void *__mptr = (void *)(ptr); \
32 (type *)((char *)__mptr - offsetof(type,member));})
33
34 #endif
35
36 struct list_head {
37 struct list_head *next, *prev;
38 };
39
40 #define LIST_HEAD_INIT(name) { &(name), &(name) }
41
42 #define LIST_HEAD(name) \
43 struct list_head name = LIST_HEAD_INIT(name)
44
INIT_LIST_HEAD(struct list_head * list)45 static inline void INIT_LIST_HEAD(struct list_head *list)
46 {
47 list->next = list;
48 list->prev = list;
49 }
50
51 /*
52 * Insert a new entry between two known consecutive entries.
53 *
54 * This is only for internal list manipulation where we know
55 * the prev/next entries already!
56 */
__list_add(struct list_head * n,struct list_head * prev,struct list_head * next)57 static inline void __list_add(struct list_head *n,
58 struct list_head *prev,
59 struct list_head *next)
60 {
61 next->prev = n;
62 n->next = next;
63 n->prev = prev;
64 prev->next = n;
65 }
66
67 /**
68 * list_add - add a new entry
69 * @new: new entry to be added
70 * @head: list head to add it after
71 *
72 * Insert a new entry after the specified head.
73 * This is good for implementing stacks.
74 */
list_add(struct list_head * n,struct list_head * head)75 static inline void list_add(struct list_head *n, struct list_head *head)
76 {
77 __list_add(n, head, head->next);
78 }
79
80
81
82 /**
83 * list_add_tail - add a new entry
84 * @new: new entry to be added
85 * @head: list head to add it before
86 *
87 * Insert a new entry before the specified head.
88 * This is useful for implementing queues.
89 */
list_add_tail(struct list_head * n,struct list_head * head)90 static inline void list_add_tail(struct list_head *n, struct list_head *head)
91 {
92 __list_add(n, head->prev, head);
93 }
94
95
96 /*
97 * Delete a list entry by making the prev/next entries
98 * point to each other.
99 *
100 * This is only for internal list manipulation where we know
101 * the prev/next entries already!
102 */
__list_del(struct list_head * prev,struct list_head * next)103 static inline void __list_del(struct list_head * prev, struct list_head * next)
104 {
105 next->prev = prev;
106 prev->next = next;
107 }
108
109 /**
110 * list_del - deletes entry from list.
111 * @entry: the element to delete from the list.
112 * Note: list_empty() on entry does not return true after this, the entry is
113 * in an undefined state.
114 */
list_del(struct list_head * entry)115 static inline void list_del(struct list_head *entry)
116 {
117 __list_del(entry->prev, entry->next);
118 entry->next = NULL;
119 entry->prev = NULL;
120 }
121
122 /**
123 * list_replace - replace old entry by new one
124 * @old : the element to be replaced
125 * @new : the new element to insert
126 *
127 * If @old was empty, it will be overwritten.
128 */
list_replace(struct list_head * old,struct list_head * n)129 static inline void list_replace(struct list_head *old,
130 struct list_head *n)
131 {
132 n->next = old->next;
133 n->next->prev = n;
134 n->prev = old->prev;
135 n->prev->next = n;
136 }
137
list_replace_init(struct list_head * old,struct list_head * n)138 static inline void list_replace_init(struct list_head *old,
139 struct list_head *n)
140 {
141 list_replace(old, n);
142 INIT_LIST_HEAD(old);
143 }
144
145 /**
146 * list_del_init - deletes entry from list and reinitialize it.
147 * @entry: the element to delete from the list.
148 */
list_del_init(struct list_head * entry)149 static inline void list_del_init(struct list_head *entry)
150 {
151 __list_del(entry->prev, entry->next);
152 INIT_LIST_HEAD(entry);
153 }
154
155 /**
156 * list_move - delete from one list and add as another's head
157 * @list: the entry to move
158 * @head: the head that will precede our entry
159 */
list_move(struct list_head * list,struct list_head * head)160 static inline void list_move(struct list_head *list, struct list_head *head)
161 {
162 __list_del(list->prev, list->next);
163 list_add(list, head);
164 }
165
166 /**
167 * list_move_tail - delete from one list and add as another's tail
168 * @list: the entry to move
169 * @head: the head that will follow our entry
170 */
list_move_tail(struct list_head * list,struct list_head * head)171 static inline void list_move_tail(struct list_head *list,
172 struct list_head *head)
173 {
174 __list_del(list->prev, list->next);
175 list_add_tail(list, head);
176 }
177
178 /**
179 * list_is_last - tests whether @list is the last entry in list @head
180 * @list: the entry to test
181 * @head: the head of the list
182 */
list_is_last(const struct list_head * list,const struct list_head * head)183 static inline int list_is_last(const struct list_head *list,
184 const struct list_head *head)
185 {
186 return list->next == head;
187 }
188
189 /**
190 * list_empty - tests whether a list is empty
191 * @head: the list to test.
192 */
list_empty(const struct list_head * head)193 static inline int list_empty(const struct list_head *head)
194 {
195 return head->next == head;
196 }
197
198 /**
199 * list_empty_careful - tests whether a list is empty and not being modified
200 * @head: the list to test
201 *
202 * Description:
203 * tests whether a list is empty _and_ checks that no other CPU might be
204 * in the process of modifying either member (next or prev)
205 *
206 * NOTE: using list_empty_careful() without synchronization
207 * can only be safe if the only activity that can happen
208 * to the list entry is list_del_init(). Eg. it cannot be used
209 * if another CPU could re-list_add() it.
210 */
list_empty_careful(const struct list_head * head)211 static inline int list_empty_careful(const struct list_head *head)
212 {
213 struct list_head *next = head->next;
214 return (next == head) && (next == head->prev);
215 }
216
__list_splice(struct list_head * list,struct list_head * head)217 static inline void __list_splice(struct list_head *list,
218 struct list_head *head)
219 {
220 struct list_head *first = list->next;
221 struct list_head *last = list->prev;
222 struct list_head *at = head->next;
223
224 first->prev = head;
225 head->next = first;
226
227 last->next = at;
228 at->prev = last;
229 }
230
231 /**
232 * list_splice - join two lists
233 * @list: the new list to add.
234 * @head: the place to add it in the first list.
235 */
list_splice(struct list_head * list,struct list_head * head)236 static inline void list_splice(struct list_head *list, struct list_head *head)
237 {
238 if (!list_empty(list))
239 __list_splice(list, head);
240 }
241
242 /**
243 * list_prepare_item -prepares a list item so that it can be added to a list.
244 * param: p_item The list item to be initialized.
245 */
list_prepare_item(void * p_item)246 static inline void list_prepare_item(void* p_item) {
247 // ASSERT(p_item != NULL);
248 ((struct list_head*)p_item)->next = NULL;
249 ((struct list_head*)p_item)->prev = NULL;
250 }
251
252 /**
253 * add by emily
254 * list_swap_item - transpose two adjacent items in the list .
255 * param: node1 One item in the list
256 * param: node2 Tne another adjacent item in the list
257 */
list_swap_item(struct list_head * node1,struct list_head * node2)258 static inline void list_swap_item(struct list_head* node1, struct list_head* node2)
259 {
260 // input list
261 // |------------|
262 // n0->n1->n2->n3
263 // output list
264 // |------------|
265 // n0->n2->n1->n3
266
267 struct list_head* n0, *n3;
268 n0 = node1->prev;
269 n3 = node2->next;
270 if (node1->next == node2) {
271 n3->prev = node1;
272 node1->next = n3;
273 node1->prev = node2;
274 node2->next = node1;
275 node2->prev = n0;
276 n0->next = node2;
277 }
278 }
279
280 /**
281 * print_list -print list.
282 * param: head The list item to be printed.
283 */
get_list_num(const struct list_head * head)284 AIQ_MAYBE_UNUSED static int get_list_num(const struct list_head* head) {
285 struct list_head* p;
286 p = head->next;
287 int num =0;
288 while (p != head)
289 {
290 num++;
291 p = p->next;
292 }
293 return(num);
294 }
295
296 /**
297 * print_list -print list.
298 * param: head The list item to be printed.
299 */
print_list(struct list_head * head)300 AIQ_MAYBE_UNUSED static void print_list(struct list_head* head) {
301 struct list_head* p;
302 p = head->next;
303 while (p != head) {
304 printf("%p ", p);
305 p = p->next;
306 }
307 printf("\n");
308 }
309
310 /**
311 * list_prepare_item -clear list ,the head of list is reserved.
312 * param: l The list item to be cleared.
313 */
clear_list(struct list_head * l)314 AIQ_MAYBE_UNUSED static void clear_list(struct list_head* l) {
315 struct list_head* p;
316 if(l==NULL){
317 return;
318 }
319 p = (l)->next;
320 while (p != (l))
321 {
322 p = p->next;
323 free(p->prev);
324 }
325 INIT_LIST_HEAD(l);
326 }
327
328 /**
329 * list_splice_init - join two lists and reinitialise the emptied list.
330 * @list: the new list to add.
331 * @head: the place to add it in the first list.
332 *
333 * The list at @list is reinitialised
334 */
list_splice_init(struct list_head * list,struct list_head * head)335 static inline void list_splice_init(struct list_head *list,
336 struct list_head *head)
337 {
338 if (!list_empty(list)) {
339 __list_splice(list, head);
340 INIT_LIST_HEAD(list);
341 }
342 }
343
344 /**
345 * list_entry - get the struct for this entry
346 * @ptr: the &struct list_head pointer.
347 * @type: the type of the struct this is embedded in.
348 * @member: the name of the list_struct within the struct.
349 */
350 #define list_entry(ptr, type, member) \
351 container_of(ptr, type, member)
352
353 /**
354 * list_first_entry - get the first element from a list
355 * @ptr: the list head to take the element from.
356 * @type: the type of the struct this is embedded in.
357 * @member: the name of the list_struct within the struct.
358 *
359 * Note, that list is expected to be not empty.
360 */
361 #define list_first_entry(ptr, type, member) \
362 list_entry((ptr)->next, type, member)
363
364 /**
365 * list_for_each - iterate over a list
366 * @pos: the &struct list_head to use as a loop cursor.
367 * @head: the head for your list.
368 */
369 #define list_for_each(pos, head) \
370 for (pos = (head)->next; pos != (head); \
371 pos = pos->next)
372
373 /**
374 * __list_for_each - iterate over a list
375 * @pos: the &struct list_head to use as a loop cursor.
376 * @head: the head for your list.
377 *
378 * This variant differs from list_for_each() in that it's the
379 * simplest possible list iteration code, no prefetching is done.
380 * Use this for code that knows the list to be very short (empty
381 * or 1 entry) most of the time.
382 */
383 #define __list_for_each(pos, head) \
384 for (pos = (head)->next; pos != (head); pos = pos->next)
385
386 /**
387 * list_for_each_prev - iterate over a list backwards
388 * @pos: the &struct list_head to use as a loop cursor.
389 * @head: the head for your list.
390 */
391 #define list_for_each_prev(pos, head) \
392 for (pos = (head)->prev; pos != (head); \
393 pos = pos->prev)
394
395 /**
396 * list_for_each_safe - iterate over a list safe against removal of list entry
397 * @pos: the &struct list_head to use as a loop cursor.
398 * @n: another &struct list_head to use as temporary storage
399 * @head: the head for your list.
400 */
401 #define list_for_each_safe(pos, n, head) \
402 for (pos = (head)->next, n = pos->next; pos != (head); \
403 pos = n, n = pos->next)
404
405 /**
406 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
407 * @pos: the &struct list_head to use as a loop cursor.
408 * @n: another &struct list_head to use as temporary storage
409 * @head: the head for your list.
410 */
411 #define list_for_each_prev_safe(pos, n, head) \
412 for (pos = (head)->prev, n = pos->prev; \
413 pos != (head); \
414 pos = n, n = pos->prev)
415
416 /**
417 * list_for_each_entry - iterate over list of given type
418 * @pos: the type * to use as a loop cursor.
419 * @head: the head for your list.
420 * @member: the name of the list_struct within the struct.
421 */
422 #define list_for_each_entry(pos, head, member) \
423 for (pos = list_entry((head)->next, typeof(*pos), member); \
424 &pos->member != (head); \
425 pos = list_entry(pos->member.next, typeof(*pos), member))
426
427 /**
428 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
429 * @pos: the type * to use as a loop cursor.
430 * @n: another type * to use as temporary storage
431 * @head: the head for your list.
432 * @member: the name of the list_struct within the struct.
433 */
434 #define list_for_each_entry_safe(pos, n, head, member) \
435 for (pos = list_entry((head)->next, typeof(*pos), member), \
436 n = list_entry(pos->member.next, typeof(*pos), member); \
437 &pos->member != (head); \
438 pos = n, n = list_entry(n->member.next, typeof(*n), member))
439
440 /**
441 * list_for_each_entry_reverse - iterate backwards over list of given type.
442 * @pos: the type * to use as a loop cursor.
443 * @head: the head for your list.
444 * @member: the name of the list_struct within the struct.
445 */
446 #define list_for_each_entry_reverse(pos, head, member) \
447 for (pos = list_entry((head)->prev, typeof(*pos), member); \
448 &pos->member != (head); \
449 pos = list_entry(pos->member.prev, typeof(*pos), member))
450
451 /**
452 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
453 * @pos: the type * to use as a start point
454 * @head: the head of the list
455 * @member: the name of the list_struct within the struct.
456 *
457 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
458 */
459 #define list_prepare_entry(pos, head, member) \
460 ((pos) ? : list_entry(head, typeof(*pos), member))
461
462 /**
463 * list_for_each_entry_continue - continue iteration over list of given type
464 * @pos: the type * to use as a loop cursor.
465 * @head: the head for your list.
466 * @member: the name of the list_struct within the struct.
467 *
468 * Continue to iterate over list of given type, continuing after
469 * the current position.
470 */
471 #define list_for_each_entry_continue(pos, head, member) \
472 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
473 &pos->member != (head); \
474 pos = list_entry(pos->member.next, typeof(*pos), member))
475
476 /**
477 * list_for_each_entry_continue_reverse - iterate backwards from the given point
478 * @pos: the type * to use as a loop cursor.
479 * @head: the head for your list.
480 * @member: the name of the list_struct within the struct.
481 *
482 * Start to iterate over list of given type backwards, continuing after
483 * the current position.
484 */
485 #define list_for_each_entry_continue_reverse(pos, head, member) \
486 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
487 &pos->member != (head); \
488 pos = list_entry(pos->member.prev, typeof(*pos), member))
489
490 /**
491 * list_for_each_entry_from - iterate over list of given type from the current point
492 * @pos: the type * to use as a loop cursor.
493 * @head: the head for your list.
494 * @member: the name of the list_struct within the struct.
495 *
496 * Iterate over list of given type, continuing from current position.
497 */
498 #define list_for_each_entry_from(pos, head, member) \
499 for (; &pos->member != (head); \
500 pos = list_entry(pos->member.next, typeof(*pos), member))
501
502 /**
503 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
504 * @pos: the type * to use as a loop cursor.
505 * @n: another type * to use as temporary storage
506 * @head: the head for your list.
507 * @member: the name of the list_struct within the struct.
508 */
509 #define list_for_each_entry_safe(pos, n, head, member) \
510 for (pos = list_entry((head)->next, typeof(*pos), member), \
511 n = list_entry(pos->member.next, typeof(*pos), member); \
512 &pos->member != (head); \
513 pos = n, n = list_entry(n->member.next, typeof(*n), member))
514
515 /**
516 * list_for_each_entry_safe_continue
517 * @pos: the type * to use as a loop cursor.
518 * @n: another type * to use as temporary storage
519 * @head: the head for your list.
520 * @member: the name of the list_struct within the struct.
521 *
522 * Iterate over list of given type, continuing after current point,
523 * safe against removal of list entry.
524 */
525 #define list_for_each_entry_safe_continue(pos, n, head, member) \
526 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
527 n = list_entry(pos->member.next, typeof(*pos), member); \
528 &pos->member != (head); \
529 pos = n, n = list_entry(n->member.next, typeof(*n), member))
530
531 /**
532 * list_for_each_entry_safe_from
533 * @pos: the type * to use as a loop cursor.
534 * @n: another type * to use as temporary storage
535 * @head: the head for your list.
536 * @member: the name of the list_struct within the struct.
537 *
538 * Iterate over list of given type from current point, safe against
539 * removal of list entry.
540 */
541 #define list_for_each_entry_safe_from(pos, n, head, member) \
542 for (n = list_entry(pos->member.next, typeof(*pos), member); \
543 &pos->member != (head); \
544 pos = n, n = list_entry(n->member.next, typeof(*n), member))
545
546 /**
547 * list_for_each_entry_safe_reverse
548 * @pos: the type * to use as a loop cursor.
549 * @n: another type * to use as temporary storage
550 * @head: the head for your list.
551 * @member: the name of the list_struct within the struct.
552 *
553 * Iterate backwards over list of given type, safe against removal
554 * of list entry.
555 */
556 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
557 for (pos = list_entry((head)->prev, typeof(*pos), member), \
558 n = list_entry(pos->member.prev, typeof(*pos), member); \
559 &pos->member != (head); \
560 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
561
562
563 #endif
564