1 /*
2 list.c
3
4 Dug Song <dugsong@anzen.com>
5
6 Copyright (c) 1999 Anzen Computing. All rights reserved.
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions
10 are met:
11
12 1. Redistributions of source code must retain the above copyright
13 notice, this list of conditions and the following disclaimer.
14 2. Redistributions in binary form must reproduce the above copyright
15 notice, this list of conditions and the following disclaimer in the
16 documentation and/or other materials provided with the distribution.
17 3. All advertising materials mentioning features or use of this software
18 must display the following acknowledgement:
19 This product includes software developed by Anzen Computing.
20 4. Neither the name of Anzen Computing nor the names of its
21 contributors may be used to endorse or promote products derived
22 from this software without specific prior written permission.
23
24 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
25 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
26 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
27 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
28 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
30 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
31 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
32 IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
33 OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
34 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35
36 $Id: list.c,v 1.5 1999/06/21 20:06:58 dugsong Exp $
37 */
38
39 #include "config.h"
40
41 #ifdef STDC_HEADERS
42 #include <stdlib.h>
43 #endif
44
45 #include "list.h"
46
47 ELEM *
list_elem(unsigned char * data,int len)48 list_elem(unsigned char *data, int len)
49 {
50 ELEM *new;
51
52 if ((new = malloc(sizeof(ELEM))) == NULL ||
53 (new->data = malloc(len)) == NULL) {
54 if (new) free(new);
55 return NULL;
56 }
57 memcpy(new->data, data, len);
58 new->len = len;
59 new->head = NULL;
60 new->prev = NULL;
61 new->next = NULL;
62
63 return new;
64 }
65
66 ELEM *
list_add(ELEM * elem,ELEM * new)67 list_add(ELEM *elem, ELEM *new)
68 {
69 if (!elem) {
70 new->head = new;
71 new->prev = NULL;
72 new->next = NULL;
73 }
74 else {
75 new->head = elem->head;
76 new->next = elem->next;
77 new->prev = elem;
78 elem->next = new;
79 if (new->next) new->next->prev = new;
80 }
81 return (new);
82 }
83
84 int
list_free(ELEM * elem)85 list_free(ELEM *elem)
86 {
87 ELEM *next, *f = elem;
88
89 if (f->prev) f->prev->next = NULL;
90
91 for ( ; f != NULL ; f = next) {
92 next = f->next;
93 free(f->data);
94 free(f);
95 }
96 return 1;
97 }
98
99 ELEM *
list_last(ELEM * elem)100 list_last(ELEM *elem)
101 {
102 ELEM *f;
103
104 if (!elem) return NULL;
105 for (f = elem ; f->next != NULL ; f = f->next) ;
106 return (f);
107 }
108
109 ELEM *
list_dup(ELEM * elem)110 list_dup(ELEM *elem)
111 {
112 ELEM *dup = NULL;
113
114 if (elem && (dup = list_elem(elem->data, elem->len)) != NULL)
115 list_add(elem, dup);
116
117 return (dup);
118 }
119
120 ELEM *
list_swap(ELEM * elem)121 list_swap(ELEM *elem)
122 {
123 ELEM *f, *next = elem->next;
124
125 if (next) {
126 elem->next = next->next;
127 next->prev = elem->prev;
128 elem->prev = next;
129 next->next = elem;
130
131 if (elem->next) elem->next->prev = elem;
132
133 if (next->prev) next->prev->next = next;
134 else {
135 for (f = next ; f != NULL ; f = f->next)
136 f->head = next;
137 }
138 }
139 else if (elem->prev == elem->head) { /* last elem of two. */
140 return list_swap(elem->head);
141 }
142 else { /* last elem of a few, swap with head. */
143 next = elem->head;
144 next->prev = elem->prev;
145 elem->prev = NULL;
146 elem->next = next->next;
147 next->next = NULL;
148 if (elem->next)
149 elem->next->prev = elem;
150 if (next->prev)
151 next->prev->next = next;
152
153 for (f = elem ; f != NULL ; f = f->next)
154 f->head = elem;
155 }
156 return (elem);
157 }
158
159 ELEM *
list_randomize(ELEM * elem)160 list_randomize(ELEM *elem)
161 {
162 int i;
163 ELEM *f;
164
165 /* XXX - lame. */
166 for (i = 0, f = elem->head ; f && f->next != NULL ; f = f->next, i++)
167 if (i % 2) f = list_swap(f);
168
169 return (elem->head);
170 }
171