Main Page   Modules   Class Hierarchy   Compound List   File List   Compound Members   File Members  

linklist.cpp

00001 /*  Fast atomical linklist class
00002  *  (c) Copyright 2001 Denis Roio aka jaromil <jaromil@dyne.org>
00003  *
00004  * This source code is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU Public License as published 
00006  * by the Free Software Foundation; either version 2 of the License,
00007  * or (at your option) any later version.
00008  *
00009  * This source code is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00012  * Please refer to the GNU Public License for more details.
00013  *
00014  * You should have received a copy of the GNU Public License along with
00015  * this source code; if not, write to:
00016  * Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00017  *
00018  * "$Id: linklist.cpp,v 1.3 2004/02/13 16:58:16 jaromil Exp $"
00019  *
00020  -------------------------------------------------------------------------
00021    linked list container class
00022    
00023    NOTE: add and rem don't take care of deleting pointers
00024    that has to be done by the process that creates them and
00025    knows which inheriting class they are (delete is done in main)
00026 */
00027 
00028 #include <iostream>
00029 
00030 #include <jutils.h>
00031 #include <linklist.h>
00032 #include <config.h>
00033 
00034 Linklist::Linklist() {
00035   length = 0;
00036   first = NULL;
00037   last = NULL;
00038   if(pthread_mutex_init (&_mutex,NULL))
00039     error("%i:%s error initializing POSIX thread mutex",
00040           __LINE__,__FILE__);
00041 }
00042 
00043 Linklist::~Linklist() {
00044   clear();
00045   if(pthread_mutex_destroy(&_mutex))
00046     error("error destroying POSIX thread mutex",
00047           __LINE__,__FILE__);
00048 }
00049 
00050 void Linklist::lock() {
00051   pthread_mutex_lock(&_mutex);
00052 }
00053 void Linklist::unlock() {
00054   pthread_mutex_unlock(&_mutex);
00055 }
00056 
00057 /* adds one element at the end of the list */
00058 void Linklist::append(Entry *addr) {
00059   Entry *ptr = NULL;
00060   if(addr->list) addr->rem();
00061 
00062   lock();
00063 
00064   if(!last) { /* that's the first entry */
00065     last = addr;
00066     last->next = NULL;
00067     last->prev = NULL;
00068     first = last;
00069   } else { /* add the entry to the end */
00070     ptr = last;
00071     ptr->next = addr;
00072     addr->next = NULL;
00073     addr->prev = ptr;
00074     last = addr;
00075   }
00076   /* save the pointer to this list */
00077   addr->list = this;
00078   length++;
00079 
00080   unlock();
00081 
00082 }
00083 
00084 void Linklist::prepend(Entry *addr) {
00085   Entry *ptr = NULL;
00086   if(addr->list) addr->rem();
00087   lock();
00088   
00089   if(!first) { /* that's the first entry */
00090     first = addr;
00091     first->next = NULL;
00092     first->prev = NULL;
00093     last = first;
00094   } else { /* add an entry to the beginning */
00095     ptr = first;
00096     ptr->prev = addr;
00097     addr->next = ptr;
00098     addr->prev = NULL;
00099     first = addr;
00100   }
00101   addr->list = this;
00102   length++;
00103   unlock();
00104 }
00105 
00106 /* adds an element at the position specified
00107    if pos is out of bounds adds it at the beginning or the end
00108    the element occupying allready the position slides down 
00109    THIS FUNCTION IS NOT YET RELIABLE
00110 */
00111 void Linklist::insert(Entry *addr, int pos) {
00112   if(length<=pos) { /* adds it at the end */
00113     append(addr);
00114     return;
00115   } else if(pos<=1) {
00116     prepend(addr);
00117     return;
00118   }
00119 
00120   if(addr->list) addr->rem();
00121 
00122   Entry *ptr = pick(pos);
00123 
00124   lock();
00125   ptr->prev->next = addr;
00126   addr->prev = ptr->prev;
00127   
00128   ptr->prev = addr;
00129   addr->next = ptr;
00130   
00131   length++;
00132   addr->list = this;
00133   unlock();
00134 }
00135 
00136 /* clears the list
00137    i don't delete filters here because they have to be deleted
00138    from the procedure creating them. so this call simply discards
00139    the pointers stored into the linked list. OBJECTS ARE NOT FREED */
00140 bool Linklist::clear() {
00141   //  func("you are using Linklist::clear()");
00142   //  func("you have to free all the elements of the list by hand");
00143   //  func("it's use is highly error prone, be warned!");
00144   lock();
00145   sel(0);
00146   length = 0;
00147   first = NULL;
00148   last = NULL;
00149   unlock();
00150   return(true);
00151 }
00152 
00153 /* takes one element from the list
00154    === STARTING FROM 1 ===
00155    returns NULL if called with pos=0 or pos>length
00156    returns Entry pointer otherwise 
00157    this function is then overloading the operator[]
00158 */
00159 Entry *Linklist::pick(int pos) {
00160   if((length<pos)||(pos<1)) return(NULL);
00161   if(pos==1) return(first);
00162   if(pos==length) return(last);
00163 
00164   Entry *ptr = first;
00165   int c;
00166   for(c=1;c<pos;c++) ptr = ptr->next;
00167 
00168   return(ptr);
00169 }
00170 
00171 
00172 /* this function is a wrapper around Entry::up()
00173    better to use that if you have a pointer to your Entry */
00174 bool Linklist::moveup(int pos) {
00175   Entry *p = pick(pos);
00176   if(!p) return(false);
00177   return( p->up() );
00178 }
00179 bool Linklist::movedown(int pos) {
00180   Entry *p = pick(pos);
00181   if(!p) return(false);
00182   return( p->down() );
00183 }
00184 bool Linklist::moveto(int num, int pos) {
00185   Entry 
00186     *p = pick(num);
00187   if(!p) return(false);
00188   return( p->move(pos) );
00189 }
00190 /* removes one element from the list */
00191 bool Linklist::rem(int pos) {
00192   Entry *ptr = pick(pos);
00193   if(ptr==NULL) return(false);
00194   ptr->rem();
00195   return(true);
00196 }
00197   
00198 /* selects ONLY ONE, deselects the others
00199    use Entry::sel() if you want to do multiple selects */
00200 bool Linklist::sel(int pos) {
00201   int c;
00202   bool res = false;
00203   Entry *ptr = last;
00204 
00205   if(pos>length) return(res);
00206 
00207   for(c=length;c>0;c--) {
00208     if(c==pos) {
00209       if(ptr->select) 
00210         res = false; // was allready selected
00211       else {
00212         ptr->sel(true);
00213         res = true; // a new one is selected
00214       }
00215     } else ptr->sel(false);
00216     ptr = ptr->prev;
00217   }
00218   return(res);
00219 }
00220 
00221 /* returns the last one selected
00222    this is supposed to be used with single selections */
00223 Entry *Linklist::selected() {  
00224   int c;
00225   Entry *ptr = last;
00226   for(c=length;c>0;c--) {
00227     if(ptr->select) return ptr;
00228     ptr = ptr->prev;
00229   }
00230   return NULL;
00231 }
00232 
00233 Entry::Entry() {
00234   next = NULL;
00235   prev = NULL;
00236   list = NULL;
00237   select = false;
00238 }
00239 
00240 Entry::~Entry() {
00241   rem();
00242 }
00243 
00244 
00245 bool Entry::up() {
00246   if(!prev || !list) return(false);
00247   list->lock();
00248 
00249   Entry *tprev = prev,
00250     *tnext = next,
00251     *pp = prev->prev;
00252 
00253   if(!next)
00254     list->last = prev;
00255 
00256   if(tnext)
00257     tnext->prev = tprev;
00258 
00259   next = tprev;
00260   prev = pp;
00261   tprev->next = tnext;
00262   tprev->prev = this;
00263 
00264   if(pp)
00265     pp->next = this;
00266 
00267   if(!prev)
00268     list->first = this;
00269 
00270   list->unlock();
00271   return(true);
00272 }
00273 
00274 bool Entry::down() {
00275   if(!next || !list) return(false);
00276   list->lock();
00277 
00278   Entry *tprev = prev,
00279     *tnext = next,
00280     *nn = next->next;
00281 
00282   if(!prev)
00283     list->first = next;
00284 
00285   if(tprev)
00286     tprev->next = tnext;
00287 
00288   prev = tnext;
00289   next = nn;
00290   tnext->prev = tprev;
00291   tnext->next = this;
00292   if(nn)
00293     nn->prev = this;
00294 
00295   if(!next)
00296     list->last = this;
00297 
00298   list->unlock();
00299   return(true);
00300 }
00301 
00302 bool Entry::move(int pos) {
00303   func("Entry::move(%i) - NEW LINKLIST MOVE");
00304   if(!list) return(false);
00305   list->lock();
00306 
00307   Entry *tn, *tp;
00308 
00309   Entry *swapping = list->pick(pos);
00310   if(swapping == this) return(true);
00311   if(!swapping) return(false);
00312 
00313   tn = swapping->next;
00314   tp = swapping->prev;
00315 
00316   swapping->next = next;
00317   swapping->prev = prev;
00318   if(next) next->prev = swapping;
00319   else list->last = swapping;
00320   if(prev) prev->next = swapping;
00321   else list->first = swapping;
00322 
00323   next = tn;
00324   prev = tp;
00325   if(next) next->prev = this;
00326   else list->last = this;
00327   if(prev) prev->next = this;
00328   else list->first = this;
00329 
00330   list->unlock();
00331   func("LINKLIST MOVE RETURNS SUCCESS");
00332 
00333   return(true);
00334 }
00335 
00336 void Entry::rem() {
00337   if(!list) return;
00338   list->lock();
00339 
00340   if(prev)
00341     prev->next = next;
00342   else list->first = next;
00343   
00344   if(next)
00345     next->prev = prev;
00346   else list->last = prev;
00347 
00348   list->length--;
00349   list->unlock();
00350   list = NULL;
00351 }
00352 
00353 void Entry::sel(bool on) {
00354   select = on;
00355 }
00356 
00357 
00358 /* MUSE specific, deprecated use of ID and position */
00359 Entry *Linklist::pick_id(int id) {
00360   Entry *d = begin();
00361 
00362   while(d) {
00363     if(d->id == id) break;
00364     d = d->next;
00365   }
00366   return d;
00367 }
00368 
00369 int Linklist::selected_pos() {
00370   int c;
00371   Entry *ptr = last;
00372   for(c=length;c>0;c--) {
00373     if(ptr->select) return c;
00374     ptr = ptr->prev;
00375   }
00376   return 0;
00377 }

Generated on Thu Dec 16 12:28:21 2004 for MuSE by doxygen1.3