1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 
3 /**
4  * @copyright 2013 Couchbase, Inc.
5  *
6  * @author Filipe Manana  <filipe@couchbase.com>
7  *
8  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
9  * use this file except in compliance with the License. You may obtain a copy of
10  * the License at
11  *
12  *  http://www.apache.org/licenses/LICENSE-2.0
13  *
14  * Unless required by applicable law or agreed to in writing, software
15  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
16  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
17  * License for the specific language governing permissions and limitations under
18  * the License.
19  **/
20 
21 #include <stdlib.h>
22 #include <assert.h>
23 #include <string.h>
24 #include "sorted_list.h"
25 
26 
27 typedef struct sorted_list_node_t {
28     void *element;
29     struct sorted_list_node_t *next;
30 } sorted_list_node_t;
31 
32 typedef struct {
33     sorted_list_cmp_t cmp_fun;
34     sorted_list_node_t *head;
35     int length;
36 } sorted_list_t;
37 
38 typedef struct {
39     sorted_list_node_t *current;
40 } sorted_list_iterator_t;
41 
42 
sorted_list_create(sorted_list_cmp_t cmp_fun)43 void *sorted_list_create(sorted_list_cmp_t cmp_fun)
44 {
45     sorted_list_t *list = (sorted_list_t *) malloc(sizeof(sorted_list_t));
46 
47     if (list != NULL) {
48         list->cmp_fun = cmp_fun;
49         list->head = NULL;
50         list->length = 0;
51     }
52 
53     return (void *) list;
54 }
55 
56 
sorted_list_add(void *list, const void *elem, size_t elem_size)57 int sorted_list_add(void *list, const void *elem, size_t elem_size)
58 {
59     sorted_list_t *l = (sorted_list_t *) list;
60     sorted_list_node_t *n = l->head;
61     sorted_list_node_t *prev = NULL;
62     sorted_list_node_t *new_node;
63     int cmp = 0;
64 
65     new_node = (sorted_list_node_t *) malloc(sizeof(sorted_list_node_t));
66     if (new_node == NULL) {
67         return -1;
68     }
69     new_node->element = malloc(elem_size);
70     if (new_node->element == NULL) {
71         free(new_node);
72         return -1;
73     }
74     memcpy(new_node->element, elem, elem_size);
75 
76     if (l->head == NULL) {
77         new_node->next = NULL;
78         l->head = new_node;
79         l->length += 1;
80         return 0;
81     }
82 
83     while (n != NULL) {
84         cmp = l->cmp_fun(n->element, elem);
85         if (cmp >= 0) {
86             break;
87         }
88         prev = n;
89         n = n->next;
90     }
91 
92     if (prev != NULL) {
93         prev->next = new_node;
94     } else {
95         l->head = new_node;
96     }
97 
98     if (cmp == 0) {
99         new_node->next = n->next;
100         free(n->element);
101         free(n);
102     } else {
103         l->length += 1;
104         new_node->next = n;
105     }
106 
107     return 0;
108 }
109 
110 
sorted_list_get(const void *list, const void *elem)111 void *sorted_list_get(const void *list, const void *elem)
112 {
113     const sorted_list_t *l = (const sorted_list_t *) list;
114     sorted_list_node_t *n = l->head;
115     int cmp;
116 
117     while (n != NULL) {
118         cmp = l->cmp_fun(n->element, elem);
119         if (cmp == 0) {
120             return n->element;
121         } else if (cmp > 0) {
122             return NULL;
123         } else {
124             n = n->next;
125         }
126     }
127 
128     return n;
129 }
130 
131 
sorted_list_remove(void *list, const void *elem)132 void sorted_list_remove(void *list, const void *elem)
133 {
134     sorted_list_t *l = (sorted_list_t *) list;
135     sorted_list_node_t *n = l->head;
136     sorted_list_node_t *prev = NULL;
137     int cmp;
138 
139     while (n != NULL) {
140         cmp = l->cmp_fun(n->element, elem);
141         if (cmp == 0) {
142             if (prev == NULL) {
143                 assert(n == l->head);
144                 l->head = n->next;
145             } else {
146                 prev->next = n->next;
147             }
148             l->length -= 1;
149             free(n->element);
150             free(n);
151             break;
152         } else if (cmp > 0) {
153             return;
154         } else {
155             prev = n;
156             n = n->next;
157         }
158     }
159 }
160 
161 
sorted_list_free(void *list)162 void sorted_list_free(void *list)
163 {
164     sorted_list_t *l = (sorted_list_t *) list;
165     sorted_list_node_t *n = NULL;
166 
167     if (l != NULL) {
168         while (l->head != NULL) {
169             n = l->head;
170             l->head = l->head->next;
171             free(n->element);
172             free(n);
173         }
174         free(list);
175     }
176 }
177 
178 
sorted_list_size(const void *list)179 int sorted_list_size(const void *list)
180 {
181     const sorted_list_t *l = (const sorted_list_t *) list;
182 
183     return l->length;
184 }
185 
186 
sorted_list_iterator(const void *list)187 void *sorted_list_iterator(const void *list)
188 {
189    const sorted_list_t *l = (const sorted_list_t *) list;
190    sorted_list_iterator_t *it = NULL;
191 
192    it = (sorted_list_iterator_t *) malloc(sizeof(*it));
193    if (it != NULL) {
194        it->current = l->head;
195    }
196 
197    return (void *) it;
198 }
199 
200 
sorted_list_next(void *iterator)201 void *sorted_list_next(void *iterator)
202 {
203     sorted_list_iterator_t *it = (sorted_list_iterator_t *) iterator;
204     void *elem = NULL;
205 
206     if (it->current != NULL) {
207         elem = it->current->element;
208         it->current = it->current->next;
209     }
210 
211     return elem;
212 }
213 
214 
sorted_list_free_iterator(void *iterator)215 void sorted_list_free_iterator(void *iterator)
216 {
217     free(iterator);
218 }
219