1 | /*
|
---|
2 | * Copyright (C) 2009-2012 by Matthias Ringwald
|
---|
3 | *
|
---|
4 | * Redistribution and use in source and binary forms, with or without
|
---|
5 | * modification, are permitted provided that the following conditions
|
---|
6 | * are met:
|
---|
7 | *
|
---|
8 | * 1. Redistributions of source code must retain the above copyright
|
---|
9 | * notice, this list of conditions and the following disclaimer.
|
---|
10 | * 2. Redistributions in binary form must reproduce the above copyright
|
---|
11 | * notice, this list of conditions and the following disclaimer in the
|
---|
12 | * documentation and/or other materials provided with the distribution.
|
---|
13 | * 3. Neither the name of the copyright holders nor the names of
|
---|
14 | * contributors may be used to endorse or promote products derived
|
---|
15 | * from this software without specific prior written permission.
|
---|
16 | * 4. Any redistribution, use, or modification is done solely for
|
---|
17 | * personal benefit and not for any commercial purpose or for
|
---|
18 | * monetary gain.
|
---|
19 | *
|
---|
20 | * THIS SOFTWARE IS PROVIDED BY MATTHIAS RINGWALD AND CONTRIBUTORS
|
---|
21 | * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
---|
22 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
|
---|
23 | * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL MATTHIAS
|
---|
24 | * RINGWALD OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
|
---|
25 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
|
---|
26 | * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
|
---|
27 | * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
|
---|
28 | * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
|
---|
29 | * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
|
---|
30 | * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
---|
31 | * SUCH DAMAGE.
|
---|
32 | *
|
---|
33 | * Please inquire about commercial licensing options at btstack@ringwald.ch
|
---|
34 | *
|
---|
35 | */
|
---|
36 |
|
---|
37 | /*
|
---|
38 | * linked_list.c
|
---|
39 | *
|
---|
40 | * Created by Matthias Ringwald on 7/13/09.
|
---|
41 | */
|
---|
42 |
|
---|
43 | #include <btstack/linked_list.h>
|
---|
44 | #include <stdlib.h>
|
---|
45 | #include <stdio.h>
|
---|
46 |
|
---|
47 | /**
|
---|
48 | * tests if list is empty
|
---|
49 | */
|
---|
50 | int linked_list_empty(linked_list_t * list){
|
---|
51 | return *list == (void *) 0;
|
---|
52 | }
|
---|
53 |
|
---|
54 | /**
|
---|
55 | * linked_list_get_last_item
|
---|
56 | */
|
---|
57 | linked_item_t * linked_list_get_last_item(linked_list_t * list){ // <-- find the last item in the list
|
---|
58 | linked_item_t *lastItem = NULL;
|
---|
59 | linked_item_t *it;
|
---|
60 | for (it = *list; it ; it = it->next){
|
---|
61 | if (it) {
|
---|
62 | lastItem = it;
|
---|
63 | }
|
---|
64 | }
|
---|
65 | return lastItem;
|
---|
66 | }
|
---|
67 |
|
---|
68 |
|
---|
69 | /**
|
---|
70 | * linked_list_add
|
---|
71 | */
|
---|
72 | void linked_list_add(linked_list_t * list, linked_item_t *item){ // <-- add item to list
|
---|
73 | // check if already in list
|
---|
74 | linked_item_t *it;
|
---|
75 | for (it = *list; it ; it = it->next){
|
---|
76 | if (it == item) {
|
---|
77 | return;
|
---|
78 | }
|
---|
79 | }
|
---|
80 | // add first
|
---|
81 | item->next = *list;
|
---|
82 | *list = item;
|
---|
83 | }
|
---|
84 |
|
---|
85 | void linked_list_add_tail(linked_list_t * list, linked_item_t *item){ // <-- add item to list as last element
|
---|
86 | // check if already in list
|
---|
87 | linked_item_t *it;
|
---|
88 | for (it = (linked_item_t *) list; it->next ; it = it->next){
|
---|
89 | if (it->next == item) {
|
---|
90 | return;
|
---|
91 | }
|
---|
92 | }
|
---|
93 | item->next = (linked_item_t*) 0;
|
---|
94 | it->next = item;
|
---|
95 | }
|
---|
96 |
|
---|
97 | /**
|
---|
98 | * Remove data_source from run loop
|
---|
99 | *
|
---|
100 | * @note: assumes that data_source_t.next is first element in data_source
|
---|
101 | */
|
---|
102 | int linked_list_remove(linked_list_t * list, linked_item_t *item){ // <-- remove item from list
|
---|
103 | linked_item_t *it;
|
---|
104 | for (it = (linked_item_t *) list; it ; it = it->next){
|
---|
105 | if (it->next == item){
|
---|
106 | it->next = item->next;
|
---|
107 | return 0;
|
---|
108 | }
|
---|
109 | }
|
---|
110 | return -1;
|
---|
111 | }
|
---|
112 |
|
---|
113 | /**
|
---|
114 | * @returns number of items in list
|
---|
115 | */
|
---|
116 | int linked_list_count(linked_list_t * list){
|
---|
117 | linked_item_t *it;
|
---|
118 | int counter = 0;
|
---|
119 | for (it = (linked_item_t *) list; it ; it = it->next) {
|
---|
120 | counter++;
|
---|
121 | }
|
---|
122 | return counter;
|
---|
123 | }
|
---|
124 |
|
---|
125 |
|
---|
126 | void linked_item_set_user(linked_item_t *item, void *user_data){
|
---|
127 | item->next = (linked_item_t *) 0;
|
---|
128 | item->user_data = user_data;
|
---|
129 | }
|
---|
130 |
|
---|
131 | void * linked_item_get_user(linked_item_t *item) {
|
---|
132 | return item->user_data;
|
---|
133 | }
|
---|
134 |
|
---|
135 | //
|
---|
136 | // Linked List Iterator implementation
|
---|
137 | //
|
---|
138 |
|
---|
139 | void linked_list_iterator_init(linked_list_iterator_t * it, linked_list_t * head){
|
---|
140 | it->advance_on_next = 0;
|
---|
141 | it->prev = (linked_item_t*) head;
|
---|
142 | it->curr = * head;
|
---|
143 | }
|
---|
144 |
|
---|
145 | int linked_list_iterator_has_next(linked_list_iterator_t * it){
|
---|
146 | // log_info("linked_list_iterator_has_next: advance on next %u, it->prev %p, it->curr %p", it->advance_on_next, it->prev, it->curr);
|
---|
147 | if (!it->advance_on_next){
|
---|
148 | return it->curr != NULL;
|
---|
149 | }
|
---|
150 | if (it->prev->next != it->curr){
|
---|
151 | // current item has been removed
|
---|
152 | return it->prev->next != NULL;
|
---|
153 | }
|
---|
154 | // current items has not been removed
|
---|
155 | return it->curr->next != NULL;
|
---|
156 | }
|
---|
157 |
|
---|
158 | linked_item_t * linked_list_iterator_next(linked_list_iterator_t * it){
|
---|
159 | if (it->advance_on_next){
|
---|
160 | if (it->prev->next == it->curr){
|
---|
161 | it->prev = it->curr;
|
---|
162 | it->curr = it->curr->next;
|
---|
163 | } else {
|
---|
164 | // curr was removed from the list, set it again but don't advance prev
|
---|
165 | it->curr = it->prev->next;
|
---|
166 | }
|
---|
167 | } else {
|
---|
168 | it->advance_on_next = 1;
|
---|
169 | }
|
---|
170 | return it->curr;
|
---|
171 | }
|
---|
172 |
|
---|
173 | void linked_list_iterator_remove(linked_list_iterator_t * it){
|
---|
174 | it->curr = it->curr->next;
|
---|
175 | it->prev->next = it->curr;
|
---|
176 | it->advance_on_next = 0;
|
---|
177 | }
|
---|