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 "btstack_debug.h" 48 49 /** 50 * tests if list is empty 51 */ 52 bool btstack_linked_list_empty(btstack_linked_list_t * list){ 53 return *list == (void *) 0; 54 } 55 56 /** 57 * btstack_linked_list_get_last_item 58 */ 59 btstack_linked_item_t * btstack_linked_list_get_last_item(btstack_linked_list_t * list){ // <-- find the last item in the list 60 btstack_linked_item_t *lastItem = NULL; 61 btstack_linked_item_t *it; 62 for (it = *list; it != NULL; it = it->next){ 63 if (it != NULL) { 64 lastItem = it; 65 } 66 } 67 return lastItem; 68 } 69 70 71 /** 72 * btstack_linked_list_add 73 */ 74 bool btstack_linked_list_add(btstack_linked_list_t * list, btstack_linked_item_t *item){ // <-- add item to list 75 // check if already in list 76 btstack_linked_item_t *it; 77 for (it = *list; it != NULL; it = it->next){ 78 if (it == item) { 79 return false; 80 } 81 } 82 // add first 83 item->next = *list; 84 *list = item; 85 return true; 86 } 87 88 bool 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 != NULL ; it = it->next){ 92 if (it->next == item) { 93 return false; 94 } 95 } 96 item->next = (btstack_linked_item_t*) 0; 97 it->next = item; 98 return true; 99 } 100 101 bool btstack_linked_list_remove(btstack_linked_list_t * list, btstack_linked_item_t *item){ // <-- remove item from list 102 if (!item) return false; 103 btstack_linked_item_t *it; 104 for (it = (btstack_linked_item_t *) list; it != NULL; it = it->next){ 105 if (it->next == item){ 106 it->next = item->next; 107 return true; 108 } 109 } 110 return false; 111 } 112 113 /** 114 * @returns number of items in list 115 */ 116 int btstack_linked_list_count(btstack_linked_list_t * list){ 117 btstack_linked_item_t *it; 118 int counter = 0; 119 for (it = (btstack_linked_item_t *) list; it->next != NULL; it = it->next) { 120 counter++; 121 } 122 return counter; 123 } 124 125 // get first element 126 btstack_linked_item_t * btstack_linked_list_get_first_item(btstack_linked_list_t * list){ 127 return * list; 128 } 129 130 // pop (get + remove) first element 131 btstack_linked_item_t * btstack_linked_list_pop(btstack_linked_list_t * list){ 132 btstack_linked_item_t * item = *list; 133 if (!item) return NULL; 134 *list = item->next; 135 return item; 136 } 137 138 139 // 140 // Linked List Iterator implementation 141 // 142 143 void btstack_linked_list_iterator_init(btstack_linked_list_iterator_t * it, btstack_linked_list_t * list){ 144 it->advance_on_next = 0; 145 it->prev = (btstack_linked_item_t*) list; 146 it->curr = * list; 147 } 148 149 bool btstack_linked_list_iterator_has_next(btstack_linked_list_iterator_t * it){ 150 // 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); 151 if (!it->advance_on_next){ 152 return it->curr != NULL; 153 } 154 if (it->prev->next != it->curr){ 155 // current item has been removed 156 return it->prev->next != NULL; 157 } 158 // current items has not been removed 159 return it->curr->next != NULL; 160 } 161 162 btstack_linked_item_t * btstack_linked_list_iterator_next(btstack_linked_list_iterator_t * it){ 163 if (it->advance_on_next){ 164 if (it->prev->next == it->curr){ 165 it->prev = it->curr; 166 it->curr = it->curr->next; 167 } else { 168 // curr was removed from the list, set it again but don't advance prev 169 it->curr = it->prev->next; 170 } 171 } else { 172 it->advance_on_next = 1; 173 } 174 return it->curr; 175 } 176 177 void btstack_linked_list_iterator_remove(btstack_linked_list_iterator_t * it){ 178 btstack_assert(it->prev->next == it->curr); 179 it->curr = it->curr->next; 180 it->prev->next = it->curr; 181 it->advance_on_next = 0; 182 } 183