xref: /btstack/src/btstack_linked_list.c (revision ab2c6ae4b737d5e801d3defe4117331eb244ebb7)
1 /*
2  * Copyright (C) 2014 BlueKitchen GmbH
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 BLUEKITCHEN GMBH 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
34  * [email protected]
35  *
36  */
37 
38 #define __BTSTACK_FILE__ "btstack_linked_list.c"
39 
40 /*
41  *  linked_list.c
42  *
43  *  Created by Matthias Ringwald on 7/13/09.
44  */
45 
46 #include "btstack_linked_list.h"
47 #include <stdlib.h>
48 #include <stdio.h>
49 
50 /**
51  * tests if list is empty
52  */
53 int  btstack_linked_list_empty(btstack_linked_list_t * list){
54     return *list == (void *) 0;
55 }
56 
57 /**
58  * btstack_linked_list_get_last_item
59  */
60 btstack_linked_item_t * btstack_linked_list_get_last_item(btstack_linked_list_t * list){        // <-- find the last item in the list
61     btstack_linked_item_t *lastItem = NULL;
62     btstack_linked_item_t *it;
63     for (it = *list; it ; it = it->next){
64         if (it) {
65             lastItem = it;
66         }
67     }
68     return lastItem;
69 }
70 
71 
72 /**
73  * btstack_linked_list_add
74  */
75 void btstack_linked_list_add(btstack_linked_list_t * list, btstack_linked_item_t *item){        // <-- add item to list
76     // check if already in list
77     btstack_linked_item_t *it;
78     for (it = *list; it ; it = it->next){
79         if (it == item) {
80             return;
81         }
82     }
83     // add first
84     item->next = *list;
85     *list = item;
86 }
87 
88 void btstack_linked_list_add_tail(btstack_linked_list_t * list, btstack_linked_item_t *item){   // <-- add item to list as last element
89     // check if already in list
90     btstack_linked_item_t *it;
91     for (it = (btstack_linked_item_t *) list; it->next ; it = it->next){
92         if (it->next == item) {
93             return;
94         }
95     }
96     item->next = (btstack_linked_item_t*) 0;
97     it->next = item;
98 }
99 
100 int  btstack_linked_list_remove(btstack_linked_list_t * list, btstack_linked_item_t *item){    // <-- remove item from list
101     if (!item) return -1;
102     btstack_linked_item_t *it;
103     for (it = (btstack_linked_item_t *) list; it ; it = it->next){
104         if (it->next == item){
105             it->next =  item->next;
106             return 0;
107         }
108     }
109     return -1;
110 }
111 
112 /**
113  * @returns number of items in list
114  */
115  int btstack_linked_list_count(btstack_linked_list_t * list){
116     btstack_linked_item_t *it;
117     int counter = 0;
118     for (it = (btstack_linked_item_t *) list; it->next ; it = it->next) {
119         counter++;
120     }
121     return counter;
122 }
123 
124 // get first element
125 btstack_linked_item_t * btstack_linked_list_get_first_item(btstack_linked_list_t * list){
126     return * list;
127 }
128 
129 // pop (get + remove) first element
130 btstack_linked_item_t * btstack_linked_list_pop(btstack_linked_list_t * list){
131     btstack_linked_item_t * item = *list;
132     if (!item) return NULL;
133     *list = item->next;
134     return item;
135 }
136 
137 
138 //
139 // Linked List Iterator implementation
140 //
141 
142 void btstack_linked_list_iterator_init(btstack_linked_list_iterator_t * it, btstack_linked_list_t * head){
143     it->advance_on_next = 0;
144     it->prev = (btstack_linked_item_t*) head;
145     it->curr = * head;
146 }
147 
148 int btstack_linked_list_iterator_has_next(btstack_linked_list_iterator_t * it){
149     // log_info("btstack_linked_list_iterator_has_next: advance on next %u, it->prev %p, it->curr %p", it->advance_on_next, it->prev, it->curr);
150     if (!it->advance_on_next){
151         return it->curr != NULL;
152     }
153     if (it->prev->next != it->curr){
154         // current item has been removed
155         return it->prev->next != NULL;
156     }
157     // current items has not been removed
158     return it->curr->next != NULL;
159 }
160 
161 btstack_linked_item_t * btstack_linked_list_iterator_next(btstack_linked_list_iterator_t * it){
162     if (it->advance_on_next){
163         if (it->prev->next == it->curr){
164             it->prev = it->curr;
165             it->curr = it->curr->next;
166         } else {
167             // curr was removed from the list, set it again but don't advance prev
168             it->curr = it->prev->next;
169         }
170     } else {
171         it->advance_on_next = 1;
172     }
173     return it->curr;
174 }
175 
176 void btstack_linked_list_iterator_remove(btstack_linked_list_iterator_t * it){
177     it->curr = it->curr->next;
178     it->prev->next = it->curr;
179     it->advance_on_next = 0;
180 }
181