1 /* 2 * linked list routines 3 * by Matthew Luckie 4 * 5 * Copyright (C) 2004-2019 Matthew Luckie. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY Matthew Luckie ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL Matthew Luckie BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 * 28 * $Id: mjl_list.h,v 1.41 2019/05/22 06:12:57 mjl Exp $ 29 * 30 */ 31 32 #ifndef __MJL_LIST_H 33 #define __MJL_LIST_H 34 35 typedef struct slist slist_t; 36 typedef struct dlist dlist_t; 37 typedef struct clist clist_t; 38 39 typedef struct slist_node slist_node_t; 40 typedef struct dlist_node dlist_node_t; 41 typedef struct clist_node clist_node_t; 42 43 typedef int (*slist_foreach_t)(void *item, void *param); 44 typedef int (*dlist_foreach_t)(void *item, void *param); 45 typedef int (*clist_foreach_t)(void *item, void *param); 46 47 typedef void (*slist_onremove_t)(void *item); 48 typedef void (*dlist_onremove_t)(void *item); 49 typedef void (*clist_onremove_t)(void *item); 50 51 typedef int (*slist_cmp_t)(const void *a, const void *b); 52 typedef int (*dlist_cmp_t)(const void *a, const void *b); 53 54 typedef void (*slist_free_t)(void *item); 55 typedef void (*dlist_free_t)(void *item); 56 typedef void (*clist_free_t)(void *item); 57 58 #ifndef DMALLOC 59 slist_t *slist_alloc(void); 60 slist_t *slist_dup(slist_t *list, const slist_foreach_t func, void *param); 61 slist_node_t *slist_head_push(slist_t *list, void *item); 62 slist_node_t *slist_tail_push(slist_t *list, void *item); 63 #endif 64 65 #ifdef DMALLOC 66 slist_t *slist_alloc_dm(const char *file, const int line); 67 slist_t *slist_dup_dm(slist_t *oldlist,const slist_foreach_t func,void *param, 68 const char *file, const int line); 69 slist_node_t *slist_head_push_dm(slist_t *list, void *item, 70 const char *file, const int line); 71 slist_node_t *slist_tail_push_dm(slist_t *list, void *item, 72 const char *file, const int line); 73 74 #define slist_alloc() slist_alloc_dm(__FILE__, __LINE__) 75 #define slist_dup(old,func,param) slist_dup_dm((old), (func), (param), \ 76 __FILE__, __LINE__) 77 #define slist_head_push(list, item) slist_head_push_dm((list), (item), \ 78 __FILE__, __LINE__) 79 #define slist_tail_push(list, item) slist_tail_push_dm((list), (item), \ 80 __FILE__, __LINE__) 81 #endif 82 83 void slist_init(slist_t *list); 84 void slist_onremove(slist_t *list, slist_onremove_t onremove); 85 void slist_concat(slist_t *first, slist_t *second); 86 void *slist_head_pop(slist_t *list); 87 void *slist_head_item(const slist_t *list); 88 void *slist_tail_item(const slist_t *list); 89 void *slist_node_item(const slist_node_t *node); 90 slist_node_t *slist_head_node(const slist_t *list); 91 slist_node_t *slist_tail_node(const slist_t *list); 92 slist_node_t *slist_node_next(const slist_node_t *node); 93 int slist_foreach(slist_t *list, const slist_foreach_t func, void *param); 94 int slist_count(const slist_t *list); 95 int slist_qsort(slist_t *list, slist_cmp_t func); 96 int slist_shuffle(slist_t *list); 97 void slist_lock(slist_t *list); 98 void slist_unlock(slist_t *list); 99 int slist_islocked(slist_t *list); 100 void slist_empty(slist_t *list); 101 void slist_empty_cb(slist_t *list, slist_free_t func); 102 void slist_free(slist_t *list); 103 void slist_free_cb(slist_t *list, slist_free_t func); 104 105 #ifndef DMALLOC 106 dlist_t *dlist_alloc(void); 107 dlist_t *dlist_dup(dlist_t *list, const dlist_foreach_t func, void *param); 108 dlist_node_t *dlist_node_alloc(void *item); 109 dlist_node_t *dlist_head_push(dlist_t *list, void *item); 110 dlist_node_t *dlist_tail_push(dlist_t *list, void *item); 111 #else 112 dlist_t *dlist_alloc_dm(const char *file, const int line); 113 dlist_t *dlist_dup_dm(dlist_t *oldlist,const dlist_foreach_t func,void *param, 114 const char *file, const int line); 115 dlist_node_t *dlist_node_alloc_dm(void *item,const char *file,const int line); 116 dlist_node_t *dlist_head_push_dm(dlist_t *list, void *item, 117 const char *file, const int line); 118 dlist_node_t *dlist_tail_push_dm(dlist_t *list, void *item, 119 const char *file, const int line); 120 #define dlist_alloc() dlist_alloc_dm(__FILE__, __LINE__) 121 #define dlist_node_alloc(item) dlist_node_alloc_dm((item), __FILE__, __LINE__) 122 #define dlist_head_push(list,item) dlist_head_push_dm((list), (item), \ 123 __FILE__, __LINE__) 124 #define dlist_tail_push(list,item) dlist_tail_push_dm((list), (item), \ 125 __FILE__, __LINE__) 126 #endif 127 128 void dlist_init(dlist_t *list); 129 void dlist_onremove(dlist_t *list, dlist_onremove_t onremove); 130 void dlist_concat(dlist_t *first, dlist_t *second); 131 void *dlist_head_pop(dlist_t *list); 132 void *dlist_tail_pop(dlist_t *list); 133 void *dlist_head_item(const dlist_t *list); 134 void *dlist_tail_item(const dlist_t *list); 135 void *dlist_node_pop(dlist_t *list, dlist_node_t *node); 136 void *dlist_node_item(const dlist_node_t *node); 137 dlist_node_t *dlist_head_node(const dlist_t *list); 138 dlist_node_t *dlist_tail_node(const dlist_t *list); 139 dlist_node_t *dlist_node_next(const dlist_node_t *node); 140 dlist_node_t *dlist_node_prev(const dlist_node_t *node); 141 void dlist_node_eject(dlist_t *list, dlist_node_t *node); 142 void dlist_node_head_push(dlist_t *list, dlist_node_t *node); 143 void dlist_node_tail_push(dlist_t *list, dlist_node_t *node); 144 int dlist_foreach(dlist_t *list, const dlist_foreach_t func, void *param); 145 int dlist_count(const dlist_t *list); 146 int dlist_qsort(dlist_t *list, dlist_cmp_t func); 147 int dlist_shuffle(dlist_t *list); 148 void dlist_lock(dlist_t *list); 149 void dlist_unlock(dlist_t *list); 150 int dlist_islocked(dlist_t *list); 151 void dlist_empty(dlist_t *list); 152 void dlist_empty_cb(dlist_t *list, dlist_free_t func); 153 void dlist_free(dlist_t *list); 154 void dlist_free_cb(dlist_t *list, dlist_free_t func); 155 156 #ifndef DMALLOC 157 clist_t *clist_alloc(void); 158 clist_node_t *clist_tail_push(clist_t *list, void *item); 159 #else 160 clist_t *clist_alloc_dm(const char *file, const int line); 161 clist_node_t *clist_tail_push_dm(clist_t *list, void *item, 162 const char *file, const int line); 163 #define clist_alloc() clist_alloc_dm(__FILE__, __LINE__) 164 #define clist_tail_push(list,item) clist_tail_push_dm((list), (item), \ 165 __FILE__, __LINE__) 166 #endif 167 168 void clist_init(clist_t *list); 169 void clist_onremove(clist_t *list, clist_onremove_t onremove); 170 clist_node_t *clist_head_node(const clist_t *list); 171 clist_node_t *clist_head_push(clist_t *list, void *item); 172 void *clist_head_pop(clist_t *list); 173 void *clist_tail_pop(clist_t *list); 174 void *clist_head_item(const clist_t *list); 175 void *clist_tail_item(const clist_t *list); 176 void *clist_node_pop(clist_t *list, clist_node_t *node); 177 void *clist_node_item(const clist_node_t *node); 178 clist_node_t *clist_node_next(const clist_node_t *node); 179 clist_node_t *clist_head_left(clist_t *node); 180 clist_node_t *clist_head_right(clist_t *node); 181 int clist_foreach(clist_t *list, const clist_foreach_t func, void *param); 182 int clist_count(const clist_t *list); 183 void clist_lock(clist_t *list); 184 void clist_unlock(clist_t *list); 185 int clist_islocked(clist_t *list); 186 void clist_free(clist_t *list); 187 void clist_free_cb(clist_t *list, clist_free_t func); 188 189 #endif 190