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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
/*
* The MIT License
*
* Copyright (C) 2010-2016 Alexander Saprykin <saprykin.spb@gmail.com>
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* 'Software'), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
/**
* @file plist.h
* @brief Singly linked list
* @author Alexander Saprykin
*
* A singly linked list is a data structure consists of the nodes which
* represent a sequence. Each node contains a data pointer and a pointer to the
* next node. Every node has a link only to the next node, hence list is a
* singly linked (in a single direction).
*
* As the singly linked list is a linear collection of the nodes with the
* sequential access, it has an O(N) average complexity for appending, removing
* and searching operations. Prepending a node takes O(1) constant time. Thus it
* is not intended for heavy usage, please refer to #PHashTable or #PTree if you
* are working with large data sets.
*
* Before the first usage you must initialize a #PList variable to NULL. After
* that you can use the p_list_append(), p_list_prepend(), p_list_remove() and
* p_list_reverse() routines to update that variable:
* @code
* PList *list;
* ppointer data;
*
* list = NULL;
* data = my_obj_new ();
*
* list = p_list_append (list, data);
* @endcode
* #PList stores only the pointers to the data, so you must free used memory
* manually, p_list_free() only frees list's internal memory, not the data it
* stores the pointers for. The best approach to free used memory is the
* p_list_foreach() routine:
* @code
* PList *list;
* ...
* p_list_foreach (list, (PFunc) my_free_func, my_data);
* p_list_free (list);
* @endcode
* Also you can use #P_INT_TO_POINTER and #P_POINTER_TO_INT macros to store
* integers (up to 32-bit) without allocating memory for them:
* @code
* PList *list;
* pint a;
*
* list = p_list_append (list, P_INT_TO_POINTER (12));
* a = P_POINTER_TO_INT (list->data);
* @endcode
* #PList can store several nodes with the same pointer value, but
* p_list_remove() will remove only the first matching node.
*
* If you need to add large amount of nodes at once it is better to prepend them
* and then reverse the list.
*/
#if !defined (PLIBSYS_H_INSIDE) && !defined (PLIBSYS_COMPILATION)
# error "Header files shouldn't be included directly, consider using <plibsys.h> instead."
#endif
#ifndef PLIBSYS_HEADER_PLIST_H
#define PLIBSYS_HEADER_PLIST_H
#include <pmacros.h>
#include <ptypes.h>
P_BEGIN_DECLS
/** Typedef for a list node. */
typedef struct PList_ PList;
/** Node for a singly linked list. */
struct PList_ {
ppointer data; /**< Pointer to the node data. */
PList *next; /**< Next list node. */
};
/**
* @brief Appends data to a list.
* @param list #PList for appending the data.
* @param data Data to append.
* @return Pointer to the updated list in case of success, @a list otherwise.
* @since 0.0.1
*
* Before appending the first node to the list, @a list argument must be
* initialized with NULL. Otherwise behavior is unpredictable.
*/
P_LIB_API PList * p_list_append (PList *list,
ppointer data) P_GNUC_WARN_UNUSED_RESULT;
/**
* @brief Removes data from a list.
* @param list List to remove the data from.
* @param data Data to remove.
* @return Pointer to the updated list in case of success, @a list otherwise.
* @since 0.0.1
*
* It searches for the first matching occurrence in the @a list and removes
* that node. Note that it removes only the pointer from the @a list, not the
* data it pointers to, so you need to free the data manually.
*/
P_LIB_API PList * p_list_remove (PList *list,
ppointer data) P_GNUC_WARN_UNUSED_RESULT;
/**
* @brief Calls a specified function for each list node.
* @param list List to go through.
* @param func Pointer for the callback function.
* @param user_data User defined data, may be NULL.
* @since 0.0.1
*
* This function goes through the whole @a list and calls @a func for each node.
* The @a func will receive pointer to the node's data and @a user_data. You can
* use it to free the data:
* @code
* p_list_foreach (list, (PFunc) free, NULL);
* p_list_free (list);
* @endcode
*/
P_LIB_API void p_list_foreach (PList *list,
PFunc func,
ppointer user_data);
/**
* @brief Frees list memory.
* @param list List to free.
* @since 0.0.1
*
* This function frees only the list's internal memory, not the data in the
* pointers stored in the nodes. Don't forget to free all the data stored in the
* list manually.
*/
P_LIB_API void p_list_free (PList *list);
/**
* @brief Gets the last node from the list.
* @param list List to get the node from.
* @return Pointer to the last @a list node, NULL if the @a list is empty.
* @since 0.0.1
*/
P_LIB_API PList * p_list_last (PList *list);
/**
* @brief Gets the number of list nodes.
* @param list List to count nodes in.
* @return Number of nodes in the @a list.
* @since 0.0.1
* @note This function will iterate through the whole @a list, so don't use it
* in condition of the for-loop or in the code which is repeated a lot of times.
*/
P_LIB_API psize p_list_length (const PList *list);
/**
* @brief Prepends data to a list.
* @param list #PList for prepending the data.
* @param data Data to prepend.
* @return Pointer to the updated list in case of success, @a list otherwise.
* @since 0.0.1
*
* Before prepending the first node to the list, @a list argument must be
* initialized with NULL. Otherwise behavior is unpredictable.
*/
P_LIB_API PList * p_list_prepend (PList *list,
ppointer data) P_GNUC_WARN_UNUSED_RESULT;
/**
* @brief Reverses the list order.
* @param list #PList to reverse the order.
* @return Pointer to the top of the reversed list.
* @since 0.0.1
*/
P_LIB_API PList * p_list_reverse (PList *list) P_GNUC_WARN_UNUSED_RESULT;
P_END_DECLS
#endif /* PLIBSYS_HEADER_PLIST_H */
|
