LCOV - code coverage report
Current view: top level - src - List.h (source / functions) Hit Total Coverage
Test: app.info Lines: 7 9 77.8 %
Date: 2010-12-13 Functions: 9 11 81.8 %
Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : // $Id: List.h 463 2004-09-26 21:04:20Z vern $
       2                 :            : 
       3                 :            : #ifndef list_h
       4                 :            : #define list_h
       5                 :            : 
       6                 :            : // BaseList.h --
       7                 :            : //      Interface for class BaseList, current implementation is as an
       8                 :            : //      array of ent's.  This implementation was chosen to optimize
       9                 :            : //      getting to the ent's rather than inserting and deleting.
      10                 :            : //      Also pairs of append's and get's act like push's and pop's
      11                 :            : //      and are very efficient.  The only really expensive operations
      12                 :            : //      are inserting (but not appending), which requires pushing every
      13                 :            : //      element up, and resizing the list, which involves getting new space
      14                 :            : //      and moving the data.  Resizing occurs automatically when inserting
      15                 :            : //      more elements than the list can currently hold.  Automatic
      16                 :            : //      resizing is done one "chunk_size" of elements at a time and
      17                 :            : //      always increases the size of the list.  Resizing to zero
      18                 :            : //      (or to less than the current value of num_entries)
      19                 :            : //      will decrease the size of the list to the current number of
      20                 :            : //      elements.  Resize returns the new max_entries.
      21                 :            : //
      22                 :            : //      Entries must be either a pointer to the data or nonzero data with
      23                 :            : //      sizeof(data) <= sizeof(void*).
      24                 :            : 
      25                 :            : #include <stdarg.h>
      26                 :            : #include "util.h"
      27                 :            : 
      28                 :            : typedef void* ent;
      29                 :            : typedef int (*list_cmp_func)(const void* v1, const void* v2);
      30                 :            : 
      31                 :            : class BaseList {
      32                 :            : public:
      33                 :     626260 :         ~BaseList()             { clear(); }
      34                 :            : 
      35                 :            :         void clear();           // remove all entries
      36                 :    6317083 :         int length() const      { return num_entries; }
      37                 :            :         int chunk() const       { return chunk_size; }
      38                 :            :         int max() const         { return max_entries; }
      39                 :            :         int resize(int = 0);    // 0 => size to fit current number of entries
      40                 :            : 
      41                 :            :         void sort(list_cmp_func cmp_func);
      42                 :            : 
      43                 :          0 :         int MemoryAllocation() const
      44                 :          0 :                 { return padded_sizeof(*this) + pad_size(max_entries * sizeof(ent)); }
      45                 :            : 
      46                 :            : protected:
      47                 :            :         BaseList(int = 0);
      48                 :            :         BaseList(BaseList&);
      49                 :            : 
      50                 :            :         void insert(ent);       // add at head of list
      51                 :            : 
      52                 :            :         // Assumes that the list is sorted and inserts at correct position.
      53                 :            :         void sortedinsert(ent, list_cmp_func cmp_func);
      54                 :            : 
      55                 :            :         void append(ent);       // add to end of list
      56                 :            :         ent remove(ent);        // delete entry from list
      57                 :            :         ent remove_nth(int);    // delete nth entry from list
      58                 :            :         ent get();              // return and remove ent at end of list
      59                 :         16 :         ent last()              // return at end of list
      60                 :         16 :                 { return entry[num_entries-1]; }
      61                 :            : 
      62                 :            :         // Return 0 if ent is not in the list, ent otherwise.
      63                 :            :         ent is_member(ent) const;
      64                 :            : 
      65                 :            :         // Returns -1 if ent is not in the list, otherwise its position.
      66                 :            :         int member_pos(ent) const;
      67                 :            : 
      68                 :            :         ent replace(int, ent);  // replace entry #i with a new value
      69                 :            : 
      70                 :            :         // Return nth ent of list (do not remove).
      71                 :    6771234 :         ent operator[](int i) const
      72                 :            :                 {
      73                 :            : #ifdef SAFE_LISTS
      74                 :            :                 if ( i < 0 || i > num_entries-1 )
      75                 :            :                         return 0;
      76                 :            :                 else
      77                 :            : #endif
      78                 :    6771234 :                         return entry[i];
      79                 :            :                 }
      80                 :            : 
      81                 :            :         void operator=(BaseList&);
      82                 :            : 
      83                 :            :         ent* entry;
      84                 :            :         int chunk_size;         // increase size by this amount when necessary
      85                 :            :         int max_entries;
      86                 :            :         int num_entries;
      87                 :            :         };
      88                 :            : 
      89                 :            : 
      90                 :            : // List.h -- interface for class List
      91                 :            : //      Use:    to get a list of pointers to class foo you should:
      92                 :            : //              1) typedef foo* Pfoo; (the macros don't like explicit pointers)
      93                 :            : //              2) declare(List,Pfoo); (declare an interest in lists of Pfoo's)
      94                 :            : //              3) variables are declared like:
      95                 :            : //                              List(Pfoo) bar; (bar is of type list of Pfoo's)
      96                 :            : 
      97                 :            : // For lists of "type".
      98                 :            : 
      99                 :            : #define List(type) type ## List
     100                 :            : 
     101                 :            : // For lists of pointers to "type"
     102                 :            : #define PList(type) type ## PList
     103                 :            : 
     104                 :            : #define Listdeclare(type)                                               \
     105                 :            : struct List(type) : BaseList                                            \
     106                 :            :         {                                                               \
     107                 :            :         List(type)(type ...);                                           \
     108                 :            :         List(type)() : BaseList(0) {}                                   \
     109                 :            :         List(type)(int sz) : BaseList(sz) {}                            \
     110                 :            :         List(type)(List(type)& l) : BaseList((BaseList&)l) {}           \
     111                 :            :                                                                         \
     112                 :            :         void operator=(List(type)& l)                                       \
     113                 :            :                 { BaseList::operator=((BaseList&)l); }                      \
     114                 :            :         void insert(type a)     { BaseList::insert(ent(a)); }           \
     115                 :            :         void sortedinsert(type a, list_cmp_func cmp_func)               \
     116                 :            :                 { BaseList::sortedinsert(ent(a), cmp_func); }           \
     117                 :            :         void append(type a)     { BaseList::append(ent(a)); }           \
     118                 :            :         type remove(type a)                                             \
     119                 :            :                         { return type(BaseList::remove(ent(a))); }      \
     120                 :            :         type remove_nth(int n)  { return type(BaseList::remove_nth(n)); }\
     121                 :            :         type get()              { return type(BaseList::get()); }       \
     122                 :            :         type last()             { return type(BaseList::last()); }      \
     123                 :            :         type replace(int i, type new_type)                              \
     124                 :            :                 { return type(BaseList::replace(i,ent(new_type))); }    \
     125                 :            :         type is_member(type e) const                                    \
     126                 :            :                 { return type(BaseList::is_member(ent(e))); }           \
     127                 :            :         int member_pos(type e) const                                    \
     128                 :            :                 { return BaseList::member_pos(ent(e)); }                \
     129                 :            :                                                                         \
     130                 :            :         type operator[](int i) const                                    \
     131                 :            :                 { return type(BaseList::operator[](i)); }               \
     132                 :            :         };                                                              \
     133                 :            : 
     134                 :            : #define Listimplement(type)                                             \
     135                 :            : List(type)::List(type)(type e1 ...) : BaseList()                        \
     136                 :            :         {                                                               \
     137                 :            :         append(e1);                                                     \
     138                 :            :         va_list ap;                                                     \
     139                 :            :         va_start(ap,e1);                                                \
     140                 :            :         for ( type e = va_arg(ap,type); e != 0; e = va_arg(ap,type) )   \
     141                 :            :                 append(e);                                              \
     142                 :            :         resize();                                                       \
     143                 :            :         }
     144                 :            : 
     145                 :            : #define PListdeclare(type)                                              \
     146                 :            : struct PList(type) : BaseList                                           \
     147                 :            :         {                                                               \
     148                 :            :         PList(type)(type* ...);                                         \
     149                 :            :         PList(type)() : BaseList(0) {}                                  \
     150                 :            :         PList(type)(int sz) : BaseList(sz) {}                           \
     151                 :            :         PList(type)(PList(type)& l) : BaseList((BaseList&)l) {}         \
     152                 :            :                                                                         \
     153                 :            :         void operator=(PList(type)& l)                                      \
     154                 :            :                 { BaseList::operator=((BaseList&)l); }                      \
     155                 :            :         void insert(type* a)    { BaseList::insert(ent(a)); }           \
     156                 :            :         void sortedinsert(type* a, list_cmp_func cmp_func)              \
     157                 :            :                 { BaseList::sortedinsert(ent(a), cmp_func); }           \
     158                 :            :         void append(type* a)    { BaseList::append(ent(a)); }           \
     159                 :            :         type* remove(type* a)                                           \
     160                 :            :                 { return (type*)BaseList::remove(ent(a)); }             \
     161                 :            :         type* remove_nth(int n) { return (type*)(BaseList::remove_nth(n)); }\
     162                 :            :         type* get()             { return (type*)BaseList::get(); }      \
     163                 :            :         type* operator[](int i) const                                   \
     164                 :            :                 { return (type*)(BaseList::operator[](i)); }            \
     165                 :            :         type* replace(int i, type* new_type)                            \
     166                 :            :                 { return (type*)BaseList::replace(i,ent(new_type)); }   \
     167                 :            :         type* is_member(type* e)                                        \
     168                 :            :                 { return (type*)BaseList::is_member(ent(e)); }          \
     169                 :            :         int member_pos(type* e)                                         \
     170                 :            :                 { return BaseList::member_pos(ent(e)); }                \
     171                 :            :         };                                                              \
     172                 :            : 
     173                 :            : #define PListimplement(type)                                            \
     174                 :            : PList(type)::PList(type)(type* ep1 ...) : BaseList()                    \
     175                 :            :         {                                                               \
     176                 :            :         append(ep1);                                                    \
     177                 :            :         va_list ap;                                                     \
     178                 :            :         va_start(ap,ep1);                                               \
     179                 :            :         for ( type* ep = va_arg(ap,type*); ep != 0;                     \
     180                 :            :               ep = va_arg(ap,type*) )                                   \
     181                 :            :                 append(ep);                                             \
     182                 :            :         resize();                                                       \
     183                 :            :         }
     184                 :            : 
     185                 :            : 
     186                 :            : #define declare(metatype,type) metatype ## declare (type)
     187                 :            : 
     188                 :            : // Popular type of list: list of strings.
     189                 :      28137 : declare(PList,char);
     190                 :            : typedef PList(char) name_list;
     191                 :            : 
     192                 :            : // Macro to visit each list element in turn.
     193                 :            : #define loop_over_list(list, iterator)  \
     194                 :            :         int iterator;   \
     195                 :            :         for ( iterator = 0; iterator < (list).length(); ++iterator )
     196                 :            : 
     197                 :            : #endif /* list_h */

Generated by: LCOV version 1.8