Mercurial > hg > octave-shane > gnulib-hg
annotate lib/gl_sublist.c @ 7603:23f14c284219
Simplify xmalloc expressions. Add overflow check in xmalloc arguments.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Mon, 06 Nov 2006 13:03:10 +0000 |
| parents | 52a8ff5ade8a |
| children | 238942284e2f |
| rev | line source |
|---|---|
| 7420 | 1 /* Sequential list data type backed by another list. |
| 2 Copyright (C) 2006 Free Software Foundation, Inc. | |
| 3 Written by Bruno Haible <bruno@clisp.org>, 2006. | |
| 4 | |
| 5 This program is free software; you can redistribute it and/or modify | |
| 6 it under the terms of the GNU General Public License as published by | |
| 7 the Free Software Foundation; either version 2, or (at your option) | |
| 8 any later version. | |
| 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 | |
| 16 along with this program; if not, write to the Free Software Foundation, | |
| 17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ | |
| 18 | |
| 19 #include <config.h> | |
| 20 | |
| 21 /* Specification. */ | |
| 22 #include "gl_sublist.h" | |
| 23 | |
| 24 #include <stdlib.h> | |
| 25 | |
| 26 #include "xalloc.h" | |
| 27 | |
| 28 #ifndef uintptr_t | |
| 29 # define uintptr_t unsigned long | |
| 30 #endif | |
| 31 | |
| 32 /* -------------------------- gl_list_t Data Type -------------------------- */ | |
| 33 | |
| 34 /* Concrete gl_list_impl type, valid for this file only. */ | |
| 35 struct gl_list_impl | |
| 36 { | |
| 37 struct gl_list_impl_base base; | |
| 38 /* Reference to the whole list. */ | |
| 39 gl_list_t whole; | |
| 40 /* Limits of the index range. */ | |
| 41 size_t start; | |
| 42 size_t end; | |
| 43 }; | |
| 44 | |
| 45 /* struct gl_list_node_impl doesn't exist here. The pointers are actually | |
| 46 indices + 1. (We don't use the whole list's gl_list_node_t implementation, | |
| 47 because gl_sublist_next_node and gl_sublist_previous_node would not be easy | |
| 48 to implement with this choice.) */ | |
| 49 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1) | |
| 50 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) | |
| 51 | |
| 52 static gl_list_t | |
| 53 gl_sublist_create_empty (gl_list_implementation_t implementation, | |
| 54 gl_listelement_equals_fn equals_fn, | |
| 55 gl_listelement_hashcode_fn hashcode_fn, | |
| 56 bool allow_duplicates) | |
| 57 { | |
| 58 /* Shouldn't be called. */ | |
| 59 abort (); | |
| 60 } | |
| 61 | |
| 62 static gl_list_t | |
| 63 gl_sublist_create_fill (gl_list_implementation_t implementation, | |
| 64 gl_listelement_equals_fn equals_fn, | |
| 65 gl_listelement_hashcode_fn hashcode_fn, | |
| 66 bool allow_duplicates, | |
| 67 size_t count, const void **contents) | |
| 68 { | |
| 69 /* Shouldn't be called. */ | |
| 70 abort (); | |
| 71 } | |
| 72 | |
| 73 static size_t | |
| 74 gl_sublist_size (gl_list_t list) | |
| 75 { | |
| 76 return list->end - list->start; | |
| 77 } | |
| 78 | |
| 79 static const void * | |
| 80 gl_sublist_node_value (gl_list_t list, gl_list_node_t node) | |
| 81 { | |
| 82 uintptr_t index = NODE_TO_INDEX (node); | |
| 83 if (!(index < list->end - list->start)) | |
| 84 /* Invalid argument. */ | |
| 85 abort (); | |
| 86 return gl_list_get_at (list->whole, list->start + index); | |
| 87 } | |
| 88 | |
| 89 static gl_list_node_t | |
| 90 gl_sublist_next_node (gl_list_t list, gl_list_node_t node) | |
| 91 { | |
| 92 uintptr_t index = NODE_TO_INDEX (node); | |
| 93 size_t count = list->end - list->start; | |
| 94 if (!(index < count)) | |
| 95 /* Invalid argument. */ | |
| 96 abort (); | |
| 97 index++; | |
| 98 if (index < count) | |
| 99 return INDEX_TO_NODE (index); | |
| 100 else | |
| 101 return NULL; | |
| 102 } | |
| 103 | |
| 104 static gl_list_node_t | |
| 105 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node) | |
| 106 { | |
| 107 uintptr_t index = NODE_TO_INDEX (node); | |
| 108 if (!(index < list->end - list->start)) | |
| 109 /* Invalid argument. */ | |
| 110 abort (); | |
| 111 if (index > 0) | |
| 112 return INDEX_TO_NODE (index - 1); | |
| 113 else | |
| 114 return NULL; | |
| 115 } | |
| 116 | |
| 117 static const void * | |
| 118 gl_sublist_get_at (gl_list_t list, size_t position) | |
| 119 { | |
| 120 if (!(position < list->end - list->start)) | |
| 121 /* Invalid argument. */ | |
| 122 abort (); | |
| 123 return gl_list_get_at (list->whole, list->start + position); | |
| 124 } | |
| 125 | |
| 126 static gl_list_node_t | |
| 127 gl_sublist_set_at (gl_list_t list, size_t position, const void *elt) | |
| 128 { | |
| 129 if (!(position < list->end - list->start)) | |
| 130 /* Invalid argument. */ | |
| 131 abort (); | |
| 132 gl_list_set_at (list->whole, list->start + position, elt); | |
| 133 return INDEX_TO_NODE (position); | |
| 134 } | |
| 135 | |
| 136 static gl_list_node_t | |
| 137 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index, | |
| 138 const void *elt) | |
| 139 { | |
| 140 if (!(start_index <= end_index && end_index <= list->end - list->start)) | |
| 141 /* Invalid arguments. */ | |
| 142 abort (); | |
| 143 { | |
| 144 size_t index = | |
| 145 gl_list_indexof_from_to (list->whole, | |
| 146 list->start + start_index, | |
| 147 list->start + end_index, | |
| 148 elt); | |
| 149 if (index != (size_t)(-1)) | |
| 150 return INDEX_TO_NODE (index - list->start); | |
| 151 else | |
| 152 return NULL; | |
| 153 } | |
| 154 } | |
| 155 | |
| 156 static size_t | |
| 157 gl_sublist_indexof_from_to (gl_list_t list, | |
| 158 size_t start_index, size_t end_index, | |
| 159 const void *elt) | |
| 160 { | |
| 161 if (!(start_index <= end_index && end_index <= list->end - list->start)) | |
| 162 /* Invalid arguments. */ | |
| 163 abort (); | |
| 164 { | |
| 165 size_t index = | |
| 166 gl_list_indexof_from_to (list->whole, | |
| 167 list->start + start_index, | |
| 168 list->start + end_index, | |
| 169 elt); | |
| 170 if (index != (size_t)(-1)) | |
| 171 index -= list->start; | |
| 172 return index; | |
| 173 } | |
| 174 } | |
| 175 | |
| 176 static gl_list_node_t | |
| 177 gl_sublist_add_first (gl_list_t list, const void *elt) | |
| 178 { | |
| 179 gl_list_add_at (list->whole, list->start, elt); | |
| 180 list->end++; | |
| 181 return INDEX_TO_NODE (0); | |
| 182 } | |
| 183 | |
| 184 static gl_list_node_t | |
| 185 gl_sublist_add_last (gl_list_t list, const void *elt) | |
| 186 { | |
| 187 gl_list_add_at (list->whole, list->end, elt); | |
| 188 list->end++; | |
| 189 return INDEX_TO_NODE (list->end - list->start - 1); | |
| 190 } | |
| 191 | |
| 192 static gl_list_node_t | |
| 193 gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt) | |
| 194 { | |
| 195 size_t position = NODE_TO_INDEX (node); | |
| 196 if (!(position < list->end - list->start)) | |
| 197 /* Invalid argument. */ | |
| 198 abort (); | |
| 199 gl_list_add_at (list->whole, list->start + position, elt); | |
| 200 list->end++; | |
| 201 return INDEX_TO_NODE (position); | |
| 202 } | |
| 203 | |
| 204 static gl_list_node_t | |
| 205 gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt) | |
| 206 { | |
| 207 size_t position = NODE_TO_INDEX (node); | |
| 208 if (!(position < list->end - list->start)) | |
| 209 /* Invalid argument. */ | |
| 210 abort (); | |
| 211 position++; | |
| 212 gl_list_add_at (list->whole, list->start + position, elt); | |
| 213 list->end++; | |
| 214 return INDEX_TO_NODE (position); | |
| 215 } | |
| 216 | |
| 217 static gl_list_node_t | |
| 218 gl_sublist_add_at (gl_list_t list, size_t position, const void *elt) | |
| 219 { | |
| 220 if (!(position <= list->end - list->start)) | |
| 221 /* Invalid argument. */ | |
| 222 abort (); | |
| 223 gl_list_add_at (list->whole, list->start + position, elt); | |
| 224 list->end++; | |
| 225 return INDEX_TO_NODE (position); | |
| 226 } | |
| 227 | |
| 228 static bool | |
| 229 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node) | |
| 230 { | |
| 231 uintptr_t index = NODE_TO_INDEX (node); | |
| 232 if (!(index < list->end - list->start)) | |
| 233 /* Invalid argument. */ | |
| 234 abort (); | |
| 235 return gl_list_remove_at (list->whole, list->start + index); | |
| 236 } | |
| 237 | |
| 238 static bool | |
| 239 gl_sublist_remove_at (gl_list_t list, size_t position) | |
| 240 { | |
| 241 if (!(position < list->end - list->start)) | |
| 242 /* Invalid argument. */ | |
| 243 abort (); | |
| 244 return gl_list_remove_at (list->whole, list->start + position); | |
| 245 } | |
| 246 | |
| 247 static bool | |
| 248 gl_sublist_remove (gl_list_t list, const void *elt) | |
| 249 { | |
| 250 size_t position = | |
| 251 gl_list_indexof_from_to (list->whole, list->start, list->end, elt); | |
| 252 if (position == (size_t)(-1)) | |
| 253 return false; | |
| 254 else | |
| 255 return gl_list_remove_at (list->whole, position); | |
| 256 } | |
| 257 | |
| 258 static void | |
| 259 gl_sublist_list_free (gl_list_t list) | |
| 260 { | |
| 261 free (list); | |
| 262 } | |
| 263 | |
| 264 /* --------------------- gl_list_iterator_t Data Type --------------------- */ | |
| 265 | |
| 266 static gl_list_iterator_t | |
| 267 gl_sublist_iterator (gl_list_t list) | |
| 268 { | |
| 269 return gl_list_iterator_from_to (list->whole, list->start, list->end); | |
| 270 } | |
| 271 | |
| 272 static gl_list_iterator_t | |
| 273 gl_sublist_iterator_from_to (gl_list_t list, | |
| 274 size_t start_index, size_t end_index) | |
| 275 { | |
| 276 if (!(start_index <= end_index && end_index <= list->end - list->start)) | |
| 277 /* Invalid arguments. */ | |
| 278 abort (); | |
| 279 return gl_list_iterator_from_to (list->whole, | |
| 280 list->start + start_index, | |
| 281 list->start + end_index); | |
| 282 } | |
| 283 | |
| 284 static bool | |
| 285 gl_sublist_iterator_next (gl_list_iterator_t *iterator, | |
| 286 const void **eltp, gl_list_node_t *nodep) | |
| 287 { | |
| 288 /* Shouldn't be called. */ | |
| 289 abort (); | |
| 290 } | |
| 291 | |
| 292 static void | |
| 293 gl_sublist_iterator_free (gl_list_iterator_t *iterator) | |
| 294 { | |
| 295 /* Shouldn't be called. */ | |
| 296 abort (); | |
| 297 } | |
| 298 | |
| 299 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ | |
| 300 | |
| 301 static gl_list_node_t | |
| 302 gl_sublist_sortedlist_search (gl_list_t list, | |
| 303 gl_listelement_compar_fn compar, | |
| 304 const void *elt) | |
| 305 { | |
| 306 size_t index = | |
| 307 gl_sortedlist_indexof_from_to (list->whole, compar, | |
| 308 list->start, list->end, elt); | |
| 309 if (index != (size_t)(-1)) | |
| 310 return INDEX_TO_NODE (index - list->start); | |
| 311 else | |
| 312 return NULL; | |
| 313 } | |
| 314 | |
| 315 static gl_list_node_t | |
| 316 gl_sublist_sortedlist_search_from_to (gl_list_t list, | |
| 317 gl_listelement_compar_fn compar, | |
| 318 size_t low, size_t high, | |
| 319 const void *elt) | |
| 320 { | |
| 321 size_t index; | |
| 322 | |
| 323 if (!(low <= high && high <= list->end - list->start)) | |
| 324 /* Invalid arguments. */ | |
| 325 abort (); | |
| 326 | |
| 327 index = | |
| 328 gl_sortedlist_indexof_from_to (list->whole, compar, | |
| 329 list->start + low, list->start + high, elt); | |
| 330 if (index != (size_t)(-1)) | |
| 331 return INDEX_TO_NODE (index - list->start); | |
| 332 else | |
| 333 return NULL; | |
| 334 } | |
| 335 | |
| 336 static size_t | |
| 337 gl_sublist_sortedlist_indexof (gl_list_t list, | |
| 338 gl_listelement_compar_fn compar, | |
| 339 const void *elt) | |
| 340 { | |
| 341 size_t index = | |
| 342 gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end, | |
| 343 elt); | |
| 344 if (index != (size_t)(-1)) | |
| 345 index -= list->start; | |
| 346 return index; | |
| 347 } | |
| 348 | |
| 349 static size_t | |
| 350 gl_sublist_sortedlist_indexof_from_to (gl_list_t list, | |
| 351 gl_listelement_compar_fn compar, | |
| 352 size_t low, size_t high, | |
| 353 const void *elt) | |
| 354 { | |
| 355 size_t index; | |
| 356 | |
| 357 if (!(low <= high && high <= list->end - list->start)) | |
| 358 /* Invalid arguments. */ | |
| 359 abort (); | |
| 360 | |
| 361 index = gl_sortedlist_indexof_from_to (list->whole, compar, | |
| 362 list->start + low, list->start + high, | |
| 363 elt); | |
| 364 if (index != (size_t)(-1)) | |
| 365 index -= list->start; | |
| 366 return index; | |
| 367 } | |
| 368 | |
| 369 static gl_list_node_t | |
| 370 gl_sublist_sortedlist_add (gl_list_t list, | |
| 371 gl_listelement_compar_fn compar, | |
| 372 const void *elt) | |
| 373 { | |
| 374 /* It's impossible to implement this method without risking to put the | |
| 375 whole list into unsorted order (namely, when the given ELT is smaller | |
| 376 or larger than all elements of the sublist). */ | |
| 377 abort (); | |
| 378 } | |
| 379 | |
| 380 static bool | |
| 381 gl_sublist_sortedlist_remove (gl_list_t list, | |
| 382 gl_listelement_compar_fn compar, | |
| 383 const void *elt) | |
| 384 { | |
| 385 size_t index = gl_sublist_sortedlist_indexof (list, compar, elt); | |
| 386 if (index == (size_t)(-1)) | |
| 387 return false; | |
| 388 else | |
| 389 return gl_sublist_remove_at (list, index); | |
| 390 } | |
| 391 | |
| 392 | |
| 393 static const struct gl_list_implementation gl_sublist_list_implementation = | |
| 394 { | |
| 395 gl_sublist_create_empty, | |
| 396 gl_sublist_create_fill, | |
| 397 gl_sublist_size, | |
| 398 gl_sublist_node_value, | |
| 399 gl_sublist_next_node, | |
| 400 gl_sublist_previous_node, | |
| 401 gl_sublist_get_at, | |
| 402 gl_sublist_set_at, | |
| 403 gl_sublist_search_from_to, | |
| 404 gl_sublist_indexof_from_to, | |
| 405 gl_sublist_add_first, | |
| 406 gl_sublist_add_last, | |
| 407 gl_sublist_add_before, | |
| 408 gl_sublist_add_after, | |
| 409 gl_sublist_add_at, | |
| 410 gl_sublist_remove_node, | |
| 411 gl_sublist_remove_at, | |
| 412 gl_sublist_remove, | |
| 413 gl_sublist_list_free, | |
| 414 gl_sublist_iterator, | |
| 415 gl_sublist_iterator_from_to, | |
| 416 gl_sublist_iterator_next, | |
| 417 gl_sublist_iterator_free, | |
| 418 gl_sublist_sortedlist_search, | |
| 419 gl_sublist_sortedlist_search_from_to, | |
| 420 gl_sublist_sortedlist_indexof, | |
| 421 gl_sublist_sortedlist_indexof_from_to, | |
| 422 gl_sublist_sortedlist_add, | |
| 423 gl_sublist_sortedlist_remove | |
| 424 }; | |
| 425 | |
| 426 gl_list_t | |
| 427 gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index) | |
| 428 { | |
| 429 if (!(start_index <= end_index && end_index <= gl_list_size (whole_list))) | |
| 430 /* Invalid arguments. */ | |
| 431 abort (); | |
| 432 { | |
|
7603
23f14c284219
Simplify xmalloc expressions. Add overflow check in xmalloc arguments.
Bruno Haible <bruno@clisp.org>
parents:
7420
diff
changeset
|
433 struct gl_list_impl *list = XMALLOC (struct gl_list_impl); |
| 7420 | 434 |
| 435 list->base.vtable = &gl_sublist_list_implementation; | |
| 436 list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */ | |
| 437 list->base.hashcode_fn = whole_list->base.hashcode_fn; /* actually unused */ | |
| 438 list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */ | |
| 439 if (whole_list->base.vtable == &gl_sublist_list_implementation) | |
| 440 { | |
| 441 /* Optimization of a sublist of a sublist: Collapse the two | |
| 442 indirections into a single indirection. */ | |
| 443 list->whole = whole_list->whole; | |
| 444 list->start = whole_list->start + start_index; | |
| 445 list->end = whole_list->start + end_index; | |
| 446 } | |
| 447 else | |
| 448 { | |
| 449 list->whole = whole_list; | |
| 450 list->start = start_index; | |
| 451 list->end = end_index; | |
| 452 } | |
| 453 | |
| 454 return list; | |
| 455 } | |
| 456 } |