xosview  1.23
About: xosview is an X Windows based system monitor (cpu, memory, swap and network usage; interrupt and serial activities; load average).
  Fossies Dox: xosview-1.23.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

llist.cc
Go to the documentation of this file.
1 //
2 // Copyright (c) 1994, 1995, 2006 by Mike Romberg ( mike.romberg@noaa.gov )
3 //
4 // This file may be distributed under terms of the GPL
5 //
6 
7 #include "llist.h"
8 #include <stdio.h>
9 
10 LList::LNode::LNode( void *data ){
11  data_ = data;
12  next_ = NULL;
13  prev_ = NULL;
14 }
15 
16 LList::LList( void ){
17  n_ = 0;
18  top_ = NULL;
19  btm_ = NULL;
20  for ( int i = 0 ; i < MAXCURR ; i++ )
21  curr_[i] = NULL;
22  cmp_fun_ = NULL;
23 }
24 
25 LList::LList( int ( *cmp_fun )( void *data, void *key ) ){
26  n_ = 0;
27  top_ = NULL;
28  btm_ = NULL;
29  for ( int i = 0 ; i < MAXCURR ; i++ )
30  curr_[i] = NULL;
31  cmp_fun_ = cmp_fun;
32 }
33 
34 LList::~LList( void ){
35  while ( n_ )
36  pop();
37 }
38 
39 int LList::push( void *data ){
40  if ( !n_ ) {
41  top_ = new LNode( data );
42  if ( top_ == NULL ) return ( 0 );
43  n_ = 1;
44  btm_ = top_;
45  return ( 1 );
46  }
47 
48  btm_->next_ = new LNode( data );
49  if ( btm_->next_ == NULL ) return ( 0 );
50  n_++;
51  btm_->next_->prev_ = btm_;
52  btm_ = btm_->next_;
53  return ( 1 );
54 }
55 
56 void *LList::pop( void ){
57  void *temp;
58  LNode *temp2;
59 
60  if ( !n_ ) return ( NULL );
61 
62  temp = btm_->data_;
63  if ( n_ == 1 ) {
64  delete top_;
65  top_ = NULL;
66  btm_ = NULL;
67  n_ = 0;
68  return ( temp );
69  }
70 
71  n_--;
72  temp2 = btm_->prev_;
73  btm_->prev_->next_ = NULL;
74  delete btm_;
75  btm_ = temp2;
76  return ( temp );
77 }
78 
79 void *LList::dequeue( void ){
80  void *temp;
81  LNode *temp2;
82 
83  if ( !n_ ) return ( NULL );
84 
85  if ( n_ == 1 ) {
86  temp = top_->data_;
87  n_ = 0;
88  delete top_;
89  top_ = NULL;
90  btm_ = NULL;
91  return ( temp );
92  }
93 
94  n_--;
95  temp2 = top_->next_;
96  temp = top_->data_;
97  top_->next_->prev_ = NULL;
98  delete top_;
99  top_ = temp2;
100  return ( temp );
101 }
102 
103 int LList::insert( void *data, void *key ){
104  LNode *current, *temp;
105 
106  current = top_;
107 
108  /* Empty List */
109  if ( !n_ ) {
110  if ( ( top_ = new LNode( data ) ) == NULL ) return ( 0 );
111  btm_ = top_;
112  n_++;
113  return ( 1 );
114  }
115 
116  while ( ( cmp_fun_( current->data_, key ) < 0 ) &&
117  ( current->next_ != NULL ) )
118  current = current->next_;
119 
120  if ( ( temp = new LNode( data ) ) == NULL ) return ( 0 );
121 
122  n_++;
123 
124  /* Add To End of List */
125  if ( ( current->next_ == NULL ) &&
126  ( cmp_fun_( current->data_, key ) < 0 ) ) {
127  temp->prev_ = btm_;
128  current->next_ = temp;
129  btm_ = temp;
130  return ( 1 );
131  }
132 
133  /* Add To Top of List */
134  if ( ( current->prev_ == NULL ) &&
135  ( cmp_fun_( current->data_, key ) > 0 ) ) {
136  temp->next_ = current;
137  current->prev_ = temp;
138  top_ = temp;
139  return ( 1 );
140  }
141 
142  /* Middle Of List */
143  temp->next_ = current;
144  temp->prev_ = current->prev_;
145  current->prev_->next_ = temp;
146  current->prev_ = temp;
147  return ( 1 );
148 }
149 
150 void *LList::find( void *key ){
151  LNode *temp;
152 
153  temp = findnode( key );
154  if ( temp == NULL ) return ( NULL );
155  return ( temp->data_ );
156 }
157 
158 void *LList::removematch( void *key ){
159  LNode *ptr;
160 
161  ptr = findnode( key );
162 
163  if ( ptr == NULL ) return ( NULL );
164 
165  return ( deletenode( ptr ) );
166 }
167 
168 int LList::putontop( void *data ){
169  LNode *buff;
170 
171  if ( ( buff = new LNode( data ) ) == NULL ) return ( 0 );
172 
173  top_->prev_ = buff;
174  buff->next_ = top_;
175  top_ = buff;
176  n_++;
177  return ( 1 );
178 }
179 
180 void LList::remove( void *data ){
181  LNode *tmp;
182  int found = 0;
183 
184  tmp = top_;
185  while ( (!found) && (tmp != NULL) ) {
186  if ( tmp->data_ == data ) found = 1;
187  if ( !found ) tmp = tmp->next_;
188  }
189 
190  if ( (tmp == NULL) || (!found) ) return;
191 
192  deletenode( tmp );
193 }
194 
195 void *LList::findn( int n ){
196  LNode *temp;
197 
198  temp = findnnode( n );
199  if ( temp == NULL ) return ( NULL );
200  return ( temp->data_ );
201 }
202 
203 int LList::index( void *data ){
204  int a = 1;
205  LNode *tmp;
206 
207  tmp = top_;
208  while ( tmp != NULL ) {
209  if ( tmp->data_ == data ) return ( a );
210  a++;
211  tmp = tmp->next_;
212  }
213  return ( 0 );
214 }
215 
216 void LList::setc( int n, int which ){
217  curr_[which] = findnnode( n );
218 }
219 
220 void LList::incc( int which ){
221  if ( curr_[which] != NULL ) curr_[which] = curr_[which]->next_;
222 }
223 
224 void LList::decc( int which ){
225  if ( curr_[which] != NULL ) curr_[which] = curr_[which]->prev_;
226 }
227 
228 void *LList::findc( int which ){
229  if ( curr_[which] == NULL ) return ( NULL );
230 
231  return ( curr_[which]->data_ );
232 }
233 
234 void LList::save( int size, FILE *fp ){
235  int i;
236  void *buf;
237 
238  fwrite( &n_, sizeof( int ), 1, fp ); /* save n */
239 
240  setc( 1 );
241  for ( i = 1 ; i <= n_ ; i ++ ) {
242  buf = findc();
243  fwrite ( buf, size, 1, fp );
244  incc();
245  }
246 }
247 
248 int LList::restore( int size, FILE *fp ){
249  int i;
250  void *buf;
251 
252  fread ( &i, sizeof ( int ), 1, fp );
253 
254  for ( ; i > 0 ; i-- ) {
255  if ( ( buf = new char[size] ) == NULL ) return ( 0 );
256  if ( ! push( buf ) ) return ( 0 );
257  }
258 
259  return ( 1 );
260 }
261 
262 void LList::kill( void ){
263 // while ( n_ ) {
264 // delete pop();
265 // }
266 }
267 
268 
269 
270 
271 
273  LNode *current;
274 
275  current = top_;
276 
277  if ( current == NULL ) return ( NULL );
278 
279  while ( ( cmp_fun_( current->data_, key ) ) &&
280  ( current != NULL ) )
281  current = current->next_;
282 
283  if ( current == NULL ) return ( NULL );
284 
285  return ( current );
286 }
287 
288 void *LList::deletenode( LNode *ptr ){
289  void *rtn;
290 
291  if ( ( top_ == NULL ) || ( ptr == NULL ) ) return ( NULL );
292 
293  if ( n_ == 1 ) {
294  rtn = top_->data_;
295  n_ = 0;
296  delete top_;
297  top_ = btm_ = NULL;
298  return ( rtn );
299  }
300 
301  n_--;
302 
303  if ( ptr->prev_ == NULL ) {
304  rtn = ptr->data_;
305  top_ = top_->next_;
306  top_->prev_ = NULL;
307  delete ptr;
308  return ( rtn );
309  }
310 
311  if ( ptr->next_ == NULL ) {
312  rtn = ptr->data_;
313  btm_ = btm_->prev_;
314  btm_->next_ = NULL;
315  delete ptr;
316  return ( rtn );
317  }
318 
319  ptr->prev_->next_ = ptr->next_;
320  ptr->next_->prev_ = ptr->prev_;
321  rtn = ptr->data_;
322  delete ptr;
323  return ( rtn );
324 }
325 
327  int j;
328  LNode *current;
329 
330  if ( (i > n_) || (i < 1) ) return ( NULL );
331 
332  if ( i <= n_ / 2 ) {
333  current = top_;
334  for ( j = 1 ; j < i ; j++ ) current = current->next_;
335  return ( current );
336  }
337 
338  current = btm_;
339  for ( j = n_ ; j > i ; j-- ) current = current->prev_;
340  return ( current );
341 }
void * data_
Definition: llist.h:109
LNode(void *data=NULL)
Definition: llist.cc:10
LNode * next_
Definition: llist.h:110
LNode * prev_
Definition: llist.h:111
virtual ~LList(void)
Definition: llist.cc:34
void * dequeue(void)
Definition: llist.cc:79
LNode * curr_[4]
Definition: llist.h:116
void kill(void)
Definition: llist.cc:262
LNode * findnnode(int i)
Definition: llist.cc:326
void setc(int n, int which=0)
Definition: llist.cc:216
void * findc(int which=0)
Definition: llist.cc:228
void remove(void *data)
Definition: llist.cc:180
void * deletenode(LNode *ptr)
Definition: llist.cc:288
int push(void *data)
Definition: llist.cc:39
LList(void)
Definition: llist.cc:16
LNode * top_
Definition: llist.h:115
void * find(void *key)
Definition: llist.cc:150
void incc(int which=0)
Definition: llist.cc:220
LNode * btm_
Definition: llist.h:115
void * pop(void)
Definition: llist.cc:56
int restore(int size, FILE *fp)
Definition: llist.cc:248
int n(void) const
Definition: llist.h:102
int n_
Definition: llist.h:114
int putontop(void *data)
Definition: llist.cc:168
int insert(void *data, void *key)
Definition: llist.cc:103
void * findn(int n)
Definition: llist.cc:195
LNode * findnode(void *key)
Definition: llist.cc:272
int index(void *data)
Definition: llist.cc:203
void decc(int which=0)
Definition: llist.cc:224
void save(int size, FILE *fp)
Definition: llist.cc:234
int(* cmp_fun_)(void *data, void *key)
Definition: llist.h:119
void * removematch(void *key)
Definition: llist.cc:158
#define MAXCURR
Definition: llist.h:12