prj/tech/libsrc/cpptools/fixedstk.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // $Source: x:/prj/tech/libsrc/cpptools/RCS/fixedstk.h $
   3 // $Author: TOML $
   4 // $Date: 1997/09/22 22:29:29 $
   5 // $Revision: 1.1 $
   6 //
   7 // Fixed size stacks of fixed size things...
   8 //
   9 // Very simple overflowing circular stack structures, with thread-safe and
  10 // normal versions.  Designed with systems-level stuff in mind -- Not meant for
  11 // use with high copy overhead -- or any complex use really.  Input devices,
  12 // network protocols, multithreaded communication...
  13 //
  14 // Not a lot of error checking!
  15 //
  16 // Tries to remain consistent if in interrupt situation, but not verified! Make
  17 // sure to declare instance volatile if using under interrupt
  18 //
  19 // Size MUST be a power of 2, because we implement the wrap-around logic
  20 // (index = (index + 1) % kMaxElems) with only powers of 2 in mind
  21 // (index = (index + 1) & (kMaxElems - 1)) for performance
  22 //
  23 // We use temporaries so that values are never totally invalid (i.e., we can never
  24 // be interrrupted or preempted with either insert or remove index pointing
  25 // off the end of the array)
  26 //
  27
  28 #ifndef __FIXEDSTK_H
  29 #define __FIXEDSTK_H
  30
  31 ///////////////////////////////////////////////////////////////////////////////
  32 //
  33 // TEMPLATE: cFixedStack
  34 //
  35 // A simple stack for things like device managers, network handling, etc.
  36 //
  37
  38 template <class T, unsigned kMaxElems>
  39 class cFixedStack
  40 {
  41     // A macro is used for index advancement to _ensure_ this
  42     // is inlined -- Watcom sometimes decides not to inline
  43     // this tiny code fragment!
  44
  45     #define cFixedStack_Advance(index) \
  46     { \
  47         register unsigned temp = index; \
  48         temp++; \
  49         temp &= unsigned(kMaxElems - 1); \
  50         index = temp; \
  51     }
  52
  53     #define cFixedStack_Retreat(index) \
  54     { \
  55         register unsigned temp = index; \
  56         temp--; \
  57         temp &= unsigned(kMaxElems - 1); \
  58         index = temp; \
  59     }
  60
  61 public:
  62     cFixedStack()
  63     {
  64         #ifdef DEBUG
  65         unsigned test = ((kMaxElems) & (kMaxElems - 1));
  66         AssertMsg(test == 0, "Must be power of 2");
  67         #endif
  68         m_iNext = m_iBottom = 0;
  69     }
  70
  71     //
  72     // Queries for stack state
  73     //
  74     BOOL IsEmpty()
  75     {
  76         return (m_iNext == m_iBottom);
  77     }
  78
  79     BOOL IsFull()
  80     {
  81         return (((m_iNext + 1) & unsigned(kMaxElems - 1)) == m_iBottom);
  82     }
  83
  84     unsigned GetSize()
  85     {
  86         return kMaxElems;
  87     }
  88
  89     //
  90     // Empty the stack
  91     //
  92     void Flush()
  93     {
  94         m_iNext = 0;
  95         m_iBottom = 0;
  96     }
  97
  98     //
  99     // Push to the stack, discarding oldest if overflown.  TRUE is no overflow
 100     //
 101     BOOL Push(const T * pPush)
 102     {
 103         const BOOL fOverflow = IsFull();
 104
 105         // If overflowing, discard oldest stack item...
 106         if (fOverflow)
 107         {
 108             cFixedStack_Advance(m_iBottom);
 109         }
 110
 111         m_Entries[m_iNext] = *pPush;
 112
 113         cFixedStack_Advance(m_iNext);
 114
 115         return fOverflow;
 116     }
 117
 118     //
 119     // Push to the stack, getting pointer to added item.
 120     // TRUE is no overflow
 121     //
 122     BOOL Push(const T * pPush, const T ** ppPushed)
 123     {
 124         const BOOL fOverflow = IsFull();
 125
 126         if (fOverflow)
 127         {
 128             cFixedStack_Advance(m_iBottom);
 129         }
 130
 131         *ppPushed = &m_Entries[m_iNext];
 132         m_Entries[m_iNext] = *pPush;
 133
 134         cFixedStack_Advance(m_iNext);
 135
 136         return fOverflow;
 137     }
 138
 139     //
 140     // Push to the stack, discarding if overflown.  TRUE is no overflow
 141     //
 142     BOOL PushUnlessFull(const T * pPush)
 143     {
 144         if (!IsFull())
 145         {
 146             m_Entries[m_iNext] = *pPush;
 147             cFixedStack_Advance(m_iNext);
 148             return TRUE;
 149         }
 150         return FALSE;
 151     }
 152
 153     //
 154     // Push to the stack, getting pointer to added item.
 155     // TRUE is no overflow
 156     //
 157     BOOL PushUnlessFull(const T * pPush, const T ** ppPushed)
 158     {
 159         if (!IsFull())
 160         {
 161             *ppPushed = &m_Entries[m_iNext];
 162             m_Entries[m_iNext] = *pPush;
 163             cFixedStack_Advance(m_iNext);
 164             return TRUE;
 165         }
 166         *ppPushed = NULL;
 167         return FALSE;
 168     }
 169
 170     //
 171     // Get the next available item from the stack. TRUE if
 172     // there is any.
 173     //
 174     BOOL Pop(T * pReturn)
 175     {
 176         if (!IsEmpty())
 177         {
 178             cFixedStack_Retreat(m_iNext);
 179             *pReturn = m_Entries[m_iNext];
 180             return TRUE;
 181         }
 182         return FALSE;
 183     }
 184
 185     //
 186     // Check for the next available item from the stack. TRUE if
 187     // there is any.
 188     //
 189     BOOL Peek(T * pReturn)
 190     {
 191         if (!IsEmpty())
 192         {
 193             *pReturn = m_Entries[((m_iNext - 1) & unsigned(kMaxElems - 1))];
 194             return TRUE;
 195         }
 196         return FALSE;
 197     }
 198
 199     //
 200     // Check for the next available item from the stack.
 201     // Results are undefined if stack is actually empty
 202     //
 203     const T & Peek()
 204     {
 205         return m_Entries[((m_iNext - 1) & unsigned(kMaxElems - 1))];
 206     }
 207
 208     //
 209     // Threading support
 210     //
 211     BOOL WaitForData(ulong msecTimeout = 0)
 212     {
 213         return !IsEmpty();
 214     }
 215     HANDLE GetAvailabilitySignalHandle()    { return NULL; }
 216     void Lock()                             {}
 217     void Unlock()                           {}
 218
 219
 220 private:
 221     unsigned    m_iNext;
 222     unsigned    m_iBottom;
 223
 224     T           m_Entries[kMaxElems];
 225
 226     #undef cFixedStack_Advance
 227     #undef cFixedStack_Retreat
 228 };
 229
 230 ///////////////////////////////////////////////////////////////////////////////
 231 //
 232 // TEMPLATE: cFixedMTStack
 233 //
 234 // A thread-safe version of cFixedStack
 235 //
 236
 237 #ifdef __THRDTOOL_H
 238
 239 template <class T, unsigned kMaxElems>
 240 class cFixedMTStack : private cFixedStack<T, kMaxElems>
 241 {
 242 public:
 243     BOOL IsEmpty()
 244     {
 245         cAutoLock lock(m_Lock);
 246         return cFixedStack<T, kMaxElems>::IsEmpty();
 247     }
 248
 249     BOOL IsFull()
 250     {
 251         cAutoLock lock(m_Lock);
 252         return cFixedStack<T, kMaxElems>::IsFull();
 253     }
 254
 255     unsigned GetSize()
 256     {
 257         return cFixedStack<T, kMaxElems>::GetSize();
 258     }
 259
 260     void Flush()
 261     {
 262         cAutoLock lock(m_Lock);
 263         cFixedStack<T, kMaxElems>::Flush();
 264     }
 265
 266     BOOL Push(const T * pPush)
 267     {
 268         cAutoLock lock(m_Lock);
 269         if (IsEmpty())
 270             m_AvailabilitySignal.Set();
 271         return cFixedStack<T, kMaxElems>::Push(pPush);
 272     }
 273
 274     BOOL Push(const T * pPush, const T ** ppPushed)
 275     {
 276         cAutoLock lock(m_Lock);
 277         if (IsEmpty())
 278             m_AvailabilitySignal.Set();
 279         return cFixedStack<T, kMaxElems>::Push(pPush, ppPushed);
 280     }
 281
 282     BOOL PushUnlessFull(const T * pPush)
 283     {
 284         cAutoLock lock(m_Lock);
 285         if (IsEmpty())
 286             m_AvailabilitySignal.Set();
 287         return cFixedStack<T, kMaxElems>::PushUnlessFull(pPush);
 288     }
 289
 290     BOOL PushUnlessFull(const T * pPush, const T ** ppPushed)
 291     {
 292         cAutoLock lock(m_Lock);
 293         if (IsEmpty())
 294             m_AvailabilitySignal.Set();
 295         return cFixedStack<T, kMaxElems>::PushUnlessFull(pPush, ppPushed);
 296     }
 297
 298     BOOL Pop(T * pReturn)
 299     {
 300         cAutoLock lock(m_Lock);
 301         BOOL result = cFixedStack<T, kMaxElems>::Pop(pReturn);
 302         if (IsEmpty())
 303             m_AvailabilitySignal.Reset();
 304         return result;
 305     }
 306
 307     BOOL Peek(T * pReturn)
 308     {
 309         cAutoLock lock(m_Lock);
 310         return cFixedStack<T, kMaxElems>::Peek(pReturn);
 311     }
 312
 313     BOOL WaitForData(ulong msecTimeout = INFINITE)
 314     {
 315         return m_AvailabilitySignal.Wait(msecTimeout);
 316     }
 317
 318     HANDLE GetAvailabilitySignalHandle()
 319     {
 320         return m_AvailabilitySignal;
 321     }
 322
 323     void Lock()
 324     {
 325         m_Lock.Lock();
 326     }
 327
 328     void Unlock()
 329     {
 330         m_Lock.Unlock();
 331     }
 332
 333 private:
 334     cThreadLock  m_Lock;
 335     cThreadEvent m_AvailabilitySignal;
 336 };
 337
 338 #endif
 339
 340 ///////////////////////////////////////////////////////////////////////////////
 341
 342 #endif /* !__FIXEDSTK_H */