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 fc__attribute((nonnull (1)));
81
82void genlist_unique(struct genlist *pgenlist);
83void genlist_unique_full(struct genlist *pgenlist,
84 genlist_comp_fn_t comp_data_func)
85 fc__attribute((nonnull (1)));
86
87void genlist_append(struct genlist *pgenlist, void *data)
88 fc__attribute((nonnull (1)));
89void genlist_prepend(struct genlist *pgenlist, void *data)
90 fc__attribute((nonnull (1)));
91void genlist_insert(struct genlist *pgenlist, void *data, int idx)
92 fc__attribute((nonnull (1)));
93void genlist_insert_after(struct genlist *pgenlist, void *data,
94 struct genlist_link *plink)
95 fc__attribute((nonnull (1)));
96void genlist_insert_before(struct genlist *pgenlist, void *data,
97 struct genlist_link *plink)
98 fc__attribute((nonnull (1)));
99
100bool genlist_remove(struct genlist *pgenlist, const void *data)
101 fc__attribute((nonnull (1)));
102bool genlist_remove_if(struct genlist *pgenlist,
103 genlist_cond_fn_t cond_data_func)
104 fc__attribute((nonnull (1)));
105int genlist_remove_all(struct genlist *pgenlist, const void *data)
106 fc__attribute((nonnull (1)));
107int genlist_remove_all_if(struct genlist *pgenlist,
108 genlist_cond_fn_t cond_data_func)
109 fc__attribute((nonnull (1)));
110void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink)
111 fc__attribute((nonnull (1)));
112void genlist_pop_front(struct genlist *pgenlist)
113 fc__attribute((nonnull (1)));
114void genlist_pop_back(struct genlist *pgenlist)
115 fc__attribute((nonnull (1)));
116
117int genlist_size(const struct genlist *pgenlist)
118 fc__attribute((nonnull (1)));
119void *genlist_get(const struct genlist *pgenlist, int idx);
120void *genlist_front(const struct genlist *pgenlist);
121void *genlist_back(const struct genlist *pgenlist);
122struct genlist_link *genlist_link_get(const struct genlist *pgenlist, int idx)
123 fc__attribute((nonnull (1)));
124 inline static struct genlist_link *genlist_head(const struct genlist *pgenlist)
125{
126 return (pgenlist != nullptr ? pgenlist->head_link : nullptr);
127}
128struct genlist_link *genlist_tail(const struct genlist *pgenlist);
129
130struct genlist_link *genlist_search(const struct genlist *pgenlist,
131 const void *data)
132 fc__attribute((nonnull (1)));
133struct genlist_link *genlist_search_if(const struct genlist *pgenlist,
134 genlist_cond_fn_t cond_data_func)
135 fc__attribute((nonnull (1)));
136
137void genlist_sort(struct genlist *pgenlist,
138 int (*compar) (const void *, const void *));
139void genlist_shuffle(struct genlist *pgenlist);
140void genlist_reverse(struct genlist *pgenlist)
141 fc__attribute((nonnull (1)));
142
143void genlist_allocate_mutex(struct genlist *pgenlist);
144void genlist_release_mutex(struct genlist *pgenlist);
145
146
147/* A single element of a genlist, storing the pointer to user
148 * data, and pointers to the next and previous elements: */
149 struct genlist_link {
150 struct genlist_link *next, *prev;
151 void *dataptr;
152};
153
154/************************************************************************/
159 static inline void *genlist_link_data(const struct genlist_link *plink)
160{
161 return (plink != nullptr ? plink->dataptr : nullptr);
162}
163
164/************************************************************************/
169 fc__warn_unused_result
170 static inline struct genlist_link *genlist_link_prev(const struct genlist_link *plink)
171{
172 return plink->prev;
173}
174
175/************************************************************************/
180 fc__warn_unused_result
181 static inline struct genlist_link *genlist_link_next(const struct genlist_link *plink)
182{
183 return plink->next;
184}
185
186#ifdef __cplusplus
187}
188#endif /* __cplusplus */
189
190#endif /* FC__GENLIST_H */
incite_cost
char * incite_cost
Definition comments.c:74
fcthread.h
genlist_insert_before
void genlist_insert_before(struct genlist *pgenlist, void *data, struct genlist_link *plink) fc__attribute((nonnull(1)))
Definition genlist.c:490
genlist_allocate_mutex
void genlist_allocate_mutex(struct genlist *pgenlist)
Definition genlist.c:647
genlist_unique_full
void genlist_unique_full(struct genlist *pgenlist, genlist_comp_fn_t comp_data_func) fc__attribute((nonnull(1)))
Definition genlist.c:287
genlist_release_mutex
void genlist_release_mutex(struct genlist *pgenlist)
Definition genlist.c:655
genlist_insert
void genlist_insert(struct genlist *pgenlist, void *data, int idx) fc__attribute((nonnull(1)))
Definition genlist.c:456
genlist_get
void * genlist_get(const struct genlist *pgenlist, int idx)
Definition genlist.c:221
genlist_pop_front
void genlist_pop_front(struct genlist *pgenlist) fc__attribute((nonnull(1)))
Definition genlist.c:431
genlist_remove_all
int genlist_remove_all(struct genlist *pgenlist, const void *data) fc__attribute((nonnull(1)))
Definition genlist.c:342
genlist_erase
void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink) fc__attribute((nonnull(1)))
Definition genlist.c:421
genlist_cond_fn_t
bool(* genlist_cond_fn_t)(const void *)
Definition genlist.h:53
genlist_append
void genlist_append(struct genlist *pgenlist, void *data) fc__attribute((nonnull(1)))
Definition genlist.c:508
genlist_size
int genlist_size(const struct genlist *pgenlist) fc__attribute((nonnull(1)))
Definition genlist.c:192
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:124
genlist_link_data
static void * genlist_link_data(const struct genlist_link *plink)
Definition genlist.h:159
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_remove
bool genlist_remove(struct genlist *pgenlist, const void *data) fc__attribute((nonnull(1)))
Definition genlist.c:322
genlist_destroy
void genlist_destroy(struct genlist *pgenlist)
Definition genlist.c:57
genlist_reverse
void genlist_reverse(struct genlist *pgenlist) fc__attribute((nonnull(1)))
Definition genlist.c:625
genlist_back
void * genlist_back(const struct genlist *pgenlist)
Definition genlist.c:237
genlist_link_get
struct genlist_link * genlist_link_get(const struct genlist *pgenlist, int idx) fc__attribute((nonnull(1)))
Definition genlist.c:202
genlist_search
struct genlist_link * genlist_search(const struct genlist *pgenlist, const void *data) fc__attribute((nonnull(1)))
Definition genlist.c:518
genlist_unique
void genlist_unique(struct genlist *pgenlist)
Definition genlist.c:277
genlist_insert_after
void genlist_insert_after(struct genlist *pgenlist, void *data, struct genlist_link *plink) fc__attribute((nonnull(1)))
Definition genlist.c:480
genlist_pop_back
void genlist_pop_back(struct genlist *pgenlist) fc__attribute((nonnull(1)))
Definition genlist.c:441
genlist_remove_all_if
int genlist_remove_all_if(struct genlist *pgenlist, genlist_cond_fn_t cond_data_func) fc__attribute((nonnull(1)))
Definition genlist.c:391
genlist_search_if
struct genlist_link * genlist_search_if(const struct genlist *pgenlist, genlist_cond_fn_t cond_data_func) fc__attribute((nonnull(1)))
Definition genlist.c:536
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:563
genlist_new_full
struct genlist * genlist_new_full(genlist_free_fn_t free_data_func) fc__warn_unused_result
Definition genlist.c:39
genlist_tail
struct genlist_link * genlist_tail(const struct genlist *pgenlist)
Definition genlist.c:210
genlist_clear
void genlist_clear(struct genlist *pgenlist) fc__attribute((nonnull(1)))
Definition genlist.c:247
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:229
genlist_free_fn_t
void(* genlist_free_fn_t)(void *)
Definition genlist.h:51
genlist_link_prev
static fc__warn_unused_result struct genlist_link * genlist_link_prev(const struct genlist_link *plink)
Definition genlist.h:170
genlist_prepend
void genlist_prepend(struct genlist *pgenlist, void *data) fc__attribute((nonnull(1)))
Definition genlist.c:500
genlist_shuffle
void genlist_shuffle(struct genlist *pgenlist)
Definition genlist.c:595
genlist_link_next
static fc__warn_unused_result struct genlist_link * genlist_link_next(const struct genlist_link *plink)
Definition genlist.h:181
genlist_remove_if
bool genlist_remove_if(struct genlist *pgenlist, genlist_cond_fn_t cond_data_func) fc__attribute((nonnull(1)))
Definition genlist.c:368
genlist_link
Definition genlist.h:149
genlist_link::dataptr
void * dataptr
Definition genlist.h:151
genlist_link::prev
struct genlist_link * prev
Definition genlist.h:150
genlist_link::next
struct genlist_link * next
Definition genlist.h:150
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__attribute
#define fc__attribute(x)
Definition support.h:99
fc__warn_unused_result
#define fc__warn_unused_result
Definition support.h:109
bool
#define bool
Definition support.h:71