00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef llist_H
00022 #define llist_H
00023
00024 #include <limits.h>
00025
00026 #ifdef KAZLIB_SIDEEFFECT_DEBUG
00027 #include "sfx.h"
00028 #define llist_SFX_CHECK(E) SFX_CHECK(E)
00029 #else
00030 #define llist_SFX_CHECK(E) (E)
00031 #endif
00032
00033
00034
00035
00036
00037 #ifdef __cplusplus
00038 extern "C" {
00039 #endif
00040
00041 typedef unsigned long listcount_t;
00042 #define LISTCOUNT_T_MAX ULONG_MAX
00043
00044 typedef struct llnode_t {
00045 #if defined(llist_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
00046 struct llnode_t *llist_next;
00047 struct llnode_t *llist_prev;
00048 void *llist_data;
00049 #else
00050 int llist_dummy;
00051 #endif
00052 } llnode_t;
00053
00054 typedef struct lnodepool_t {
00055 #if defined(llist_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
00056 struct llnode_t *llist_pool;
00057 struct llnode_t *llist_free;
00058 listcount_t llist_size;
00059 #else
00060 int llist_dummy;
00061 #endif
00062 } lnodepool_t;
00063
00064 typedef struct llist_t {
00065 #if defined(llist_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
00066 llnode_t llist_nilnode;
00067 listcount_t llist_nodecount;
00068 listcount_t llist_maxcount;
00069 #else
00070 int llist_dummy;
00071 #endif
00072 } llist_t;
00073
00074 llnode_t *llnode_create(void *);
00075 llnode_t *llnode_init(llnode_t *, void *);
00076 void llnode_destroy(llnode_t *);
00077 void llnode_put(llnode_t *, void *);
00078 void *llnode_get(llnode_t *);
00079 int llnode_is_in_a_list(llnode_t *);
00080
00081 #if defined(llist_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
00082 #define llnode_put(N, D) ((N)->llist_data = (D))
00083 #define llnode_get(N) ((N)->llist_data)
00084 #endif
00085
00086 lnodepool_t *llnode_pool_init(lnodepool_t *, llnode_t *, listcount_t);
00087 lnodepool_t *llnode_pool_create(listcount_t);
00088 void llnode_pool_destroy(lnodepool_t *);
00089 llnode_t *llnode_borrow(lnodepool_t *, void *);
00090 void llnode_return(lnodepool_t *, llnode_t *);
00091 int llnode_pool_isempty(lnodepool_t *);
00092 int llnode_pool_isfrom(lnodepool_t *, llnode_t *);
00093
00094 llist_t *llist_init(llist_t *, listcount_t);
00095 llist_t *llist_create(listcount_t);
00096 void llist_destroy(llist_t *);
00097 void llist_destroy_nodes(llist_t *);
00098 void llist_return_nodes(llist_t *, lnodepool_t *);
00099
00100 listcount_t llist_count(llist_t *);
00101 int llist_isempty(llist_t *);
00102 int llist_isfull(llist_t *);
00103 int llist_contains(llist_t *, llnode_t *);
00104
00105 void llist_append(llist_t *, llnode_t *);
00106 void llist_prepend(llist_t *, llnode_t *);
00107 void llist_ins_before(llist_t *, llnode_t *, llnode_t *);
00108 void llist_ins_after(llist_t *, llnode_t *, llnode_t *);
00109
00110 llnode_t *llist_first(llist_t *);
00111 llnode_t *llist_last(llist_t *);
00112 llnode_t *llist_next(llist_t *, llnode_t *);
00113 llnode_t *llist_prev(llist_t *, llnode_t *);
00114
00115 llnode_t *llist_del_first(llist_t *);
00116 llnode_t *llist_del_last(llist_t *);
00117 llnode_t *llist_delete(llist_t *, llnode_t *);
00118
00119 void llist_process(llist_t *, void *, void (*)(llist_t *, llnode_t *, void *));
00120
00121 int llist_verify(llist_t *);
00122
00123 #if defined(llist_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
00124 #define llnode_pool_isempty(P) ((P)->llist_free == 0)
00125 #define llist_count(L) ((L)->llist_nodecount)
00126 #define llist_isempty(L) ((L)->llist_nodecount == 0)
00127 #define llist_isfull(L) (llist_SFX_CHECK(L)->llist_nodecount == (L)->llist_maxcount)
00128 #define llist_next(L, N) (llist_SFX_CHECK(N)->llist_next == &(L)->llist_nilnode ? NULL : (N)->llist_next)
00129 #define llist_prev(L, N) (llist_SFX_CHECK(N)->llist_prev == &(L)->llist_nilnode ? NULL : (N)->llist_prev)
00130 #define llist_first(L) llist_next(llist_SFX_CHECK(L), &(L)->llist_nilnode)
00131 #define llist_last(L) llist_prev(llist_SFX_CHECK(L), &(L)->llist_nilnode)
00132 #endif
00133
00134 #if defined(llist_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
00135 #define llist_append(L, N) llist_ins_before(llist_SFX_CHECK(L), N, &(L)->llist_nilnode)
00136 #define llist_prepend(L, N) llist_ins_after(llist_SFX_CHECK(L), N, &(L)->llist_nilnode)
00137 #define llist_del_first(L) llist_delete(llist_SFX_CHECK(L), llist_first(L))
00138 #define llist_del_last(L) llist_delete(llist_SFX_CHECK(L), llist_last(L))
00139 #endif
00140
00141
00142
00143 void llist_extract(llist_t *, llist_t *, llnode_t *, llnode_t *);
00144 void llist_transfer(llist_t *, llist_t *, llnode_t *first);
00145 void llist_merge(llist_t *, llist_t *, int (const void *, const void *));
00146 void llist_sort(llist_t *, int (const void *, const void *));
00147 llnode_t *llist_find(llist_t *, const void *, int (const void *, const void *));
00148 int llist_is_sorted(llist_t *, int (const void *, const void *));
00149
00150 #ifdef __cplusplus
00151 }
00152 #endif
00153
00154 #endif