utility/genlist.h

   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
  17 extern "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. */
  48 struct 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
  67 struct genlist *genlist_new(void) fc__warn_unused_result;
  68 struct genlist *genlist_new_full(genlist_free_fn_t free_data_func)
  69                 fc__warn_unused_result;
  70 void genlist_destroy(struct genlist *pgenlist);
  71
  72 struct genlist *genlist_copy(const struct genlist *pgenlist)
  73                 fc__warn_unused_result;
  74 struct 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
  79 void genlist_clear(struct genlist *pgenlist);
  80
  81 void genlist_unique(struct genlist *pgenlist);
  82 void genlist_unique_full(struct genlist *pgenlist,
  83                          genlist_comp_fn_t comp_data_func);
  84
  85 void genlist_append(struct genlist *pgenlist, void *data);
  86 void genlist_prepend(struct genlist *pgenlist, void *data);
  87 void genlist_insert(struct genlist *pgenlist, void *data, int idx);
  88 void genlist_insert_after(struct genlist *pgenlist, void *data,
  89                           struct genlist_link *plink);
  90 void genlist_insert_before(struct genlist *pgenlist, void *data,
  91                            struct genlist_link *plink);
  92
  93 bool genlist_remove(struct genlist *pgenlist, const void *data);
  94 bool genlist_remove_if(struct genlist *pgenlist,
  95                        genlist_cond_fn_t cond_data_func);
  96 int genlist_remove_all(struct genlist *pgenlist, const void *data);
  97 int genlist_remove_all_if(struct genlist *pgenlist,
  98                           genlist_cond_fn_t cond_data_func);
  99 void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink);
 100 void genlist_pop_front(struct genlist *pgenlist);
 101 void genlist_pop_back(struct genlist *pgenlist);
 102
 103 int genlist_size(const struct genlist *pgenlist);
 104 void *genlist_get(const struct genlist *pgenlist, int idx);
 105 void *genlist_front(const struct genlist *pgenlist);
 106 void *genlist_back(const struct genlist *pgenlist);
 107 struct 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 (NULL != pgenlist ? pgenlist->head_link : NULL);
 111 }
 112 struct genlist_link *genlist_tail(const struct genlist *pgenlist);
 113
 114 struct genlist_link *genlist_search(const struct genlist *pgenlist,
 115                                     const void *data);
 116 struct genlist_link *genlist_search_if(const struct genlist *pgenlist,
 117                                        genlist_cond_fn_t cond_data_func);
 118
 119 void genlist_sort(struct genlist *pgenlist,
 120                   int (*compar) (const void *, const void *));
 121 void genlist_shuffle(struct genlist *pgenlist);
 122 void genlist_reverse(struct genlist *pgenlist);
 123
 124 void genlist_allocate_mutex(struct genlist *pgenlist);
 125 void 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 /****************************************************************************
 136   Returns the pointer of this link.
 137 ****************************************************************************/
 138 static inline void *genlist_link_data(const struct genlist_link *plink)
 139 {
 140   return (NULL != plink ? plink->dataptr : NULL);
 141 }
 142
 143 /****************************************************************************
 144   Returns the previous link.
 145 ****************************************************************************/
 146 fc__warn_unused_result
 147 static inline struct genlist_link *genlist_link_prev(const struct genlist_link *plink)
 148 {
 149   return plink->prev;
 150 }
 151
 152 /****************************************************************************
 153   Returns the next link.
 154 ****************************************************************************/
 155 fc__warn_unused_result
 156 static inline struct genlist_link *genlist_link_next(const struct genlist_link *plink)
 157 {
 158   return plink->next;
 159 }
 160
 161 #ifdef __cplusplus
 162 }
 163 #endif /* __cplusplus */
 164
 165 #endif  /* FC__GENLIST_H */