1 /* ms.c - resizable multiset implementation */
3 /* Copyright (C) 2008 Keith Rarick and Philotic Inc.
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 <http://www.gnu.org/licenses/>.
25 ms_init(ms a
, ms_event_fn oninsert
, ms_event_fn onremove
)
27 a
->used
= a
->cap
= a
->last
= 0;
29 a
->oninsert
= oninsert
;
30 a
->onremove
= onremove
;
37 size_t ncap
= (a
->cap
<< 1) ? : 1;
39 nitems
= malloc(ncap
* sizeof(void *));
42 memcpy(nitems
, a
->items
, a
->used
* sizeof(void *));
49 ms_append(ms a
, void *item
)
51 if (a
->used
>= a
->cap
) grow(a
);
52 if (a
->used
>= a
->cap
) return 0;
54 a
->items
[a
->used
++] = item
;
55 if (a
->oninsert
) a
->oninsert(a
, item
, a
->used
- 1);
60 ms_delete(ms a
, size_t i
)
64 if (i
>= a
->used
) return 0;
66 a
->items
[i
] = a
->items
[--a
->used
];
68 /* it has already been removed now */
69 if (a
->onremove
) a
->onremove(a
, item
, i
);
76 while (ms_delete(a
, 0));
78 ms_init(a
, a
->oninsert
, a
->onremove
);
82 ms_remove(ms a
, void *item
)
86 for (i
= 0; i
< a
->used
; i
++) {
87 if (a
->items
[i
] == item
) return ms_delete(a
, i
);
93 ms_contains(ms a
, void *item
)
97 for (i
= 0; i
< a
->used
; i
++) {
98 if (a
->items
[i
] == item
) return 1;
108 if (!a
->used
) return NULL
;
110 a
->last
= a
->last
% a
->used
;
111 item
= a
->items
[a
->last
];
112 ms_delete(a
, a
->last
);