"Fossies" - the Fresh Open Source Software Archive

Member "xosview-1.23/llist.cc" (11 Jul 2020, 6014 Bytes) of package /linux/misc/xosview-1.23.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "llist.cc" see the Fossies "Dox" file reference documentation.

    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 
  272 LList::LNode *LList::findnode( void *key ){
  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 
  326 LList::LNode *LList::findnnode( int i ){
  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 }