src/cx/list.h

Sat, 22 Jan 2022 19:10:04 +0100

author
Mike Becker <universe@uap-core.de>
date
Sat, 22 Jan 2022 19:10:04 +0100
changeset 497
b182a8b8a1af
parent 495
2856c74e18ba
child 499
3dc9075df822
permissions
-rw-r--r--

pointer type must be explicit in cx_foreach macro

390
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
28 /**
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
29 * \file list.h
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
30 * \brief Interface for list implementations.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
31 * \author Mike Becker
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
32 * \author Olaf Wintermann
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
33 * \version 3.0
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
34 * \copyright 2-Clause BSD License
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
35 */
390
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37 #ifndef UCX_LIST_H
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
38 #define UCX_LIST_H
d345541018fa starts ucx 3.0 development
Mike Becker <universe@uap-core.de>
parents:
diff changeset
39
484
9e6900b1cf9d add common.h include to all other header files
Mike Becker <universe@uap-core.de>
parents: 474
diff changeset
40 #include "common.h"
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
41 #include "allocator.h"
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
42 #include "iterator.h"
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
43
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
44 #ifdef __cplusplus
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
45 extern "C" {
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
46 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
47
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
48 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
49 * A comparator function comparing two list elements.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
50 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
51 typedef int(*CxListComparator)(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
52 void const *left,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
53 void const *right
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
54 );
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
55
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
56 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
57 * Internal type for the list structure - use CxList instead.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
58 */
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
59 typedef struct cx_list_s cx_list_s;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
60
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
61 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
62 * The class definition for arbitrary lists.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
63 */
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
64 typedef struct {
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
65 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
66 * Member function for adding an element.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
67 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
68 int (*add)(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
69 cx_list_s *list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
70 void const *elem
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
71 );
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
72
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
73 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
74 * Member function for inserting an element.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
75 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
76 int (*insert)(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
77 cx_list_s *list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
78 size_t index,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
79 void const *elem
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
80 );
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
81
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
82 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
83 * Member function for removing an element.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
84 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
85 int (*remove)(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
86 cx_list_s *list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
87 size_t index
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
88 );
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
89
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
90 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
91 * Member function for element lookup.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
92 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
93 void *(*at)(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
94 cx_list_s const *list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
95 size_t index
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
96 );
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
97
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
98 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
99 * Member function for finding an element.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
100 */
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
101 size_t (*find)(
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
102 cx_list_s const *list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
103 void const *elem
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
104 );
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
105
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
106 /**
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
107 * Member function for sorting the list in place.
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
108 */
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
109 void (*sort)(cx_list_s *list);
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
110
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
111 /**
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
112 * Member function for comparing this list to another list of the same type.
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
113 */
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
114 int (*compare)(
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
115 cx_list_s const *list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
116 cx_list_s const *other
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
117 );
490
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
118
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
119 /**
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
120 * Member function for reversing the order of the items.
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
121 */
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
122 void (*reverse)(cx_list_s *list);
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
123
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
124 /**
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
125 * Returns an iterator pointing to the specified index.
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
126 */
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
127 CxIterator (*iterator)(
495
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
128 cx_list_s *list,
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
129 size_t index
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
130 );
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
131 } cx_list_class;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
132
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
133 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
134 * Structure for holding the base data of a list.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
135 */
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
136 struct cx_list_s {
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
137 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
138 * The list class definition.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
139 */
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
140 cx_list_class *cl;
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
141 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
142 * The allocator to use.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
143 */
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
144 CxAllocator allocator;
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
145 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
146 * The comparator function for the elements.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
147 */
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
148 CxListComparator cmpfunc;
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
149 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
150 * The size of each element (payload only).
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
151 */
401
e6a8f7fb0c45 copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents: 398
diff changeset
152 size_t itemsize;
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
153 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
154 * The size of the list (number of currently stored elements).
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
155 */
401
e6a8f7fb0c45 copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents: 398
diff changeset
156 size_t size;
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
157 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
158 * The capacity of the list (maximum number of elements).
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
159 */
401
e6a8f7fb0c45 copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents: 398
diff changeset
160 size_t capacity;
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
161 };
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
162
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
163 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
164 * Common type for all list implementations.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
165 */
412
af766caea48d removes stupid high level wrapper for linked lists + adds test for cxLinkedListCreate
Mike Becker <universe@uap-core.de>
parents: 406
diff changeset
166 typedef cx_list_s *CxList;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
167
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
168 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
169 * Adds an item to the end of the list.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
170 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
171 * \remark It is implementation defined whether
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
172 * the contents of the element are copied or the
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
173 * pointer is added to the list. In the latter case
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
174 * the \c itemsize of the list SHALL be \c sizeof(void*).
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
175 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
176 * @param list the list
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
177 * @param elem a pointer to the element to add
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
178 * @return zero on success, non-zero on memory allocation failure
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
179 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
180 static inline int cxListAdd(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
181 CxList list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
182 void const *elem
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
183 ) {
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
184 return list->cl->add(list, elem);
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
185 }
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
186
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
187 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
188 * Inserts an item at the specified index.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
189 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
190 * If \p index equals the list \c size, this is effectively cxListAdd().
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
191 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
192 * \remark It is implementation defined whether
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
193 * the contents of the element are copied or the
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
194 * pointer is added to the list. In the latter case
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
195 * the \c itemsize of the list SHALL be \c sizeof(void*).
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
196 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
197 * @param list the list
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
198 * @param index the index the element shall have
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
199 * @param elem a pointer to the element to add
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
200 * @return zero on success, non-zero on memory allocation failure
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
201 * or when the index is out of bounds
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
202 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
203 static inline int cxListInsert(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
204 CxList list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
205 size_t index,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
206 void const *elem
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
207 ) {
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
208 return list->cl->insert(list, index, elem);
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
209 }
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
210
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
211 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
212 * Removes the element at the specified index.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
213 * @param list the list
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
214 * @param index the index of the element
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
215 * @return zero on success, non-zero if the index is out of bounds
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
216 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
217 static inline int cxListRemove(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
218 CxList list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
219 size_t index
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
220 ) {
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
221 return list->cl->remove(list, index);
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
222 }
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
223
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
224 /**
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
225 * Returns a pointer to the element at the specified index.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
226 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
227 * @param list the list
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
228 * @param index the index of the element
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
229 * @return a pointer to the element or \c NULL if the index is out of bounds
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
230 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
231 static inline void *cxListAt(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
232 CxList list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
233 size_t index
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
234 ) {
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
235 return list->cl->at(list, index);
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
236 }
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
237
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
238 /**
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
239 * Returns an iterator pointing to the item at the specified index.
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
240 *
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
241 * The returned iterator is position-aware.
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
242 *
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
243 * If the index is out of range, a past-the-end iterator will be returned.
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
244 *
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
245 * @param list the list
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
246 * @param index the index where the iterator shall point at
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
247 * @return a new iterator
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
248 */
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
249 static inline CxIterator cxListIterator(
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
250 CxList list,
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
251 size_t index
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
252 ) {
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
253 return list->cl->iterator(list, index);
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
254 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
255
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
256 /**
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
257 * Returns an iterator pointing to the first item of the list.
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
258 *
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
259 * The returned iterator is position-aware.
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
260 *
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
261 * If the list is empty, a past-the-end iterator will be returned.
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
262 *
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
263 * @param list the list
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
264 * @return a new iterator
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
265 */
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
266 static inline CxIterator cxListBegin(CxList list) {
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
267 return list->cl->iterator(list, 0);
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
268 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
269
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
270 /**
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
271 * Returns the index of the first element that equals \p elem.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
272 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
273 * Determining equality is performed by the list's comparator function.
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
274 *
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
275 * @param list the list
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
276 * @param elem the element to find
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
277 * @return the index of the element or \c (size+1) if the element is not found
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
278 */
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
279 static inline size_t cxListFind(
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
280 CxList list,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
281 void const *elem
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
282 ) {
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
283 return list->cl->find(list, elem);
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
284 }
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents: 393
diff changeset
285
464
7fafc95968fc add documentation for list.h
Mike Becker <universe@uap-core.de>
parents: 460
diff changeset
286 /**
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
287 * Sorts the list in place.
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
288 *
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
289 * \remark The underlying sort algorithm is implementation defined.
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
290 *
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
291 * @param list the list
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
292 */
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
293 static inline void cxListSort(CxList list) {
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
294 list->cl->sort(list);
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 464
diff changeset
295 }
404
86ebc3745e62 adds cxListLast
Mike Becker <universe@uap-core.de>
parents: 401
diff changeset
296
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
297 /**
490
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
298 * Reverses the order of the items.
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
299 *
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
300 * @param list the list
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
301 */
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
302 static inline void cxListReverse(CxList list) {
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
303 list->cl->reverse(list);
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
304 }
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
305
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
306 /**
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
307 * Compares a list to another list of the same type.
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
308 *
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
309 * First, the list sizes are compared. If they match, the lists are compared element-wise.
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
310 *
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
311 * @param list the list
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
312 * @param other the list to compare to
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
313 * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
314 */
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
315 static inline int cxListCompare(
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
316 CxList list,
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
317 CxList other
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
318 ) {
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
319 return list->cl->compare(list, other);
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
320 }
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
321
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
322 #ifdef __cplusplus
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
323 } /* extern "C" */
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
324 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
325
393
8c0421ccbb58 no C99 comments
Mike Becker <universe@uap-core.de>
parents: 390
diff changeset
326 #endif /* UCX_LIST_H */

mercurial