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