Mercurial > hg > octave-shane > gnulib-hg
annotate lib/gl_sublist.c @ 15727:144db791c6fa
Ensure EBADF returns for socket functions on mingw.
* lib/accept.c (rpl_accept): Fail with error EBADF if the file
descriptor is invalid.
* lib/bind.c (rpl_bind): Likewise.
* lib/connect.c (rpl_connect): Likewise.
* lib/getpeername.c (rpl_getpeername): Likewise.
* lib/getsockname.c (rpl_getsockname): Likewise.
* lib/getsockopt.c (rpl_getsockopt): Likewise.
* lib/listen.c (rpl_listen): Likewise.
* lib/recv.c (rpl_recv): Likewise.
* lib/recvfrom.c (rpl_recvfrom): Likewise.
* lib/send.c (rpl_send): Likewise.
* lib/sendto.c (rpl_sendto): Likewise.
* lib/setsockopt.c (rpl_setsockopt): Likewise.
* lib/shutdown.c (rpl_shutdown): Likewise.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Wed, 21 Sep 2011 00:20:59 +0200 |
| parents | 97fc9a21a8fb |
| children | 8250f2777afc |
| rev | line source |
|---|---|
| 7420 | 1 /* Sequential list data type backed by another list. |
|
14079
97fc9a21a8fb
maint: update almost all copyright ranges to include 2011
Jim Meyering <meyering@redhat.com>
parents:
12559
diff
changeset
|
2 Copyright (C) 2006-2011 Free Software Foundation, Inc. |
| 7420 | 3 Written by Bruno Haible <bruno@clisp.org>, 2006. |
| 4 | |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8438
diff
changeset
|
5 This program is free software: you can redistribute it and/or modify |
| 7420 | 6 it under the terms of the GNU General Public License as published by |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8438
diff
changeset
|
7 the Free Software Foundation; either version 3 of the License, or |
|
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8438
diff
changeset
|
8 (at your option) any later version. |
| 7420 | 9 |
| 10 This program is distributed in the hope that it will be useful, | |
| 11 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 13 GNU General Public License for more details. | |
| 14 | |
| 15 You should have received a copy of the GNU General Public License | |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8438
diff
changeset
|
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
| 7420 | 17 |
| 18 #include <config.h> | |
| 19 | |
| 20 /* Specification. */ | |
| 21 #include "gl_sublist.h" | |
| 22 | |
| 23 #include <stdlib.h> | |
| 24 | |
| 25 #ifndef uintptr_t | |
| 26 # define uintptr_t unsigned long | |
| 27 #endif | |
| 28 | |
| 29 /* -------------------------- gl_list_t Data Type -------------------------- */ | |
| 30 | |
| 31 /* Concrete gl_list_impl type, valid for this file only. */ | |
| 32 struct gl_list_impl | |
| 33 { | |
| 34 struct gl_list_impl_base base; | |
| 35 /* Reference to the whole list. */ | |
| 36 gl_list_t whole; | |
| 37 /* Limits of the index range. */ | |
| 38 size_t start; | |
| 39 size_t end; | |
| 40 }; | |
| 41 | |
| 42 /* struct gl_list_node_impl doesn't exist here. The pointers are actually | |
| 43 indices + 1. (We don't use the whole list's gl_list_node_t implementation, | |
| 44 because gl_sublist_next_node and gl_sublist_previous_node would not be easy | |
| 45 to implement with this choice.) */ | |
| 46 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1) | |
| 47 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) | |
| 48 | |
| 49 static gl_list_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
50 gl_sublist_nx_create_empty (gl_list_implementation_t implementation, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
51 gl_listelement_equals_fn equals_fn, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
52 gl_listelement_hashcode_fn hashcode_fn, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
53 gl_listelement_dispose_fn dispose_fn, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
54 bool allow_duplicates) |
| 7420 | 55 { |
| 56 /* Shouldn't be called. */ | |
| 57 abort (); | |
| 58 } | |
| 59 | |
| 60 static gl_list_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
61 gl_sublist_nx_create_fill (gl_list_implementation_t implementation, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
62 gl_listelement_equals_fn equals_fn, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
63 gl_listelement_hashcode_fn hashcode_fn, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
64 gl_listelement_dispose_fn dispose_fn, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
65 bool allow_duplicates, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
66 size_t count, const void **contents) |
| 7420 | 67 { |
| 68 /* Shouldn't be called. */ | |
| 69 abort (); | |
| 70 } | |
| 71 | |
| 72 static size_t | |
| 73 gl_sublist_size (gl_list_t list) | |
| 74 { | |
| 75 return list->end - list->start; | |
| 76 } | |
| 77 | |
| 78 static const void * | |
| 79 gl_sublist_node_value (gl_list_t list, gl_list_node_t node) | |
| 80 { | |
| 81 uintptr_t index = NODE_TO_INDEX (node); | |
| 82 if (!(index < list->end - list->start)) | |
| 83 /* Invalid argument. */ | |
| 84 abort (); | |
| 85 return gl_list_get_at (list->whole, list->start + index); | |
| 86 } | |
| 87 | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
88 static int |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
89 gl_sublist_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt) |
|
9686
25f7280c9cf0
New abstract list operation 'node_set_value'.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
90 { |
|
25f7280c9cf0
New abstract list operation 'node_set_value'.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
91 uintptr_t index = NODE_TO_INDEX (node); |
|
25f7280c9cf0
New abstract list operation 'node_set_value'.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
92 if (!(index < list->end - list->start)) |
|
25f7280c9cf0
New abstract list operation 'node_set_value'.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
93 /* Invalid argument. */ |
|
25f7280c9cf0
New abstract list operation 'node_set_value'.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
94 abort (); |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
95 if (gl_list_nx_set_at (list->whole, list->start + index, elt) == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
96 return -1; |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
97 return 0; |
|
9686
25f7280c9cf0
New abstract list operation 'node_set_value'.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
98 } |
|
25f7280c9cf0
New abstract list operation 'node_set_value'.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
99 |
| 7420 | 100 static gl_list_node_t |
| 101 gl_sublist_next_node (gl_list_t list, gl_list_node_t node) | |
| 102 { | |
| 103 uintptr_t index = NODE_TO_INDEX (node); | |
| 104 size_t count = list->end - list->start; | |
| 105 if (!(index < count)) | |
| 106 /* Invalid argument. */ | |
| 107 abort (); | |
| 108 index++; | |
| 109 if (index < count) | |
| 110 return INDEX_TO_NODE (index); | |
| 111 else | |
| 112 return NULL; | |
| 113 } | |
| 114 | |
| 115 static gl_list_node_t | |
| 116 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node) | |
| 117 { | |
| 118 uintptr_t index = NODE_TO_INDEX (node); | |
| 119 if (!(index < list->end - list->start)) | |
| 120 /* Invalid argument. */ | |
| 121 abort (); | |
| 122 if (index > 0) | |
| 123 return INDEX_TO_NODE (index - 1); | |
| 124 else | |
| 125 return NULL; | |
| 126 } | |
| 127 | |
| 128 static const void * | |
| 129 gl_sublist_get_at (gl_list_t list, size_t position) | |
| 130 { | |
| 131 if (!(position < list->end - list->start)) | |
| 132 /* Invalid argument. */ | |
| 133 abort (); | |
| 134 return gl_list_get_at (list->whole, list->start + position); | |
| 135 } | |
| 136 | |
| 137 static gl_list_node_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
138 gl_sublist_nx_set_at (gl_list_t list, size_t position, const void *elt) |
| 7420 | 139 { |
| 140 if (!(position < list->end - list->start)) | |
| 141 /* Invalid argument. */ | |
| 142 abort (); | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
143 if (gl_list_nx_set_at (list->whole, list->start + position, elt) == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
144 return NULL; |
| 7420 | 145 return INDEX_TO_NODE (position); |
| 146 } | |
| 147 | |
| 148 static gl_list_node_t | |
| 149 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
150 const void *elt) |
| 7420 | 151 { |
| 152 if (!(start_index <= end_index && end_index <= list->end - list->start)) | |
| 153 /* Invalid arguments. */ | |
| 154 abort (); | |
| 155 { | |
| 156 size_t index = | |
| 157 gl_list_indexof_from_to (list->whole, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
158 list->start + start_index, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
159 list->start + end_index, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
160 elt); |
| 7420 | 161 if (index != (size_t)(-1)) |
| 162 return INDEX_TO_NODE (index - list->start); | |
| 163 else | |
| 164 return NULL; | |
| 165 } | |
| 166 } | |
| 167 | |
| 168 static size_t | |
| 169 gl_sublist_indexof_from_to (gl_list_t list, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
170 size_t start_index, size_t end_index, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
171 const void *elt) |
| 7420 | 172 { |
| 173 if (!(start_index <= end_index && end_index <= list->end - list->start)) | |
| 174 /* Invalid arguments. */ | |
| 175 abort (); | |
| 176 { | |
| 177 size_t index = | |
| 178 gl_list_indexof_from_to (list->whole, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
179 list->start + start_index, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
180 list->start + end_index, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
181 elt); |
| 7420 | 182 if (index != (size_t)(-1)) |
| 183 index -= list->start; | |
| 184 return index; | |
| 185 } | |
| 186 } | |
| 187 | |
| 188 static gl_list_node_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
189 gl_sublist_nx_add_first (gl_list_t list, const void *elt) |
| 7420 | 190 { |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
191 if (gl_list_nx_add_at (list->whole, list->start, elt) == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
192 return NULL; |
| 7420 | 193 list->end++; |
| 194 return INDEX_TO_NODE (0); | |
| 195 } | |
| 196 | |
| 197 static gl_list_node_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
198 gl_sublist_nx_add_last (gl_list_t list, const void *elt) |
| 7420 | 199 { |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
200 if (gl_list_nx_add_at (list->whole, list->end, elt) == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
201 return NULL; |
| 7420 | 202 list->end++; |
| 203 return INDEX_TO_NODE (list->end - list->start - 1); | |
| 204 } | |
| 205 | |
| 206 static gl_list_node_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
207 gl_sublist_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) |
| 7420 | 208 { |
| 209 size_t position = NODE_TO_INDEX (node); | |
| 210 if (!(position < list->end - list->start)) | |
| 211 /* Invalid argument. */ | |
| 212 abort (); | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
213 if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
214 return NULL; |
| 7420 | 215 list->end++; |
| 216 return INDEX_TO_NODE (position); | |
| 217 } | |
| 218 | |
| 219 static gl_list_node_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
220 gl_sublist_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) |
| 7420 | 221 { |
| 222 size_t position = NODE_TO_INDEX (node); | |
| 223 if (!(position < list->end - list->start)) | |
| 224 /* Invalid argument. */ | |
| 225 abort (); | |
| 226 position++; | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
227 if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
228 return NULL; |
| 7420 | 229 list->end++; |
| 230 return INDEX_TO_NODE (position); | |
| 231 } | |
| 232 | |
| 233 static gl_list_node_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
234 gl_sublist_nx_add_at (gl_list_t list, size_t position, const void *elt) |
| 7420 | 235 { |
| 236 if (!(position <= list->end - list->start)) | |
| 237 /* Invalid argument. */ | |
| 238 abort (); | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
239 if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
240 return NULL; |
| 7420 | 241 list->end++; |
| 242 return INDEX_TO_NODE (position); | |
| 243 } | |
| 244 | |
| 245 static bool | |
| 246 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node) | |
| 247 { | |
| 248 uintptr_t index = NODE_TO_INDEX (node); | |
| 249 if (!(index < list->end - list->start)) | |
| 250 /* Invalid argument. */ | |
| 251 abort (); | |
| 252 return gl_list_remove_at (list->whole, list->start + index); | |
| 253 } | |
| 254 | |
| 255 static bool | |
| 256 gl_sublist_remove_at (gl_list_t list, size_t position) | |
| 257 { | |
| 258 if (!(position < list->end - list->start)) | |
| 259 /* Invalid argument. */ | |
| 260 abort (); | |
| 261 return gl_list_remove_at (list->whole, list->start + position); | |
| 262 } | |
| 263 | |
| 264 static bool | |
| 265 gl_sublist_remove (gl_list_t list, const void *elt) | |
| 266 { | |
| 267 size_t position = | |
| 268 gl_list_indexof_from_to (list->whole, list->start, list->end, elt); | |
| 269 if (position == (size_t)(-1)) | |
| 270 return false; | |
| 271 else | |
| 272 return gl_list_remove_at (list->whole, position); | |
| 273 } | |
| 274 | |
| 275 static void | |
| 276 gl_sublist_list_free (gl_list_t list) | |
| 277 { | |
| 278 free (list); | |
| 279 } | |
| 280 | |
| 281 /* --------------------- gl_list_iterator_t Data Type --------------------- */ | |
| 282 | |
| 283 static gl_list_iterator_t | |
| 284 gl_sublist_iterator (gl_list_t list) | |
| 285 { | |
| 286 return gl_list_iterator_from_to (list->whole, list->start, list->end); | |
| 287 } | |
| 288 | |
| 289 static gl_list_iterator_t | |
| 290 gl_sublist_iterator_from_to (gl_list_t list, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
291 size_t start_index, size_t end_index) |
| 7420 | 292 { |
| 293 if (!(start_index <= end_index && end_index <= list->end - list->start)) | |
| 294 /* Invalid arguments. */ | |
| 295 abort (); | |
| 296 return gl_list_iterator_from_to (list->whole, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
297 list->start + start_index, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
298 list->start + end_index); |
| 7420 | 299 } |
| 300 | |
| 301 static bool | |
| 302 gl_sublist_iterator_next (gl_list_iterator_t *iterator, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
303 const void **eltp, gl_list_node_t *nodep) |
| 7420 | 304 { |
| 305 /* Shouldn't be called. */ | |
| 306 abort (); | |
| 307 } | |
| 308 | |
| 309 static void | |
| 310 gl_sublist_iterator_free (gl_list_iterator_t *iterator) | |
| 311 { | |
| 312 /* Shouldn't be called. */ | |
| 313 abort (); | |
| 314 } | |
| 315 | |
| 316 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ | |
| 317 | |
| 318 static gl_list_node_t | |
| 319 gl_sublist_sortedlist_search (gl_list_t list, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
320 gl_listelement_compar_fn compar, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
321 const void *elt) |
| 7420 | 322 { |
| 323 size_t index = | |
| 324 gl_sortedlist_indexof_from_to (list->whole, compar, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
325 list->start, list->end, elt); |
| 7420 | 326 if (index != (size_t)(-1)) |
| 327 return INDEX_TO_NODE (index - list->start); | |
| 328 else | |
| 329 return NULL; | |
| 330 } | |
| 331 | |
| 332 static gl_list_node_t | |
| 333 gl_sublist_sortedlist_search_from_to (gl_list_t list, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
334 gl_listelement_compar_fn compar, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
335 size_t low, size_t high, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
336 const void *elt) |
| 7420 | 337 { |
| 338 size_t index; | |
| 339 | |
| 340 if (!(low <= high && high <= list->end - list->start)) | |
| 341 /* Invalid arguments. */ | |
| 342 abort (); | |
| 343 | |
| 344 index = | |
| 345 gl_sortedlist_indexof_from_to (list->whole, compar, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
346 list->start + low, list->start + high, elt); |
| 7420 | 347 if (index != (size_t)(-1)) |
| 348 return INDEX_TO_NODE (index - list->start); | |
| 349 else | |
| 350 return NULL; | |
| 351 } | |
| 352 | |
| 353 static size_t | |
| 354 gl_sublist_sortedlist_indexof (gl_list_t list, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
355 gl_listelement_compar_fn compar, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
356 const void *elt) |
| 7420 | 357 { |
| 358 size_t index = | |
| 359 gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
360 elt); |
| 7420 | 361 if (index != (size_t)(-1)) |
| 362 index -= list->start; | |
| 363 return index; | |
| 364 } | |
| 365 | |
| 366 static size_t | |
| 367 gl_sublist_sortedlist_indexof_from_to (gl_list_t list, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
368 gl_listelement_compar_fn compar, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
369 size_t low, size_t high, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
370 const void *elt) |
| 7420 | 371 { |
| 372 size_t index; | |
| 373 | |
| 374 if (!(low <= high && high <= list->end - list->start)) | |
| 375 /* Invalid arguments. */ | |
| 376 abort (); | |
| 377 | |
| 378 index = gl_sortedlist_indexof_from_to (list->whole, compar, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
379 list->start + low, list->start + high, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
380 elt); |
| 7420 | 381 if (index != (size_t)(-1)) |
| 382 index -= list->start; | |
| 383 return index; | |
| 384 } | |
| 385 | |
| 386 static gl_list_node_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
387 gl_sublist_sortedlist_nx_add (gl_list_t list, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
388 gl_listelement_compar_fn compar, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
389 const void *elt) |
| 7420 | 390 { |
| 391 /* It's impossible to implement this method without risking to put the | |
| 392 whole list into unsorted order (namely, when the given ELT is smaller | |
| 393 or larger than all elements of the sublist). */ | |
| 394 abort (); | |
| 395 } | |
| 396 | |
| 397 static bool | |
| 398 gl_sublist_sortedlist_remove (gl_list_t list, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
399 gl_listelement_compar_fn compar, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
400 const void *elt) |
| 7420 | 401 { |
| 402 size_t index = gl_sublist_sortedlist_indexof (list, compar, elt); | |
| 403 if (index == (size_t)(-1)) | |
| 404 return false; | |
| 405 else | |
| 406 return gl_sublist_remove_at (list, index); | |
| 407 } | |
| 408 | |
| 409 | |
| 410 static const struct gl_list_implementation gl_sublist_list_implementation = | |
| 411 { | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
412 gl_sublist_nx_create_empty, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
413 gl_sublist_nx_create_fill, |
| 7420 | 414 gl_sublist_size, |
| 415 gl_sublist_node_value, | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
416 gl_sublist_node_nx_set_value, |
| 7420 | 417 gl_sublist_next_node, |
| 418 gl_sublist_previous_node, | |
| 419 gl_sublist_get_at, | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
420 gl_sublist_nx_set_at, |
| 7420 | 421 gl_sublist_search_from_to, |
| 422 gl_sublist_indexof_from_to, | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
423 gl_sublist_nx_add_first, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
424 gl_sublist_nx_add_last, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
425 gl_sublist_nx_add_before, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
426 gl_sublist_nx_add_after, |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
427 gl_sublist_nx_add_at, |
| 7420 | 428 gl_sublist_remove_node, |
| 429 gl_sublist_remove_at, | |
| 430 gl_sublist_remove, | |
| 431 gl_sublist_list_free, | |
| 432 gl_sublist_iterator, | |
| 433 gl_sublist_iterator_from_to, | |
| 434 gl_sublist_iterator_next, | |
| 435 gl_sublist_iterator_free, | |
| 436 gl_sublist_sortedlist_search, | |
| 437 gl_sublist_sortedlist_search_from_to, | |
| 438 gl_sublist_sortedlist_indexof, | |
| 439 gl_sublist_sortedlist_indexof_from_to, | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
440 gl_sublist_sortedlist_nx_add, |
| 7420 | 441 gl_sublist_sortedlist_remove |
| 442 }; | |
| 443 | |
| 444 gl_list_t | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
445 gl_sublist_nx_create (gl_list_t whole_list, size_t start_index, size_t end_index) |
| 7420 | 446 { |
| 447 if (!(start_index <= end_index && end_index <= gl_list_size (whole_list))) | |
| 448 /* Invalid arguments. */ | |
| 449 abort (); | |
| 450 { | |
|
12445
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
451 struct gl_list_impl *list = |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
452 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
453 |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
454 if (list == NULL) |
|
a8c91b846640
Move the malloc checking from module 'list' to new module 'xlist'.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
455 return NULL; |
| 7420 | 456 |
| 457 list->base.vtable = &gl_sublist_list_implementation; | |
| 458 list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */ | |
| 459 list->base.hashcode_fn = whole_list->base.hashcode_fn; /* actually unused */ | |
|
8438
238942284e2f
Allow the use of a destructor for the values stored in the list.
Bruno Haible <bruno@clisp.org>
parents:
7603
diff
changeset
|
460 list->base.dispose_fn = whole_list->base.dispose_fn; /* actually unused */ |
| 7420 | 461 list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */ |
| 462 if (whole_list->base.vtable == &gl_sublist_list_implementation) | |
| 463 { | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
464 /* Optimization of a sublist of a sublist: Collapse the two |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
465 indirections into a single indirection. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
466 list->whole = whole_list->whole; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
467 list->start = whole_list->start + start_index; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
468 list->end = whole_list->start + end_index; |
| 7420 | 469 } |
| 470 else | |
| 471 { | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
472 list->whole = whole_list; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
473 list->start = start_index; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9686
diff
changeset
|
474 list->end = end_index; |
| 7420 | 475 } |
| 476 | |
| 477 return list; | |
| 478 } | |
| 479 } |