Freeciv-3.3: /fast/freeciv/nightly/main/utility/genlist.h Source File

Freeciv-3.3

Loading...
Searching...
No Matches
genlist.h
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#ifndef FC__GENLIST_H
14#define FC__GENLIST_H
15
16#ifdef __cplusplus
17extern "C" {
18#endif /* __cplusplus */
19
20/****************************************************************************
21 MODULE: genlist
22
23 A "genlist" is a generic doubly-linked list. That is:
24 generic: stores (void*) pointers to arbitrary user data;
25 doubly-linked: can be efficiently traversed both "forwards"
26 and "backwards".
27
28 The list data structures are allocated dynamically, and list elements can
29 be added or removed at arbitrary positions.
30
31 Positions in the list are specified starting from 0, up to n - 1 for a
32 list with n elements. The position -1 can be used to refer to the last
33 element (that is, the same as n - 1, or n when adding a new element), but
34 other negative numbers are not meaningful.
35
36 A trap to beware of with iterators is modifying the list while the
37 iterator is active, in particular removing the next element pointed
38 to by the iterator (see further comments below).
39
40 See also the speclist module.
41****************************************************************************/
42
43/* utility */
44#include "fcthread.h"
45#include "support.h" /* bool, fc__warn_unused_result */
46
47/* A single element of a genlist, opaque type. */
48struct genlist_link;
49
50/* Function type definitions. */
51 typedef void (*genlist_free_fn_t) (void *);
52 typedef void * (*genlist_copy_fn_t) (const void *);
53 typedef bool (*genlist_cond_fn_t) (const void *);
54 typedef bool (*genlist_comp_fn_t) (const void *, const void *);
55
56/* A genlist, storing the number of elements (for quick retrieval and
57 * testing for empty lists), and pointers to the first and last elements
58 * of the list. */
59 struct genlist {
60 int nelements;
61 fc_mutex mutex;
62 struct genlist_link *head_link;
63 struct genlist_link *tail_link;
64 genlist_free_fn_t free_data_func;
65};
66
67struct genlist *genlist_new(void) fc__warn_unused_result;
68struct genlist *genlist_new_full(genlist_free_fn_t free_data_func)
69 fc__warn_unused_result;
70void genlist_destroy(struct genlist *pgenlist);
71
72struct genlist *genlist_copy(const struct genlist *pgenlist)
73 fc__warn_unused_result;
74struct genlist *genlist_copy_full(const struct genlist *pgenlist,
75 genlist_copy_fn_t copy_data_func,
76 genlist_free_fn_t free_data_func)
77 fc__warn_unused_result;
78
79void genlist_clear(struct genlist *pgenlist);
80
81void genlist_unique(struct genlist *pgenlist);
82void genlist_unique_full(struct genlist *pgenlist,
83 genlist_comp_fn_t comp_data_func);
84
85void genlist_append(struct genlist *pgenlist, void *data);
86void genlist_prepend(struct genlist *pgenlist, void *data);
87void genlist_insert(struct genlist *pgenlist, void *data, int idx);
88void genlist_insert_after(struct genlist *pgenlist, void *data,
89 struct genlist_link *plink);
90void genlist_insert_before(struct genlist *pgenlist, void *data,
91 struct genlist_link *plink);
92
93bool genlist_remove(struct genlist *pgenlist, const void *data);
94bool genlist_remove_if(struct genlist *pgenlist,
95 genlist_cond_fn_t cond_data_func);
96int genlist_remove_all(struct genlist *pgenlist, const void *data);
97int genlist_remove_all_if(struct genlist *pgenlist,
98 genlist_cond_fn_t cond_data_func);
99void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink);
100void genlist_pop_front(struct genlist *pgenlist);
101void genlist_pop_back(struct genlist *pgenlist);
102
103int genlist_size(const struct genlist *pgenlist);
104void *genlist_get(const struct genlist *pgenlist, int idx);
105void *genlist_front(const struct genlist *pgenlist);
106void *genlist_back(const struct genlist *pgenlist);
107struct genlist_link *genlist_link_get(const struct genlist *pgenlist, int idx);
108 inline static struct genlist_link *genlist_head(const struct genlist *pgenlist)
109{
110 return (pgenlist != nullptr ? pgenlist->head_link : nullptr);
111}
112struct genlist_link *genlist_tail(const struct genlist *pgenlist);
113
114struct genlist_link *genlist_search(const struct genlist *pgenlist,
115 const void *data);
116struct genlist_link *genlist_search_if(const struct genlist *pgenlist,
117 genlist_cond_fn_t cond_data_func);
118
119void genlist_sort(struct genlist *pgenlist,
120 int (*compar) (const void *, const void *));
121void genlist_shuffle(struct genlist *pgenlist);
122void genlist_reverse(struct genlist *pgenlist);
123
124void genlist_allocate_mutex(struct genlist *pgenlist);
125void genlist_release_mutex(struct genlist *pgenlist);
126
127
128/* A single element of a genlist, storing the pointer to user
129 * data, and pointers to the next and previous elements: */
130 struct genlist_link {
131 struct genlist_link *next, *prev;
132 void *dataptr;
133};
134
135/************************************************************************/
140 static inline void *genlist_link_data(const struct genlist_link *plink)
141{
142 return (plink != nullptr ? plink->dataptr : nullptr);
143}
144
145/************************************************************************/
150 fc__warn_unused_result
151 static inline struct genlist_link *genlist_link_prev(const struct genlist_link *plink)
152{
153 return plink->prev;
154}
155
156/************************************************************************/
161 fc__warn_unused_result
162 static inline struct genlist_link *genlist_link_next(const struct genlist_link *plink)
163{
164 return plink->next;
165}
166
167#ifdef __cplusplus
168}
169#endif /* __cplusplus */
170
171#endif /* FC__GENLIST_H */
incite_cost
char * incite_cost
Definition comments.c:74
fcthread.h
genlist_insert
void genlist_insert(struct genlist *pgenlist, void *data, int idx)
Definition genlist.c:478
genlist_allocate_mutex
void genlist_allocate_mutex(struct genlist *pgenlist)
Definition genlist.c:685
genlist_release_mutex
void genlist_release_mutex(struct genlist *pgenlist)
Definition genlist.c:693
genlist_get
void * genlist_get(const struct genlist *pgenlist, int idx)
Definition genlist.c:225
genlist_cond_fn_t
bool(* genlist_cond_fn_t)(const void *)
Definition genlist.h:53
genlist_erase
void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink)
Definition genlist.c:437
genlist_search_if
struct genlist_link * genlist_search_if(const struct genlist *pgenlist, genlist_cond_fn_t cond_data_func)
Definition genlist.c:570
genlist_clear
void genlist_clear(struct genlist *pgenlist)
Definition genlist.c:251
genlist_prepend
void genlist_prepend(struct genlist *pgenlist, void *data)
Definition genlist.c:528
genlist_remove_if
bool genlist_remove_if(struct genlist *pgenlist, genlist_cond_fn_t cond_data_func)
Definition genlist.c:380
genlist_append
void genlist_append(struct genlist *pgenlist, void *data)
Definition genlist.c:538
genlist_copy
struct genlist * genlist_copy(const struct genlist *pgenlist) fc__warn_unused_result
Definition genlist.c:157
genlist_comp_fn_t
bool(* genlist_comp_fn_t)(const void *, const void *)
Definition genlist.h:54
genlist_head
static struct genlist_link * genlist_head(const struct genlist *pgenlist)
Definition genlist.h:108
genlist_link_data
static void * genlist_link_data(const struct genlist_link *plink)
Definition genlist.h:140
genlist_unique_full
void genlist_unique_full(struct genlist *pgenlist, genlist_comp_fn_t comp_data_func)
Definition genlist.c:293
genlist_copy_full
struct genlist * genlist_copy_full(const struct genlist *pgenlist, genlist_copy_fn_t copy_data_func, genlist_free_fn_t free_data_func) fc__warn_unused_result
Definition genlist.c:165
genlist_destroy
void genlist_destroy(struct genlist *pgenlist)
Definition genlist.c:57
genlist_remove_all
int genlist_remove_all(struct genlist *pgenlist, const void *data)
Definition genlist.c:352
genlist_pop_front
void genlist_pop_front(struct genlist *pgenlist)
Definition genlist.c:449
genlist_insert_before
void genlist_insert_before(struct genlist *pgenlist, void *data, struct genlist_link *plink)
Definition genlist.c:516
genlist_back
void * genlist_back(const struct genlist *pgenlist)
Definition genlist.c:241
genlist_remove_all_if
int genlist_remove_all_if(struct genlist *pgenlist, genlist_cond_fn_t cond_data_func)
Definition genlist.c:405
genlist_unique
void genlist_unique(struct genlist *pgenlist)
Definition genlist.c:283
genlist_insert_after
void genlist_insert_after(struct genlist *pgenlist, void *data, struct genlist_link *plink)
Definition genlist.c:504
genlist_copy_fn_t
void *(* genlist_copy_fn_t)(const void *)
Definition genlist.h:52
genlist_sort
void genlist_sort(struct genlist *pgenlist, int(*compar)(const void *, const void *))
Definition genlist.c:599
genlist_new_full
struct genlist * genlist_new_full(genlist_free_fn_t free_data_func) fc__warn_unused_result
Definition genlist.c:39
genlist_reverse
void genlist_reverse(struct genlist *pgenlist)
Definition genlist.c:661
genlist_tail
struct genlist_link * genlist_tail(const struct genlist *pgenlist)
Definition genlist.c:214
genlist_new
struct genlist * genlist_new(void) fc__warn_unused_result
Definition genlist.c:31
genlist_front
void * genlist_front(const struct genlist *pgenlist)
Definition genlist.c:233
genlist_link_get
struct genlist_link * genlist_link_get(const struct genlist *pgenlist, int idx)
Definition genlist.c:204
genlist_pop_back
void genlist_pop_back(struct genlist *pgenlist)
Definition genlist.c:461
genlist_free_fn_t
void(* genlist_free_fn_t)(void *)
Definition genlist.h:51
genlist_search
struct genlist_link * genlist_search(const struct genlist *pgenlist, const void *data)
Definition genlist.c:550
genlist_link_prev
static fc__warn_unused_result struct genlist_link * genlist_link_prev(const struct genlist_link *plink)
Definition genlist.h:151
genlist_size
int genlist_size(const struct genlist *pgenlist)
Definition genlist.c:192
genlist_shuffle
void genlist_shuffle(struct genlist *pgenlist)
Definition genlist.c:631
genlist_remove
bool genlist_remove(struct genlist *pgenlist, const void *data)
Definition genlist.c:330
genlist_link_next
static fc__warn_unused_result struct genlist_link * genlist_link_next(const struct genlist_link *plink)
Definition genlist.h:162
genlist_link
Definition genlist.h:130
genlist_link::dataptr
void * dataptr
Definition genlist.h:132
genlist_link::prev
struct genlist_link * prev
Definition genlist.h:131
genlist_link::next
struct genlist_link * next
Definition genlist.h:131
genlist
Definition genlist.h:59
genlist::tail_link
struct genlist_link * tail_link
Definition genlist.h:63
genlist::head_link
struct genlist_link * head_link
Definition genlist.h:62
genlist::nelements
int nelements
Definition genlist.h:60
genlist::mutex
fc_mutex mutex
Definition genlist.h:61
genlist::free_data_func
genlist_free_fn_t free_data_func
Definition genlist.h:64
support.h
fc__warn_unused_result
#define fc__warn_unused_result
Definition support.h:109
bool
#define bool
Definition support.h:71