1 /* Map data type implemented by an array.
2 Copyright (C) 2006-2024 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_map.h"
26 /* Checked size_t computations. */
29 /* --------------------------- gl_map_t Data Type --------------------------- */
37 /* Concrete gl_map_impl type, valid for this file only. */
40 struct gl_map_impl_base base
;
41 /* An array of ALLOCATED pairs, of which the first COUNT are used.
42 0 <= COUNT <= ALLOCATED. */
49 gl_array_nx_create_empty (gl_map_implementation_t implementation
,
50 gl_mapkey_equals_fn equals_fn
,
51 gl_mapkey_hashcode_fn hashcode_fn
,
52 gl_mapkey_dispose_fn kdispose_fn
,
53 gl_mapvalue_dispose_fn vdispose_fn
)
55 struct gl_map_impl
*map
=
56 (struct gl_map_impl
*) malloc (sizeof (struct gl_map_impl
));
61 map
->base
.vtable
= implementation
;
62 map
->base
.equals_fn
= equals_fn
;
63 map
->base
.kdispose_fn
= kdispose_fn
;
64 map
->base
.vdispose_fn
= vdispose_fn
;
73 gl_array_size (gl_map_t map
)
79 gl_array_indexof (gl_map_t map
, const void *key
)
81 size_t count
= map
->count
;
85 gl_mapkey_equals_fn equals
= map
->base
.equals_fn
;
90 for (i
= 0; i
< count
; i
++)
91 if (equals (map
->pairs
[i
].key
, key
))
98 for (i
= 0; i
< count
; i
++)
99 if (map
->pairs
[i
].key
== key
)
107 gl_array_search (gl_map_t map
, const void *key
, const void **valuep
)
109 size_t index
= gl_array_indexof (map
, key
);
110 if (index
!= (size_t)(-1))
112 *valuep
= map
->pairs
[index
].value
;
119 /* Ensure that map->allocated > map->count.
120 Return 0 upon success, -1 upon out-of-memory. */
124 size_t new_allocated
;
128 new_allocated
= xtimes (map
->allocated
, 2);
129 new_allocated
= xsum (new_allocated
, 1);
130 memory_size
= xtimes (new_allocated
, sizeof (struct pair
));
131 if (size_overflow_p (memory_size
))
132 /* Overflow, would lead to out of memory. */
134 memory
= (struct pair
*) realloc (map
->pairs
, memory_size
);
139 map
->allocated
= new_allocated
;
144 gl_array_nx_getput (gl_map_t map
, const void *key
, const void *value
,
145 const void **oldvaluep
)
147 size_t index
= gl_array_indexof (map
, key
);
148 if (index
!= (size_t)(-1))
150 *oldvaluep
= map
->pairs
[index
].value
;
151 map
->pairs
[index
].value
= value
;
156 size_t count
= map
->count
;
159 if (count
== map
->allocated
)
163 pairs
[count
].key
= key
;
164 pairs
[count
].value
= value
;
165 map
->count
= count
+ 1;
170 /* Remove the pair at the given position,
171 0 <= position < gl_map_size (map). */
173 gl_array_remove_at (gl_map_t map
, size_t position
)
175 size_t count
= map
->count
;
180 if (map
->base
.kdispose_fn
!= NULL
)
181 map
->base
.kdispose_fn (pairs
[position
].key
);
182 for (i
= position
+ 1; i
< count
; i
++)
183 pairs
[i
- 1] = pairs
[i
];
184 map
->count
= count
- 1;
188 gl_array_getremove (gl_map_t map
, const void *key
, const void **oldvaluep
)
190 size_t index
= gl_array_indexof (map
, key
);
191 if (index
!= (size_t)(-1))
193 *oldvaluep
= map
->pairs
[index
].value
;
194 gl_array_remove_at (map
, index
);
202 gl_array_free (gl_map_t map
)
204 if (map
->pairs
!= NULL
)
206 if (map
->base
.kdispose_fn
!= NULL
|| map
->base
.vdispose_fn
!= NULL
)
208 size_t count
= map
->count
;
212 gl_mapkey_dispose_fn kdispose
= map
->base
.kdispose_fn
;
213 gl_mapvalue_dispose_fn vdispose
= map
->base
.vdispose_fn
;
214 struct pair
*pairs
= map
->pairs
;
219 vdispose (pairs
->value
);
221 kdispose (pairs
->key
);
232 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */
234 static gl_map_iterator_t
235 gl_array_iterator (gl_map_t map
)
237 gl_map_iterator_t result
;
239 result
.vtable
= map
->base
.vtable
;
241 result
.count
= map
->count
;
242 result
.p
= map
->pairs
+ 0;
243 result
.q
= map
->pairs
+ map
->count
;
244 #if defined GCC_LINT || defined lint
253 gl_array_iterator_next (gl_map_iterator_t
*iterator
,
254 const void **keyp
, const void **valuep
)
256 gl_map_t map
= iterator
->map
;
257 if (iterator
->count
!= map
->count
)
259 if (iterator
->count
!= map
->count
+ 1)
260 /* Concurrent modifications were done on the map. */
262 /* The last returned pair was removed. */
264 iterator
->p
= (struct pair
*) iterator
->p
- 1;
265 iterator
->q
= (struct pair
*) iterator
->q
- 1;
267 if (iterator
->p
< iterator
->q
)
269 struct pair
*p
= (struct pair
*) iterator
->p
;
280 gl_array_iterator_free (gl_map_iterator_t
*iterator
)
285 const struct gl_map_implementation gl_array_map_implementation
=
287 gl_array_nx_create_empty
,
294 gl_array_iterator_next
,
295 gl_array_iterator_free