1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
/*
* List Abstract Data Type
* Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
*
* Free Software License:
*
* All rights are reserved by the author, with the following exceptions:
* Permission is granted to freely reproduce and distribute this software,
* possibly in exchange for a fee, provided that this copyright notice appears
* intact. Permission is also granted to adapt this software to produce
* derivative works, as long as the modified versions carry this copyright
* notice and additional notices stating that the work has been modified.
* This source code may be translated into executable form and incorporated
* into proprietary software; there is no requirement for such software to
* contain a copyright notice related to this source.
*
* $Id: list.h,v 1.1.1.1 2008-10-21 09:10:13 cizzo Exp $
* $Name: not supported by cvs2svn $
*/
#ifndef LIST_H
#define LIST_H
#include <limits.h>
#ifdef KAZLIB_SIDEEFFECT_DEBUG
#include "sfx.h"
#define LIST_SFX_CHECK(E) SFX_CHECK(E)
#else
#define LIST_SFX_CHECK(E) (E)
#endif
/*
* Blurb for inclusion into C++ translation units
*/
#ifdef __cplusplus
extern "C" {
#endif
typedef unsigned long listcount_t;
#define LISTCOUNT_T_MAX ULONG_MAX
typedef struct lnode_t {
#if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
struct lnode_t *list_next;
struct lnode_t *list_prev;
void *list_data;
#else
int list_dummy;
#endif
} lnode_t;
typedef struct lnodepool_t {
#if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
struct lnode_t *list_pool;
struct lnode_t *list_free;
listcount_t list_size;
#else
int list_dummy;
#endif
} lnodepool_t;
typedef struct list_t {
#if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
lnode_t list_nilnode;
listcount_t list_nodecount;
listcount_t list_maxcount;
#else
int list_dummy;
#endif
} list_t;
lnode_t *lnode_create(void *);
lnode_t *lnode_init(lnode_t *, void *);
void lnode_destroy(lnode_t *);
void lnode_put(lnode_t *, void *);
void *lnode_get(lnode_t *);
int lnode_is_in_a_list(lnode_t *);
#if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
#define lnode_put(N, D) ((N)->list_data = (D))
#define lnode_get(N) ((N)->list_data)
#endif
lnodepool_t *lnode_pool_init(lnodepool_t *, lnode_t *, listcount_t);
lnodepool_t *lnode_pool_create(listcount_t);
void lnode_pool_destroy(lnodepool_t *);
lnode_t *lnode_borrow(lnodepool_t *, void *);
void lnode_return(lnodepool_t *, lnode_t *);
int lnode_pool_isempty(lnodepool_t *);
int lnode_pool_isfrom(lnodepool_t *, lnode_t *);
list_t *list_init(list_t *, listcount_t);
list_t *list_create(listcount_t);
void list_destroy(list_t *);
void list_destroy_nodes(list_t *);
void list_return_nodes(list_t *, lnodepool_t *);
listcount_t list_count(list_t *);
int list_isempty(list_t *);
int list_isfull(list_t *);
int list_contains(list_t *, lnode_t *);
void list_append(list_t *, lnode_t *);
void list_prepend(list_t *, lnode_t *);
void list_ins_before(list_t *, lnode_t *, lnode_t *);
void list_ins_after(list_t *, lnode_t *, lnode_t *);
lnode_t *list_first(list_t *);
lnode_t *list_last(list_t *);
lnode_t *list_next(list_t *, lnode_t *);
lnode_t *list_prev(list_t *, lnode_t *);
lnode_t *list_del_first(list_t *);
lnode_t *list_del_last(list_t *);
lnode_t *list_delete(list_t *, lnode_t *);
void list_process(list_t *, void *, void (*)(list_t *, lnode_t *, void *));
int list_verify(list_t *);
#if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
#define lnode_pool_isempty(P) ((P)->list_free == 0)
#define list_count(L) ((L)->list_nodecount)
#define list_isempty(L) ((L)->list_nodecount == 0)
#define list_isfull(L) (LIST_SFX_CHECK(L)->list_nodecount == (L)->list_maxcount)
#define list_next(L, N) (LIST_SFX_CHECK(N)->list_next == &(L)->list_nilnode ? NULL : (N)->list_next)
#define list_prev(L, N) (LIST_SFX_CHECK(N)->list_prev == &(L)->list_nilnode ? NULL : (N)->list_prev)
#define list_first(L) list_next(LIST_SFX_CHECK(L), &(L)->list_nilnode)
#define list_last(L) list_prev(LIST_SFX_CHECK(L), &(L)->list_nilnode)
#endif
#if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
#define list_append(L, N) list_ins_before(LIST_SFX_CHECK(L), N, &(L)->list_nilnode)
#define list_prepend(L, N) list_ins_after(LIST_SFX_CHECK(L), N, &(L)->list_nilnode)
#define list_del_first(L) list_delete(LIST_SFX_CHECK(L), list_first(L))
#define list_del_last(L) list_delete(LIST_SFX_CHECK(L), list_last(L))
#endif
/* destination list on the left, source on the right */
void list_extract(list_t *, list_t *, lnode_t *, lnode_t *);
void list_transfer(list_t *, list_t *, lnode_t *first);
void list_merge(list_t *, list_t *, int (const void *, const void *));
void list_sort(list_t *, int (const void *, const void *));
lnode_t *list_find(list_t *, const void *, int (const void *, const void *));
int list_is_sorted(list_t *, int (const void *, const void *));
#ifdef __cplusplus
}
#endif
#endif
|
