Freeciv-3.3
Loading...
Searching...
No Matches
genlist.c
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
6 any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12***********************************************************************/
13
14#ifdef HAVE_CONFIG_H
15#include <fc_config.h>
16#endif
17
18#include <stdlib.h>
19
20/* utility */
21#include "fcthread.h"
22#include "log.h"
23#include "mem.h"
24#include "shared.h" /* array_shuffle() */
25
26#include "genlist.h"
27
28/************************************************************************/
31struct genlist *genlist_new(void)
32{
33 return genlist_new_full(nullptr);
34}
35
36/************************************************************************/
40{
41 struct genlist *pgenlist = fc_calloc(1, sizeof(*pgenlist));
42
43#ifdef ZERO_VARIABLES_FOR_SEARCHING
44 pgenlist->nelements = 0;
45 pgenlist->head_link = nullptr;
46 pgenlist->tail_link = nullptr;
47#endif /* ZERO_VARIABLES_FOR_SEARCHING */
48 fc_mutex_init(&pgenlist->mutex);
49 pgenlist->free_data_func = free_data_func;
50
51 return pgenlist;
52}
53
54/************************************************************************/
58{
59 if (pgenlist == nullptr) {
60 return;
61 }
62
66}
67
68/************************************************************************/
71static void genlist_link_new(struct genlist *pgenlist, void *dataptr,
72 struct genlist_link *prev,
73 struct genlist_link *next)
74{
75 struct genlist_link *plink = fc_malloc(sizeof(*plink));
76
77 plink->dataptr = dataptr;
78 plink->prev = prev;
79 if (prev != nullptr) {
80 prev->next = plink;
81 } else {
82 pgenlist->head_link = plink;
83 }
84 plink->next = next;
85 if (next != nullptr) {
86 next->prev = plink;
87 } else {
88 pgenlist->tail_link = plink;
89 }
90 pgenlist->nelements++;
91}
92
93/************************************************************************/
97 struct genlist_link *plink)
98{
99 if (pgenlist->head_link == plink) {
100 pgenlist->head_link = plink->next;
101 } else {
102 plink->prev->next = plink->next;
103 }
104
105 if (pgenlist->tail_link == plink) {
106 pgenlist->tail_link = plink->prev;
107 } else {
108 plink->next->prev = plink->prev;
109 }
110
111 pgenlist->nelements--;
112
113 /* NB: Detach the link before calling the free function for avoiding
114 * re-entrant code. */
115 if (pgenlist->free_data_func != nullptr) {
116 pgenlist->free_data_func(plink->dataptr);
117 }
118 free(plink);
119}
120
121/************************************************************************/
127static struct genlist_link *
129{
130 struct genlist_link *plink;
131
132 if (pos == 0) {
133 return pgenlist->head_link;
134 } else if (pos == -1) {
135 return pgenlist->tail_link;
136 } else if (pos < -1 || pos >= pgenlist->nelements) {
137 return nullptr;
138 }
139
140 if (pos < pgenlist->nelements / 2) { /* Fastest to do forward search */
141 for (plink = pgenlist->head_link; pos != 0; pos--) {
142 plink = plink->next;
143 }
144 } else { /* Fastest to do backward search */
145 for (plink = pgenlist->tail_link, pos = pgenlist->nelements-pos - 1;
146 pos != 0; pos--) {
147 plink = plink->prev;
148 }
149 }
150
151 return plink;
152}
153
154/************************************************************************/
157struct genlist *genlist_copy(const struct genlist *pgenlist)
158{
159 return genlist_copy_full(pgenlist, nullptr, pgenlist->free_data_func);
160}
161
162/************************************************************************/
168{
170
171 if (pgenlist) {
172 struct genlist_link *plink;
173
174 if (copy_data_func != nullptr) {
175 for (plink = pgenlist->head_link; plink; plink = plink->next) {
177 pcopy->tail_link, nullptr);
178 }
179 } else {
180 for (plink = pgenlist->head_link; plink; plink = plink->next) {
181 genlist_link_new(pcopy, plink->dataptr, pcopy->tail_link, nullptr);
182 }
183 }
184 }
185
186 return pcopy;
187}
188
189/************************************************************************/
192int genlist_size(const struct genlist *pgenlist)
193{
194 return pgenlist->nelements;
195}
196
197/************************************************************************/
202struct genlist_link *genlist_link_get(const struct genlist *pgenlist, int idx)
203{
204 return genlist_link_at_pos(pgenlist, idx);
205}
206
207/************************************************************************/
211{
212 return (pgenlist != nullptr ? pgenlist->tail_link : nullptr);
213}
214
215/************************************************************************/
221void *genlist_get(const struct genlist *pgenlist, int idx)
222{
224}
225
226/************************************************************************/
229void *genlist_front(const struct genlist *pgenlist)
230{
232}
233
234/************************************************************************/
237void *genlist_back(const struct genlist *pgenlist)
238{
240}
241
242/************************************************************************/
248{
249 if (0 < pgenlist->nelements) {
250 genlist_free_fn_t free_data_func = pgenlist->free_data_func;
251 struct genlist_link *plink = pgenlist->head_link, *plink2;
252
253 pgenlist->head_link = nullptr;
254 pgenlist->tail_link = nullptr;
255
256 pgenlist->nelements = 0;
257
258 if (free_data_func != nullptr) {
259 do {
260 plink2 = plink->next;
261 free_data_func(plink->dataptr);
262 free(plink);
263 } while ((plink = plink2) != nullptr);
264 } else {
265 do {
266 plink2 = plink->next;
267 free(plink);
268 } while ((plink = plink2) != nullptr);
269 }
270 }
271}
272
273/************************************************************************/
278{
280}
281
282/************************************************************************/
289{
290 if (2 <= pgenlist->nelements) {
291 struct genlist_link *plink = pgenlist->head_link, *plink2;
292
293 if (comp_data_func != nullptr) {
294 do {
295 plink2 = plink->next;
296 if (plink2 != nullptr && comp_data_func(plink->dataptr,
297 plink2->dataptr)) {
298 /* Remove this element. */
300 }
301 } while ((plink = plink2) != nullptr);
302 } else {
303 do {
304 plink2 = plink->next;
305 if (plink2 != nullptr && plink->dataptr == plink2->dataptr) {
306 /* Remove this element. */
308 }
309 } while ((plink = plink2) != nullptr);
310 }
311 }
312}
313
314/************************************************************************/
322bool genlist_remove(struct genlist *pgenlist, const void *punlink)
323{
324 struct genlist_link *plink;
325
326 for (plink = pgenlist->head_link; plink != nullptr; plink = plink->next) {
327 if (plink->dataptr == punlink) {
329 return TRUE;
330 }
331 }
332
333 return FALSE;
334}
335
336/************************************************************************/
343{
344 struct genlist_link *plink;
345 int count = 0;
346
347 for (plink = pgenlist->head_link; plink != nullptr;) {
348 if (plink->dataptr == punlink) {
349 struct genlist_link *pnext = plink->next;
350
352 count++;
353 plink = pnext;
354 } else {
355 plink = plink->next;
356 }
357 }
358
359 return count;
360}
361
362/************************************************************************/
370{
371 if (cond_data_func != nullptr) {
372 struct genlist_link *plink = pgenlist->head_link;
373
374 for (; plink != nullptr; plink = plink->next) {
375 if (cond_data_func(plink->dataptr)) {
377 return TRUE;
378 }
379 }
380 }
381
382 return FALSE;
383}
384
385/************************************************************************/
393{
394 if (cond_data_func != nullptr) {
395 struct genlist_link *plink = pgenlist->head_link;
396 int count = 0;
397
398 while (plink != nullptr) {
399 if (cond_data_func(plink->dataptr)) {
400 struct genlist_link *pnext = plink->next;
401
403 count++;
404 plink = pnext;
405 } else {
406 plink = plink->next;
407 }
408 }
409 return count;
410 }
411
412 return 0;
413}
414
415/************************************************************************/
421void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink)
422{
423 if (plink != nullptr) {
425 }
426}
427
428/************************************************************************/
432{
433 if (pgenlist->head_link != nullptr) {
435 }
436}
437
438/************************************************************************/
442{
443 if (pgenlist->tail_link != nullptr) {
445 }
446}
447
448/************************************************************************/
456void genlist_insert(struct genlist *pgenlist, void *data, int pos)
457{
458 if (0 == pgenlist->nelements) {
459 /* List is empty, ignore pos. */
460 genlist_link_new(pgenlist, data, nullptr, nullptr);
461 } else if (0 == pos) {
462 /* Prepend. */
463 genlist_link_new(pgenlist, data, nullptr, pgenlist->head_link);
464 } else if (-1 >= pos || pos >= pgenlist->nelements) {
465 /* Append. */
466 genlist_link_new(pgenlist, data, pgenlist->tail_link, nullptr);
467 } else {
468 /* Insert before plink. */
470
471 fc_assert_ret(plink != nullptr);
472
473 genlist_link_new(pgenlist, data, plink->prev, plink);
474 }
475}
476
477/************************************************************************/
480void genlist_insert_after(struct genlist *pgenlist, void *data,
481 struct genlist_link *plink)
482{
483 genlist_link_new(pgenlist, data, plink,
484 plink != nullptr ? plink->next : pgenlist->head_link);
485}
486
487/************************************************************************/
490void genlist_insert_before(struct genlist *pgenlist, void *data,
491 struct genlist_link *plink)
492{
494 plink != nullptr ? plink->prev : pgenlist->tail_link, plink);
495}
496
497/************************************************************************/
500void genlist_prepend(struct genlist *pgenlist, void *data)
501{
502 genlist_link_new(pgenlist, data, nullptr, pgenlist->head_link);
503}
504
505/************************************************************************/
508void genlist_append(struct genlist *pgenlist, void *data)
509{
510 genlist_link_new(pgenlist, data, pgenlist->tail_link, nullptr);
511}
512
513/************************************************************************/
519 const void *data)
520{
521 struct genlist_link *plink;
522
523 for (plink = pgenlist->head_link; plink; plink = plink->next) {
524 if (plink->dataptr == data) {
525 return plink;
526 }
527 }
528
529 return nullptr;
530}
531
532/************************************************************************/
538{
539 if (cond_data_func != nullptr) {
540 struct genlist_link *plink = pgenlist->head_link;
541
542 for (; plink != nullptr; plink = plink->next) {
543 if (cond_data_func(plink->dataptr)) {
544 return plink;
545 }
546 }
547 }
548
549 return nullptr;
550}
551
552/************************************************************************/
564 int (*compar) (const void *, const void *))
565{
566 const size_t n = genlist_size(pgenlist);
567 void **sortbuf;
568 struct genlist_link *myiter;
569 unsigned int i;
570
571 if (n <= 1) {
572 return;
573 }
574
575 sortbuf = fc_malloc(n * sizeof(void *));
577 for (i = 0; i < n; i++, myiter = myiter->next) {
578 sortbuf[i] = myiter->dataptr;
579 }
580
581 qsort(sortbuf, n, sizeof(*sortbuf), compar);
582
584 for (i = 0; i < n; i++, myiter = myiter->next) {
585 myiter->dataptr = sortbuf[i];
586 }
588}
589
590/************************************************************************/
596{
597 const int n = genlist_size(pgenlist);
598
599 if (n > 1) {
600 void *sortbuf[n];
601 struct genlist_link *myiter;
602 int i, shuffle[n];
603
605 for (i = 0; i < n; i++, myiter = myiter->next) {
606 sortbuf[i] = myiter->dataptr;
607 /* Also create the shuffle list */
608 shuffle[i] = i;
609 }
610
611 /* Randomize it */
613
614 /* Create the shuffled list */
616 for (i = 0; i < n; i++, myiter = myiter->next) {
617 myiter->dataptr = sortbuf[shuffle[i]];
618 }
619 }
620}
621
622/************************************************************************/
626{
627 struct genlist_link *head, *tail;
628 int counter;
629
630 head = pgenlist->head_link;
631 tail = pgenlist->tail_link;
632 for (counter = pgenlist->nelements / 2; 0 < counter; counter--) {
633 /* Swap. */
634 void *temp = head->dataptr;
635
636 head->dataptr = tail->dataptr;
637 tail->dataptr = temp;
638
639 head = head->next;
640 tail = tail->prev;
641 }
642}
643
644/************************************************************************/
651
652/************************************************************************/
656{
657 fc_mutex_release(&pgenlist->mutex);
658}
#define n
Definition astring.c:77
char * incite_cost
Definition comments.c:76
void fc_mutex_allocate(fc_mutex *mutex)
void fc_mutex_init(fc_mutex *mutex)
void fc_mutex_release(fc_mutex *mutex)
void fc_mutex_destroy(fc_mutex *mutex)
bool genlist_remove(struct genlist *pgenlist, const void *punlink)
Definition genlist.c:322
void genlist_allocate_mutex(struct genlist *pgenlist)
Definition genlist.c:647
void genlist_insert(struct genlist *pgenlist, void *data, int pos)
Definition genlist.c:456
struct genlist * genlist_copy_full(const struct genlist *pgenlist, genlist_copy_fn_t copy_data_func, genlist_free_fn_t free_data_func)
Definition genlist.c:165
void genlist_release_mutex(struct genlist *pgenlist)
Definition genlist.c:655
struct genlist * genlist_new(void)
Definition genlist.c:31
void * genlist_get(const struct genlist *pgenlist, int idx)
Definition genlist.c:221
int genlist_remove_all(struct genlist *pgenlist, const void *punlink)
Definition genlist.c:342
void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink)
Definition genlist.c:421
struct genlist_link * genlist_search_if(const struct genlist *pgenlist, genlist_cond_fn_t cond_data_func)
Definition genlist.c:536
void genlist_clear(struct genlist *pgenlist)
Definition genlist.c:247
void genlist_prepend(struct genlist *pgenlist, void *data)
Definition genlist.c:500
bool genlist_remove_if(struct genlist *pgenlist, genlist_cond_fn_t cond_data_func)
Definition genlist.c:368
void genlist_append(struct genlist *pgenlist, void *data)
Definition genlist.c:508
void genlist_unique_full(struct genlist *pgenlist, genlist_comp_fn_t comp_data_func)
Definition genlist.c:287
static struct genlist_link * genlist_link_at_pos(const struct genlist *pgenlist, int pos)
Definition genlist.c:128
static void genlist_link_new(struct genlist *pgenlist, void *dataptr, struct genlist_link *prev, struct genlist_link *next)
Definition genlist.c:71
struct genlist * genlist_copy(const struct genlist *pgenlist)
Definition genlist.c:157
void genlist_destroy(struct genlist *pgenlist)
Definition genlist.c:57
void genlist_pop_front(struct genlist *pgenlist)
Definition genlist.c:431
void genlist_insert_before(struct genlist *pgenlist, void *data, struct genlist_link *plink)
Definition genlist.c:490
void * genlist_back(const struct genlist *pgenlist)
Definition genlist.c:237
int genlist_remove_all_if(struct genlist *pgenlist, genlist_cond_fn_t cond_data_func)
Definition genlist.c:391
void genlist_unique(struct genlist *pgenlist)
Definition genlist.c:277
void genlist_insert_after(struct genlist *pgenlist, void *data, struct genlist_link *plink)
Definition genlist.c:480
void genlist_sort(struct genlist *pgenlist, int(*compar)(const void *, const void *))
Definition genlist.c:563
void genlist_reverse(struct genlist *pgenlist)
Definition genlist.c:625
struct genlist_link * genlist_tail(const struct genlist *pgenlist)
Definition genlist.c:210
void * genlist_front(const struct genlist *pgenlist)
Definition genlist.c:229
struct genlist * genlist_new_full(genlist_free_fn_t free_data_func)
Definition genlist.c:39
struct genlist_link * genlist_link_get(const struct genlist *pgenlist, int idx)
Definition genlist.c:202
void genlist_pop_back(struct genlist *pgenlist)
Definition genlist.c:441
struct genlist_link * genlist_search(const struct genlist *pgenlist, const void *data)
Definition genlist.c:518
int genlist_size(const struct genlist *pgenlist)
Definition genlist.c:192
void genlist_shuffle(struct genlist *pgenlist)
Definition genlist.c:595
static void genlist_link_destroy(struct genlist *pgenlist, struct genlist_link *plink)
Definition genlist.c:96
bool(* genlist_cond_fn_t)(const void *)
Definition genlist.h:53
bool(* genlist_comp_fn_t)(const void *, const void *)
Definition genlist.h:54
static struct genlist_link * genlist_head(const struct genlist *pgenlist)
Definition genlist.h:124
static void * genlist_link_data(const struct genlist_link *plink)
Definition genlist.h:159
void *(* genlist_copy_fn_t)(const void *)
Definition genlist.h:52
void(* genlist_free_fn_t)(void *)
Definition genlist.h:51
static struct tile * pos
Definition finddlg.c:53
#define fc_assert_ret(condition)
Definition log.h:192
#define fc_calloc(n, esz)
Definition mem.h:38
#define FC_FREE(ptr)
Definition mem.h:41
#define fc_malloc(sz)
Definition mem.h:34
void array_shuffle(int *array, int n)
Definition shared.c:2011
genlist_free_fn_t free_data_func
Definition genlist.h:64
#define TRUE
Definition support.h:46
#define FALSE
Definition support.h:47