File: LL.h

package info (click to toggle)
lcdproc 0.5.9-3
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 5,064 kB
  • sloc: ansic: 59,645; sh: 1,740; perl: 681; makefile: 417
file content (210 lines) | stat: -rw-r--r-- 6,311 bytes parent folder | download | duplicates (4)
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
200
201
202
203
204
205
206
207
208
209
210
/** \file shared/LL.h
 * Define routines to deal with doubly linked lists
 */

/* This file is part of LCDproc.
 *
 * This file is released under the GNU General Public License.
 * Refer to the COPYING file distributed with this package.
 *
 * Copyright(c) 1994, Selene Scriven
 *          (c) 1999, William Ferrell
 *
 */

#ifndef LL_H
#define LL_H

/***********************************************************************
  Linked Lists!  (Doubly-Linked Lists)
  *******************************************************************

  To create a list, do the following:

    LinkedList *list;
    list = LL_new();
    if(!list) handle_an_error();

  The list can hold any type of data.  You will need to typecast your
  datatype to a "void *", though.  So, to add something to the list,
  the following would be a good way to start:

    typedef struct my_data {
      char string[16];
      int number;
    } my_data;

    my_data *thingie;

    for(something to something else)
    {
      thingie = malloc(sizeof(my_data));
      LL_AddNode(list, (void *)thingie);  // typecast it to a "void *"
    }

    For errors, the general convention is that "0" means success, and
    a negative number means failure.  Check LL.c to be sure, though.

  *******************************************************************

  To change the data, try this:

    thingie = (my_data *)LL_Get(list);  // typecast it back to "my_data"
    thingie->number = another_number;

  You don't need to "Put" the data back, but it doesn't hurt anything.

    LL_Put(list, (void *)thingie);

  However, if you want to point the node's data somewhere else, you'll
  need to get the current data first, keep track of it, then set the data
  to a new location:

    my_data * old_thingie, new_thingie;

    old_thingie = (my_data *)LL_Get(list);
    LL_Put(list, (void *)new_thingie);

    // Now, do something with old_thingie.  (maybe, free it?)

  Or, you could just delete the node entirely and then add a new one:

    my_data * thingie;

    thingie = (my_data *)LL_DeleteNode(list, NEXT);
    free(thingie);

    thingie->number = 666;

    LL_InsertNode(list, (void *)thingie);

  *******************************************************************

  To operate on each list item, try this:

    LL_Rewind(list);
    do {
      my_data = (my_data *)LL_Get(list);
      ... do something to it ...
    } while(LL_Next(list) == 0);

  *******************************************************************

  You can also treat the list like a stack, or a queue.  Just use the
  following functions:

    LL_Push()      // Regular stack stuff: add, remove, peek, rotate
    LL_Pop()
    LL_Top()

    LL_Shift()     // Other end of the stack (like in perl)
    LL_Unshift()
    LL_Look()

    LL_Enqueue()   // Standard queue operations
    LL_Dequeue()

  There are also other goodies, like sorting and searching.

  *******************************************************************
  That's about it, for now...  Be sure to free the list when you're done!
***********************************************************************/

// See LL.c for more detailed descriptions of these functions.


/** Symbolic values for directions */
typedef enum _direction {
	HEAD     = -2,
	PREV     = -1,
	CURRENT	 = 0,
	NEXT     = +1,
	TAIL     = +2
} Direction;


/** Structure for a node in a linked list */
typedef struct LL_node {
	struct LL_node *prev;	/**< Pointer to previous node */
	struct LL_node *next;	/**< Pointer to next node */
	void *data;		/**< Payload */
} LL_node;


/** Structire for a linked list */
typedef struct LinkedList {
	LL_node head;		/**< List's head anchor */
	LL_node tail;		/**< List's tail anchor */
	LL_node *current;	/**< Pointer to current node */
} LinkedList;


// Creates a new list...
LinkedList *LL_new(void);
// Destroying lists...
int LL_Destroy(LinkedList *list);

// move "current" node
LL_node *LL_GoTo(LinkedList *list, Direction whereto);

// Returns to the beginning of the list...
int LL_Rewind(LinkedList *list);
// Goes to the end of the list...
int LL_End(LinkedList *list);
// Go to the next node
int LL_Next(LinkedList *list);
// Go to the previous node
int LL_Prev(LinkedList *list);

// Data manipulation
void *LL_Get(LinkedList *list);
int LL_Put(LinkedList *list, void *data);
// Don't use these next two unless you really know what you're doing.
LL_node *LL_GetNode(LinkedList *list);
int LL_PutNode(LinkedList *list, LL_node *node);

void *LL_GetFirst(LinkedList *list);  // gets data from first node
void *LL_GetNext(LinkedList *list);	  //            ... next node
void *LL_GetPrev(LinkedList *list);	  //            ... prev node
void *LL_GetLast(LinkedList *list);	  //            ... last node

int LL_AddNode(LinkedList *list, void *add);	// Adds node AFTER current one
int LL_InsertNode(LinkedList *list, void *add);	// Adds node BEFORE current one
// Removes a node from the link; returns the data from the node
void *LL_DeleteNode(LinkedList *list, Direction whereto);
// Removes a specific node...
void *LL_Remove(LinkedList *list, void *data, Direction whereto);

// Stack operations
int LL_Push(LinkedList *list, void *add);	// Add node to end of list
void *LL_Pop(LinkedList *list);		  // Remove node from end of list
void *LL_Top(LinkedList *list);		  // Peek at end node
void *LL_Shift(LinkedList *list);	  // Remove node from start of list
void *LL_Look(LinkedList *list);		  // Peek at first node
int LL_Unshift(LinkedList *list, void *add);	// Add node to beginning of list

// Queue operations...
#define LL_Enqueue(list,add)	LL_Push(list,add)
#define LL_Dequeue(list)	LL_Shift(list)

int LL_PriorityEnqueue(LinkedList * list, void *add, int (*compare)(void *, void *));

int LL_SwapNodes(LL_node *one, LL_node *two);	// Switch two nodes positions...

int LL_Length(LinkedList *list);		  // Returns # of nodes in entire list

// Searching...
void *LL_Find(LinkedList *list, int (*compare)(void *, void *), void *value);

void LL_ForAll(LinkedList *list, void *(*action)(void *, void *), void *value);

// Array operation...
void *LL_GetByIndex(LinkedList *list, int index);  // gets the nth node, 0 being the first

// Sorts the list...
int LL_Sort(LinkedList *list, int (*compare)(void *, void *));

// Debugging...
void LL_dprint(LinkedList *list);

#endif