Stripe_u/queue.c

   1 /********************************************************************/
   2 /*   STRIPE: converting a polygonal model to triangle strips
   3      Francine Evans, 1996.
   4      SUNY @ Stony Brook
   5      Advisors: Steven Skiena and Amitabh Varshney
   6 */
   7 /********************************************************************/
   8
   9 /*---------------------------------------------------------------------*/
  10 /*   STRIPE: queue.c
  11      This file contains the routines used in the data structures lists, which
  12      are queues.
  13 */
  14 /*---------------------------------------------------------------------*/
  15
  16  #include "queue.h"
  17
  18
  19
  20 /*----------------------------------------------------------------------------
  21  * InitList:
  22  */
  23 BOOL  InitList  (PLISTHEAD LHead)
  24
  25 {
  26      if (LHead == NULL) return(FALSE);
  27
  28      LHead->LHeaders[LISTHEAD] = LHead->LHeaders[LISTTAIL] = NULL;
  29      LHead->NumList = 0;
  30      return(TRUE);
  31 }
  32
  33 /*----------------------------------------------------------------------------
  34  * AddHead:
  35  */
  36 BOOL  AddHead(PLISTHEAD LHead, PLISTINFO LInfo)
  37 {
  38      if (LHead == NULL || LInfo == NULL)
  39           return(FALSE);
  40      if (EMPTYLIST(LHead))
  41           LHead->LHeaders[LISTTAIL] = LInfo;
  42      else LHead->LHeaders[LISTHEAD]->ListNode.Previous = (void  *) LInfo;
  43
  44      LInfo->ListNode.Next = (void  *) LHead->LHeaders[LISTHEAD];
  45      LHead->LHeaders[LISTHEAD] = LInfo;
  46      LInfo->ListNode.Previous = NULL;
  47      LHead->NumList++;
  48      return(TRUE);
  49 }
  50
  51 /*----------------------------------------------------------------------------
  52  * AddTail
  53  */
  54 BOOL  AddTail(PLISTHEAD LHead, PLISTINFO LInfo)
  55 {
  56      if (LHead == NULL || LInfo == NULL)
  57           return(FALSE);
  58      if (EMPTYLIST(LHead))
  59           LHead->LHeaders[LISTHEAD] = LInfo;
  60      else LHead->LHeaders[LISTTAIL]->ListNode.Next = (void *) LInfo;
  61
  62      LInfo->ListNode.Previous = (void  *) LHead->LHeaders[LISTTAIL];
  63      LHead->LHeaders[LISTTAIL] = LInfo;
  64      LInfo->ListNode.Next = NULL;
  65      LHead->NumList++;
  66      return(TRUE);
  67 }
  68
  69
  70 BOOL  InsertNode( PLISTHEAD LHead, int nPos, PLISTINFO LInfo )
  71 {
  72 PLISTINFO LAddNode;
  73
  74      if ( LHead == NULL || LInfo == NULL || nPos > NumOnList( LHead ) )
  75           return( FALSE );
  76
  77      if ( nPos == 0 )
  78           AddHead( LHead, LInfo );
  79      else if ( nPos == NumOnList( LHead ) )
  80           AddTail( LHead, LInfo );
  81      else
  82      {
  83           if ( (LAddNode = PeekList( LHead, LISTHEAD, nPos - 1 )) == NULL )
  84                return( FALSE );
  85
  86           ((PLISTINFO)LAddNode->ListNode.Next)->ListNode.Previous = LInfo;
  87           LInfo->ListNode.Next      = LAddNode->ListNode.Next;
  88           LInfo->ListNode.Previous  = LAddNode;
  89           LAddNode->ListNode.Next   = LInfo;
  90
  91           LHead->NumList++;
  92      }
  93
  94      return( TRUE );
  95 }
  96
  97
  98
  99
 100 /*----------------------------------------------------------------------------
 101  *  RemHead:
 102  */
 103 PLISTINFO  RemHead(PLISTHEAD LHead)
 104 {
 105      PLISTINFO t, t1;
 106
 107      if ( LHead == NULL || EMPTYLIST(LHead) )
 108           return(NULL);
 109
 110      t = LHead->LHeaders[LISTHEAD];
 111      LHead->LHeaders[LISTHEAD] = (PLISTINFO) t->ListNode.Next;
 112
 113      if (LHead->LHeaders[LISTHEAD] != NULL)
 114      {
 115           t1 = (PLISTINFO) t->ListNode.Next;
 116           t1->ListNode.Previous = NULL;
 117      }
 118      else
 119           LHead->LHeaders[LISTTAIL] = NULL;
 120
 121      LHead->NumList--;
 122
 123      return(t);
 124 }
 125
 126 /*----------------------------------------------------------------------------
 127  *  RemTail:
 128  */
 129 PLISTINFO  RemTail(PLISTHEAD   LHead)
 130 {
 131      PLISTINFO   t, t1;
 132
 133      if ( LHead == NULL || EMPTYLIST(LHead) )
 134           return(NULL);
 135
 136      t = LHead->LHeaders[LISTTAIL];
 137      LHead->LHeaders[LISTTAIL] = (PLISTINFO) t->ListNode.Previous;
 138      if (LHead->LHeaders[LISTTAIL] != NULL)
 139      {
 140           t1 = (PLISTINFO) t->ListNode.Previous;
 141           t1->ListNode.Next = NULL;
 142      }
 143      else
 144           LHead->LHeaders[LISTHEAD] = NULL;
 145
 146      LHead->NumList--;
 147      return(t);
 148 }
 149
 150 /*----------------------------------------------------------------------------
 151  * PeekList:
 152  */
 153 PLISTINFO  PeekList(PLISTHEAD LHead, int wch, int index )
 154 {
 155      PLISTINFO  t;
 156
 157      if (LHead == NULL)
 158           return(NULL);
 159      if ( (t = LHead->LHeaders[wch]) == NULL )
 160           return(NULL);
 161
 162      for (; t != NULL && index > 0; index-- )
 163           t = (wch == LISTHEAD)  ? (PLISTINFO) t->ListNode.Next  :
 164                                    (PLISTINFO) t->ListNode.Previous;
 165      return(t);
 166 }
 167
 168
 169 /*----------------------------------------------------------------------------
 170  * RemoveList:
 171  */
 172 PLISTINFO   RemoveList( PLISTHEAD LHead, PLISTINFO LInfo )
 173 {
 174      PLISTINFO     t, t1;
 175
 176      t = LInfo;
 177      if (LHead == NULL)
 178           return(NULL);
 179      if (LHead->LHeaders[LISTHEAD] == t)
 180           t = (PLISTINFO) RemHead(LHead);
 181      else if (LHead->LHeaders[LISTTAIL] == t)
 182           t = (PLISTINFO) RemTail(LHead);
 183      else
 184      {
 185           t1                    = (PLISTINFO) t->ListNode.Previous;
 186           t1->ListNode.Next     = t->ListNode.Next;
 187           t1                    = (PLISTINFO) t->ListNode.Next;
 188           t1->ListNode.Previous = t->ListNode.Previous;
 189           LHead->NumList--;
 190      }
 191
 192      return(t);
 193 }
 194
 195 /*----------------------------------------------------------------------------
 196  * SearchList:
 197  *       Try to find a specific node in the queue whose key matches with
 198  *  searching key. Return the pointer to that node if found, return NULL
 199  *  otherwise
 200  *
 201  *  Input:
 202  *    lpHashTbl       => a far pointer to the hash table
 203  *    lpKey           => a far poniter to searching key
 204  *    CompareCallBack => comparision function
 205  *
 206  *  Output: a far pointer to the node to be found
 207  *
 208  */
 209 PLISTINFO  SearchList(
 210                         PLISTHEAD lpListHead,
 211                         PVOID lpSKey,
 212                         int (* CompareCallBack) ( PVOID, PVOID ) )
 213 {
 214 PLISTINFO lpListInfo;
 215
 216      lpListInfo = PeekList( lpListHead, LISTHEAD, 0);
 217      while ( lpListInfo != NULL )
 218      {
 219           if ( CompareCallBack( lpListInfo, lpSKey ) )
 220                break;
 221           lpListInfo = GetNextNode( lpListInfo );
 222      }
 223
 224      return( lpListInfo );
 225 }
 226