/ray/src/lib/tl/linkedlist.h File Reference

Linked list template. More...

#include <lib/sconfig.h>

Include dependency graph for linkedlist.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	LinkedList
	List class holding a list of objects derived from LinkedListBase (not thread-safe). More...
struct	LinkedListBase
	Base class for linked list item nodes. More...
Defines
#define	_TemplateLibrary_LinkedList_H_   1
#define	_LLB   LinkedListBase<T>

---

Detailed Description

Linked list template.

Author:

Wolfgang Wieser ] wwieser (a) gmx <*> de [

In real life one often has the "problem" to put manage several items using a linked list and these items are not meant to be part of more than one list at a time.
Hence, using standard list templates where one node entry is allocated for every list entry is too inefficient and over-engineered for this type of access: One could easily put the prev and next pointers directly into the item (only these two poiners are needed since the item is only in one list at a time -- or in no list at all).

This is just what these classes implement:

• LinkedListBase<T> is to be used as a base class for the item objects T to be queued. This contains only 2 pointers, prev and next, which are publically accessible to make lives easier (see below).
• LinkedList<T> is the linked list of objects of type T (which must have been derived from LinkedListBase<T>.
  This class is not thread-safe.

  Note:

  In order to make a linked list thread-safe you need to use an external mutex. There is little point in integrating the mutex into the list itself since you need to lock the mutex outside the linked list template implementation when operating on the list -- even when just reading, e.g.:

          Node res=NULL;
          mutex.lock();    // <-- before starting to operate on list
          for(Node *i=list.first(); i; i=i->next)
          {
              if(i->name==name)
              {  res=i;  break;  }
          }
          mutex.unlock();  // <-- done with operations on list
  

  Here is a little code example:

    // Item types to be queued: 
    struct ServerDesc : LinkedListBase<ServerDesc>
    {
        InetAdr address;
      int port;
        
        ServerDesc(const char *str);
        int connect();
    };

And somewhere else, we have the list:

    LinkedList<ServerDesc> slist;
    ServerDesc *sd=new ServerDesc("localhost:22");
  slist.append(sd);

It is easy to traverse the list first-to-last or last-to-first using e.g. (first-to-last here):

    for(ServerDesc *i=slist.first(); i; i=i->next)
        i->connect();

(Note that you do not need all the iterator object fuzz.)

Definition in file linkedlist.h.

---

Define Documentation

#define _LLB   LinkedListBase<T>

Definition at line 118 of file linkedlist.h.

#define _TemplateLibrary_LinkedList_H_   1

Definition at line 19 of file linkedlist.h.

---