Navigation


source: freeDiameter/libfdproto/lists.c

Last change on this file was 1127:1af09cc156d6, checked in by Sebastien Decugis <sdecugis@freediameter.net>, 8 years ago

Updated copyright information

File size: 5.3 KB
Line 
1/*********************************************************************************************************
2* Software License Agreement (BSD License)                                                               *
3* Author: Sebastien Decugis <sdecugis@freediameter.net>                                                  *
4*                                                                                                        *
5* Copyright (c) 2013, WIDE Project and NICT                                                              *
6* All rights reserved.                                                                                   *
7*                                                                                                        *
8* Redistribution and use of this software in source and binary forms, with or without modification, are  *
9* permitted provided that the following conditions are met:                                              *
10*                                                                                                        *
11* * Redistributions of source code must retain the above                                                 *
12*   copyright notice, this list of conditions and the                                                    *
13*   following disclaimer.                                                                                *
14*                                                                                                        *
15* * Redistributions in binary form must reproduce the above                                              *
16*   copyright notice, this list of conditions and the                                                    *
17*   following disclaimer in the documentation and/or other                                               *
18*   materials provided with the distribution.                                                            *
19*                                                                                                        *
20* * Neither the name of the WIDE Project or NICT nor the                                                 *
21*   names of its contributors may be used to endorse or                                                  *
22*   promote products derived from this software without                                                  *
23*   specific prior written permission of WIDE Project and                                                *
24*   NICT.                                                                                                *
25*                                                                                                        *
26* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED *
27* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
28* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR *
29* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT     *
30* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS    *
31* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR *
32* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF   *
33* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.                                                             *
34*********************************************************************************************************/
35
36#include "fdproto-internal.h"
37
38/* Initialize a list element */
39void fd_list_init ( struct fd_list * list, void * obj )
40{
41        memset(list, 0, sizeof(struct fd_list));
42        list->next = list;
43        list->prev = list;
44        list->head = list;
45        list->o    = obj;
46}
47
48#define CHECK_SINGLE( li ) {                    \
49        ASSERT( ((struct fd_list *)(li))->next == (li) );       \
50        ASSERT( ((struct fd_list *)(li))->prev == (li) );       \
51        ASSERT( ((struct fd_list *)(li))->head == (li) );       \
52}
53
54/* insert after a reference, checks done */
55static void list_insert_after( struct fd_list * ref, struct fd_list * item )
56{
57        item->prev = ref;
58        item->next = ref->next;
59        item->head = ref->head;
60        ref->next->prev = item;
61        ref->next = item;
62}
63
64/* insert after a reference */
65void fd_list_insert_after  ( struct fd_list * ref, struct fd_list * item )
66{
67        ASSERT(item != NULL);
68        ASSERT(ref != NULL);
69        CHECK_SINGLE ( item );
70        ASSERT(ref->head != item);
71        list_insert_after(ref, item);
72}
73
74/* Move all elements of list senti at the end of list ref */
75void fd_list_move_end(struct fd_list * ref, struct fd_list * senti)
76{
77        struct fd_list * li;
78        ASSERT(ref->head == ref);
79        ASSERT(senti->head == senti);
80       
81        if (senti->next == senti)
82                return;
83       
84        for (li = senti->next; li != senti; li = li->next)
85                li->head = ref;
86       
87        senti->next->prev = ref->prev;
88        ref->prev->next   = senti->next;
89        senti->prev->next = ref;
90        ref->prev         = senti->prev;
91        senti->prev = senti;
92        senti->next = senti;
93}
94
95/* insert before a reference, checks done */
96static void list_insert_before ( struct fd_list * ref, struct fd_list * item )
97{
98        item->prev = ref->prev;
99        item->next = ref;
100        item->head = ref->head;
101        ref->prev->next = item;
102        ref->prev = item;
103}
104
105/* insert before a reference */
106void fd_list_insert_before ( struct fd_list * ref, struct fd_list * item )
107{
108        ASSERT(item != NULL);
109        ASSERT(ref != NULL);
110        CHECK_SINGLE ( item );
111        ASSERT(ref->head != item);
112        list_insert_before(ref, item);
113}
114
115/* Insert an item in an ordered list -- ordering function provided. If duplicate object found, it is returned in ref_duplicate */
116int fd_list_insert_ordered( struct fd_list * head, struct fd_list * item, int (*cmp_fct)(void *, void *), void ** ref_duplicate)
117{
118        struct fd_list * ptr = head;
119        int cmp;
120       
121        /* Some debug sanity checks */
122        ASSERT(head != NULL);
123        ASSERT(item != NULL);
124        ASSERT(cmp_fct != NULL);
125        ASSERT(head->head == head);
126        CHECK_SINGLE ( item );
127       
128        /* loop in the list */
129        while (ptr->next != head)
130        {
131                /* Compare the object to insert with the next object in list */
132                cmp = cmp_fct( item->o, ptr->next->o );
133                if (!cmp) {
134                        /* An element with the same key already exists */
135                        if (ref_duplicate != NULL)
136                                *ref_duplicate = ptr->next->o;
137                        return EEXIST;
138                }
139               
140                if (cmp < 0)
141                        break; /* We must insert the element here */
142               
143                ptr = ptr->next;
144        }
145       
146        /* Now insert the element between ptr and ptr->next */
147        list_insert_after( ptr, item );
148       
149        /* Ok */
150        return 0;
151}
152       
153/* Unlink an object */
154void fd_list_unlink ( struct fd_list * item )
155{
156        ASSERT(item != NULL);
157        if (item->head == item)
158                return;
159        /* unlink */
160        item->next->prev = item->prev;
161        item->prev->next = item->next;
162        /* sanitize */
163        item->next = item;
164        item->prev = item;
165        item->head = item;
166}
167
168
Note: See TracBrowser for help on using the repository browser.