1 /* Set data type implemented by an array.
2 Copyright (C) 2006-2020 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2018.
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 3 of the License, or
8 (at your option) any later version.
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.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
21 #include "gl_array_set.h"
26 /* Checked size_t computations. */
29 /* --------------------------- gl_set_t Data Type --------------------------- */
31 /* Concrete gl_set_impl type, valid for this file only. */
34 struct gl_set_impl_base base
;
35 /* An array of ALLOCATED elements, of which the first COUNT are used.
36 0 <= COUNT <= ALLOCATED. */
37 const void **elements
;
43 gl_array_nx_create_empty (gl_set_implementation_t implementation
,
44 gl_setelement_equals_fn equals_fn
,
45 gl_setelement_hashcode_fn hashcode_fn
,
46 gl_setelement_dispose_fn dispose_fn
)
48 struct gl_set_impl
*set
=
49 (struct gl_set_impl
*) malloc (sizeof (struct gl_set_impl
));
54 set
->base
.vtable
= implementation
;
55 set
->base
.equals_fn
= equals_fn
;
56 set
->base
.dispose_fn
= dispose_fn
;
65 gl_array_size (gl_set_t set
)
71 gl_array_search (gl_set_t set
, const void *elt
)
73 size_t count
= set
->count
;
77 gl_setelement_equals_fn equals
= set
->base
.equals_fn
;
78 const void **elements
= set
->elements
;
83 for (i
= 0; i
< count
; i
++)
84 if (equals (elements
[i
], elt
))
91 for (i
= 0; i
< count
; i
++)
92 if (elements
[i
] == elt
)
99 /* Ensure that set->allocated > set->count.
100 Return 0 upon success, -1 upon out-of-memory. */
104 size_t new_allocated
;
108 new_allocated
= xtimes (set
->allocated
, 2);
109 new_allocated
= xsum (new_allocated
, 1);
110 memory_size
= xtimes (new_allocated
, sizeof (const void *));
111 if (size_overflow_p (memory_size
))
112 /* Overflow, would lead to out of memory. */
114 memory
= (const void **) realloc (set
->elements
, memory_size
);
118 set
->elements
= memory
;
119 set
->allocated
= new_allocated
;
124 gl_array_nx_add (gl_set_t set
, const void *elt
)
126 if (gl_array_search (set
, elt
))
130 size_t count
= set
->count
;
132 if (count
== set
->allocated
)
135 set
->elements
[count
] = elt
;
136 set
->count
= count
+ 1;
141 /* Remove the element at the given position,
142 0 <= position < gl_set_size (set). */
144 gl_array_remove_at (gl_set_t set
, size_t position
)
146 size_t count
= set
->count
;
147 const void **elements
= set
->elements
;
150 if (set
->base
.dispose_fn
!= NULL
)
151 set
->base
.dispose_fn (elements
[position
]);
152 for (i
= position
+ 1; i
< count
; i
++)
153 elements
[i
- 1] = elements
[i
];
154 set
->count
= count
- 1;
158 gl_array_remove (gl_set_t set
, const void *elt
)
160 size_t count
= set
->count
;
164 gl_setelement_equals_fn equals
= set
->base
.equals_fn
;
165 const void **elements
= set
->elements
;
171 for (i
= 0; i
< count
; i
++)
172 if (equals (elements
[i
], elt
))
174 gl_array_remove_at (set
, i
);
182 for (i
= 0; i
< count
; i
++)
183 if (elements
[i
] == elt
)
185 gl_array_remove_at (set
, i
);
194 gl_array_free (gl_set_t set
)
196 if (set
->elements
!= NULL
)
198 if (set
->base
.dispose_fn
!= NULL
)
200 size_t count
= set
->count
;
204 gl_setelement_dispose_fn dispose
= set
->base
.dispose_fn
;
205 const void **elements
= set
->elements
;
208 dispose (*elements
++);
212 free (set
->elements
);
217 /* ---------------------- gl_set_iterator_t Data Type ---------------------- */
219 static gl_set_iterator_t
220 gl_array_iterator (gl_set_t set
)
222 gl_set_iterator_t result
;
224 result
.vtable
= set
->base
.vtable
;
226 result
.count
= set
->count
;
227 result
.p
= set
->elements
+ 0;
228 result
.q
= set
->elements
+ set
->count
;
229 #if defined GCC_LINT || defined lint
238 gl_array_iterator_next (gl_set_iterator_t
*iterator
, const void **eltp
)
240 gl_set_t set
= iterator
->set
;
241 if (iterator
->count
!= set
->count
)
243 if (iterator
->count
!= set
->count
+ 1)
244 /* Concurrent modifications were done on the set. */
246 /* The last returned element was removed. */
248 iterator
->p
= (const void **) iterator
->p
- 1;
249 iterator
->q
= (const void **) iterator
->q
- 1;
251 if (iterator
->p
< iterator
->q
)
253 const void **p
= (const void **) iterator
->p
;
263 gl_array_iterator_free (gl_set_iterator_t
*iterator
)
268 const struct gl_set_implementation gl_array_set_implementation
=
270 gl_array_nx_create_empty
,
277 gl_array_iterator_next
,
278 gl_array_iterator_free