Source/LinkedList.h

   1 /*
   2  * Copyright (c) 1999-2002 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Portions Copyright (c) 1999-2002 Apple Computer, Inc.  All Rights
   7  * Reserved.  This file contains Original Code and/or Modifications of
   8  * Original Code as defined in and that are subject to the Apple Public
   9  * Source License Version 1.1 (the "License").  You may not use this file
  10  * except in compliance with the License.  Please obtain a copy of the
  11  * License at http://www.apple.com/publicsource and read it before using
  12  * this file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT.  Please see the
  19  * License for the specific language governing rights and limitations
  20  * under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  *
  24  * Modified: $Date: 2002/04/27 20:52:48 $
  25  * Revision: $Id: LinkedList.h,v 1.3 2002/04/27 20:52:48 lane Exp $
  26  */
  27
  28
  29 /*
  30         File:           LinkedList.h
  31
  32         Contains:
  33
  34 */
  35
  36 #ifndef __LINKEDLIST__
  37 #define __LINKEDLIST__
  38
  39
  40 //we cant just use "macintosh_build" - the mac macho_build is designated as "posix_build" but may
  41 //include open transport in some cases
  42 #ifndef __OPENTRANSPORT__
  43 //#if (!macintosh_build)
  44
  45 #include <stddef.h>             //for OTGetLinkObject replacement
  46
  47 #include "OPUtils.h"    //for true/false
  48
  49 #if (windows_build)
  50
  51 // ECF 010928 win32 syncronization routines for safe critical sections.  We can't simply use TryEnterCriticalSection()
  52 // to return a true/false value because it's not available in win95 and 98
  53 class OSCriticalSection
  54 {
  55         public:
  56                 NMBoolean locked;
  57                 OSCriticalSection() {locked = false; InitializeCriticalSection(&theCriticalSection);}
  58                 ~OSCriticalSection() {DeleteCriticalSection(&theCriticalSection);}
  59                 NMBoolean       acquire()       {       if (locked == true) return false; //dont have to wait in this case
  60                                                                 EnterCriticalSection(&theCriticalSection);
  61                                                                 if (locked) {LeaveCriticalSection(&theCriticalSection); return false;}
  62                                                                 else {locked = true; LeaveCriticalSection(&theCriticalSection); return true;}}
  63                 void    release()       {       EnterCriticalSection(&theCriticalSection);
  64                                                                 locked = false; LeaveCriticalSection(&theCriticalSection);}
  65
  66         CRITICAL_SECTION theCriticalSection;
  67 };
  68 #endif //windows_build
  69
  70 #if (posix_build)
  71 #include <pthread.h>
  72 class OSCriticalSection
  73 {
  74         public:
  75                 OSCriticalSection() {pthread_mutex_init(&theMutex,NULL);}
  76                 ~OSCriticalSection() {pthread_mutex_destroy(&theMutex);}
  77                 NMBoolean       acquire()       {       int error = pthread_mutex_trylock(&theMutex);
  78                                                                         if (error) return false; else return true;}
  79                 void    release()       {       pthread_mutex_unlock(&theMutex);}
  80
  81                 pthread_mutex_t theMutex;
  82 };
  83
  84 #endif //(posix_build)
  85
  86 /*      -------------------------------------------------------------------------
  87         ** OTLIFO
  88         **
  89         ** These are functions to implement a LIFO list that is interrupt-safe.
  90         ** The only function which is not is OTReverseList.  Normally, you create
  91         ** a LIFO list, populate it at interrupt time, and then use OTLIFOStealList
  92         ** to atomically remove the list, and OTReverseList to flip the list so that
  93         ** it is a FIFO list, which tends to be more useful.
  94         ------------------------------------------------------------------------- */
  95
  96         class OTLink;
  97         class OTLIFO;
  98
  99         class OTLink
 100         {
 101                 public:
 102                         OTLink* fNext;
 103                         void    Init()
 104                                                 { fNext = NULL; }
 105         };
 106
 107         class OTLIFO
 108         {
 109                 public:
 110                         OSCriticalSection theLock;
 111                         OTLink* fHead;
 112
 113                         void    Init()
 114                                         { fHead = NULL; }
 115
 116                         void    Enqueue(OTLink* link)
 117                                                         {
 118                                                                 while (true) {if (theLock.acquire()) break;}
 119                                                                 link->fNext = fHead;
 120                                                                 fHead = link;
 121                                                                 theLock.release();
 122                                                         }
 123
 124
 125                         OTLink* Dequeue()
 126                                                         {
 127                                                                 while (true) {if (theLock.acquire()) break;}
 128                                                                 OTLink *origHead = fHead;
 129                                                                 fHead = fHead->fNext;
 130                                                                 theLock.release();
 131                                                                 return origHead;
 132                                                         }
 133
 134
 135                         OTLink* StealList()
 136                                                         {
 137                                                                 while (true) {if (theLock.acquire()) break;}
 138                                                                 OTLink *origHead = fHead;
 139                                                                 fHead = NULL;
 140                                                                 theLock.release();
 141                                                                 return origHead;
 142                                                         }
 143
 144
 145                         NMBoolean       IsEmpty()
 146                                                         {
 147                                                                 return fHead == NULL;
 148                                                         }
 149         };
 150
 151 /*      -------------------------------------------------------------------------
 152         ** OTList
 153         **
 154         ** An OTList is a non-interrupt-safe list, but has more features than the
 155         ** OTLIFO list. It is a standard singly-linked list.
 156         ------------------------------------------------------------------------- */
 157
 158         typedef struct OTList   OTList;
 159
 160                 typedef NMBoolean (*OTListSearchProcPtr)(const void* ref, OTLink* linkToCheck);
 161                 //
 162                 // Remove the last link from the list
 163                 //
 164         extern OTLink*          OTRemoveLast(OTList* pList);
 165                 //
 166                 // Return the first link from the list
 167                 //
 168         extern OTLink*          OTGetFirst(OTList* pList);
 169                 //
 170                 // Return the last link from the list
 171                 //
 172         extern OTLink*          OTGetLast(OTList* pList);
 173                 //
 174                 // Return true if the link is present in the list
 175                 //
 176         extern NMBoolean                OTIsInList(OTList* pList, OTLink* link);
 177                 //
 178                 // Find a link in the list which matches the search criteria
 179                 // established by the search proc and the refPtr.  This is done
 180                 // by calling the search proc, passing it the refPtr and each
 181                 // link in the list, until the search proc returns true.
 182                 // NULL is returned if the search proc never returned true.
 183                 //
 184         extern OTLink*          OTFindLink(OTList* pList, OTListSearchProcPtr proc, const void* refPtr);
 185                 //
 186                 // Remove the specified link from the list, returning true if it was found
 187                 //
 188         extern NMBoolean                OTRemoveLink(OTList*, OTLink*);
 189                 //
 190                 // Similar to OTFindLink, but it also removes it from the list.
 191                 //
 192         extern OTLink*          OTFindAndRemoveLink(OTList* pList, OTListSearchProcPtr proc, const void* refPtr);
 193                 //
 194                 // Return the "index"th link in the list
 195                 //
 196         extern OTLink*          OTGetIndexedLink(OTList* pList, size_t index);
 197
 198         struct OTList
 199         {
 200                 OTLink*         fHead;
 201
 202                 void            Init()
 203                                                 { fHead = NULL; }
 204
 205                 NMBoolean               IsEmpty()
 206                                                 { return fHead == NULL; }
 207
 208                 void            AddFirst(OTLink* link)
 209                                                         {
 210                                                                 link->fNext = fHead;
 211                                                                 fHead = link;
 212                                                         }
 213
 214                 void            AddLast(OTLink* link)
 215                                                         {
 216                                                                 if (fHead == NULL)
 217                                                                         fHead = link->fNext;
 218                                                                 else
 219                                                                 {
 220                                                                         OTLink *current = fHead;
 221
 222                                                                         while (current->fNext != NULL)
 223                                                                                 current = current->fNext;
 224
 225                                                                         current->fNext = link;
 226                                                                 }
 227
 228
 229                                                                 link->fNext = fHead;
 230                                                                 fHead = link;
 231                                                         }
 232
 233
 234                 OTLink*         GetFirst()
 235                                                 { return OTGetFirst(this); }
 236
 237                 OTLink*         GetLast()
 238                                                 { return OTGetLast(this); }
 239
 240                 OTLink*         RemoveFirst()
 241                                                         {
 242                                                                 OTLink *origHead = fHead;
 243                                                                 fHead = fHead->fNext;
 244                                                                 return origHead;
 245                                                         }
 246
 247                 OTLink*         RemoveLast()
 248                                                 { return OTRemoveLast(this); }
 249
 250                 NMBoolean               IsInList(OTLink* link)
 251                                                 { return OTIsInList(this, link); }
 252
 253                 OTLink*         FindLink(OTListSearchProcPtr proc, const void* ref)
 254                                                 { return OTFindLink(this, proc, ref); }
 255
 256                 NMBoolean               RemoveLink(OTLink* link)
 257                                                 { return OTRemoveLink(this, link); }
 258
 259                 OTLink*         RemoveLink(OTListSearchProcPtr proc, const void* ref)
 260                                                 { return OTFindAndRemoveLink(this, proc, ref); }
 261
 262                 OTLink*         GetIndexedLink(size_t index)
 263                                                 { return OTGetIndexedLink(this, index); }
 264         };
 265
 266
 267 //FIXME!!  this is a recursive function and will crash and burn on large lists
 268 static OTLink* OTReverseList(OTLink *headRef)
 269 {
 270         OTLink  *first;
 271         OTLink  *rest;
 272
 273         if (headRef == NULL) return NULL;
 274
 275         first = headRef;
 276         rest = (OTLink *) first->fNext;
 277
 278         if (rest == NULL) return headRef;
 279
 280         rest = OTReverseList(rest);
 281
 282         first->fNext->fNext = first;
 283         first->fNext = NULL;
 284
 285         return rest;
 286 }
 287
 288
 289         #define OTGetLinkObject(link, struc, field)     \
 290                 ((struc*)((char*)(link) - offsetof(struc, field)))
 291
 292 #endif //!macintosh_build
 293 #endif  /* __LINKEDLIST__ */
 294
 295