Contiki-NG
circular-list.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017, George Oikonomou - http://www.spd.gr
3  * Copyright (c) 2017, James Pope
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in the
14  * documentation and/or other materials provided with the distribution.
15  * 3. Neither the name of the copyright holder nor the names of its
16  * contributors may be used to endorse or promote products derived
17  * from this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
28  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
30  * OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32 /*---------------------------------------------------------------------------*/
33 /**
34  * \addtogroup circular-singly-linked-list
35  * @{
36  *
37  * \file
38  * Implementation of circular singly linked lists
39  */
40 /*---------------------------------------------------------------------------*/
41 #include "contiki.h"
42 #include "lib/circular-list.h"
43 
44 #include <stdint.h>
45 #include <stdbool.h>
46 #include <string.h>
47 /*---------------------------------------------------------------------------*/
48 struct cl {
49  struct cl *next;
50 };
51 /*---------------------------------------------------------------------------*/
52 void
54 {
55  *cl = NULL;
56 }
57 /*---------------------------------------------------------------------------*/
58 void *
60 {
61  return *cl;
62 }
63 /*---------------------------------------------------------------------------*/
64 void *
66 {
67  struct cl *this;
68 
69  if(*cl == NULL) {
70  return NULL;
71  }
72 
73  for(this = *cl; this->next != *cl; this = this->next);
74 
75  return this;
76 }
77 /*---------------------------------------------------------------------------*/
78 void
80 {
81  struct cl *this, *previous;
82 
83  if(*cl == NULL) {
84  return;
85  }
86 
87  /*
88  * We start traversing from the second element.
89  * The head will be visited last. We always update the list's head after
90  * removal, just in case we have just removed the head.
91  */
92  previous = *cl;
93  this = previous->next;
94 
95  do {
96  if(this == element) {
97  previous->next = this->next;
98  *cl = this->next == this ? NULL : previous;
99  return;
100  }
101  previous = this;
102  this = this->next;
103  } while(this != ((struct cl *)*cl)->next);
104 }
105 /*---------------------------------------------------------------------------*/
106 void
108 {
109  struct cl *head;
110 
111  if(element == NULL) {
112  return;
113  }
114 
115  /* Don't add twice */
116  circular_list_remove(cl, element);
117 
118  head = *cl;
119 
120  if(head == NULL) {
121  /* If the list was empty, we update the new element to point to itself */
122  ((struct cl *)element)->next = element;
123  } else {
124  /* If the list exists, we add the new element between the current head and
125  * the previously second element. */
126  ((struct cl *)element)->next = head->next;
127  head->next = element;
128  }
129 
130  /* In all cases, the new element becomes the list's new head */
131  *cl = element;
132 }
133 /*---------------------------------------------------------------------------*/
134 unsigned long
136 {
137  unsigned long len = 1;
138  struct cl *this;
139 
140  if(circular_list_is_empty(cl)) {
141  return 0;
142  }
143 
144  for(this = *cl; this->next != *cl; this = this->next) {
145  len++;
146  }
147 
148  return len;
149 }
150 /*---------------------------------------------------------------------------*/
151 bool
153 {
154  return *cl == NULL ? true : false;
155 }
156 /*---------------------------------------------------------------------------*/
157 /** @} */
void circular_list_init(circular_list_t cl)
Initialise a circular, singly-linked list.
Definition: circular-list.c:53
unsigned long circular_list_length(circular_list_t cl)
Get the length of a circular, singly-linked list.
void * circular_list_head(circular_list_t cl)
Return the tail of a circular, singly-linked list.
Definition: circular-list.c:59
void circular_list_add(circular_list_t cl, void *element)
Add an element to a circular, singly-linked list.
void * circular_list_tail(circular_list_t cl)
Return the tail of a circular, singly-linked list.
Definition: circular-list.c:65
bool circular_list_is_empty(circular_list_t cl)
Determine whether a circular, singly-linked list is empty.
void ** circular_list_t
The circular, singly-linked list datatype.
Definition: circular-list.h:84
void circular_list_remove(circular_list_t cl, void *element)
Remove an element from a circular, singly-linked list.
Definition: circular-list.c:79