[337] | 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 | }
|
---|