home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Kernel / MsgOps / keyedCode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-17  |  9.0 KB  |  256 lines
  1.  
  2. /* File: /u1/Eden/Kernel/MsgOps/KeyedCode.c */
  3.  
  4. /*
  5.  * $Header:   /u1/Eden/Kernel/MsgOps/RCS/KeyedCode.v  Revision 1.6  85/03/14 11:43:06  eric Exp$
  6.  * INTERFACE:    Defined by exported procedures.
  7.  *
  8.  * FUNCTION:    Message Module Keyed Queue Services.
  9.  *
  10.  * IMPORTS:    Eden/Source/MsgOps/Types.h,
  11.  *              /u1/Eden/ErrCodes/MMcodes.h,
  12.  *              /u1/Eden/Source/MsgOps/BufferTypes.h,
  13.  *              /u1/Eden/Source/MsgOps/FifoTypes.h.
  14.  *
  15.  * EXPORTS:    MMInitList, MMEnterInList, MMGetFromList,
  16.  *              MMFindInList.
  17.  *
  18.  * DESIGN:      Keyed queues are structured as hashed lists based
  19.  *              on a key supplied by the user of the queue.  The
  20.  *              has algorithm simply consists of taking the key
  21.  *              modulo the hash table size as an index into the
  22.  *              queue hash table.  Collisions are resolved by
  23.  *              constructing a linked list of entries in decreasing
  24.  *              order.  Duplicate key entries are not currently
  25.  *              allowed.
  26.  *
  27.  * $Log:    /u1/Eden/Source/MsgOps/RCS/KeyedCode.v $
  28.  * Revision 1.6  85/03/14  11:43:06  eric
  29.  * Minor changes to MXTraceMsg.
  30.  *
  31.  * Revision 1.5  83/03/19  11:43:06  cady
  32.  * Modified to allow NULL data and key pointer parameters.
  33.  * 
  34.  * Revision 1.4  83/02/25  12:16:06  cady
  35.  * Added new trace levels.
  36.  * 
  37.  * Revision 1.3  83/02/24  16:40:37  cady
  38.  * Replaced conditional debug trace with dynamic trace.
  39.  * Added conditional Kernel compilation.
  40.  * 
  41.  * Revision 1.2  83/02/22  12:06:23  cady
  42.  * Replaced #if Debug with #ifdef Debug.
  43.  * 
  44.  * Revision 1.1  83/01/06  14:09:20  cady
  45.  * Initial revision
  46.  * 
  47.  * 4-Nov-1982    Initial implementation. S. Cady
  48.  */
  49.  
  50. /****************************************************************/
  51. /*                                                              */
  52. /*               Message Module Keyed Queue Library             */
  53. /*                                                              */
  54. /****************************************************************/
  55.  
  56. #include "Kernel/h/mmTypes.h"
  57. #include "Kernel/h/mmCodes.h"
  58. #include "Kernel/h/mmBufTypes.h"
  59. #include "Kernel/h/mmKeyTypes.h"
  60.  
  61. /* Keyed Queue Hash Function */
  62.  
  63. #define mHashKey(fKey) (((int)(fKey)) % KEYEDSIZE)
  64.  
  65. /****************************************************************/
  66. /*                                                              */
  67. /*                       MMInitList                             */
  68. /*                                                              */
  69. /*   MMInitList defines the specified keyed queue to be empty.  */
  70. /*                                                              */
  71. /****************************************************************/
  72.  
  73. void  MMInitList( fList  /* Keyed Queue */
  74.                 )
  75.   KeyedQueue fList;
  76. {
  77.   register int i;
  78.  
  79.   MXTraceMsg(4, "MMInitList( %d )\n", fList);
  80.  
  81.   for ( i = 0; i < KEYEDSIZE; i++ )
  82.      fList[i] = NULL;
  83. }
  84.  
  85. /****************************************************************/
  86. /*                                                              */
  87. /*                          FindEntry                           */
  88. /*                                                              */
  89. /****************************************************************/
  90.  
  91. static KKStatus FindEntry( fList,   /* Keyed Queue     */
  92.                            fKey,    /* Search Key      */
  93.              /* returns */ fPrev,   /* Preceding Entry */
  94.              /* returns */ fEntry   /* Found Entry     */
  95.                          )
  96.            KeyedQueue         fList;
  97.   register UnsignedInteger    fKey;
  98.            KeyedEltPtr       *fPrev, *fEntry;
  99. {
  100.   register KeyedEltPtr prev;
  101.   register KeyedEltPtr next;
  102.  
  103.   prev = NULL;
  104.   next = fList[mHashKey(fKey)];
  105.   while ( next != NULL )
  106.     if ( next->KeyedKey < fKey )
  107.             break;
  108.     else if ( next->KeyedKey == fKey )
  109.           { *fPrev = prev;
  110.             *fEntry = next;
  111.             return MMSS_Success;
  112.           }
  113.     else  { prev = next;
  114.             next = next->KeyedNext;
  115.           };
  116.   /* end while */
  117.   *fPrev = prev;
  118.   *fEntry = next;
  119.   return MMSF_NoEntry;
  120. }
  121.  
  122. /****************************************************************/
  123. /*                                                              */
  124. /*                       MMEnterInList                          */
  125. /*                                                              */
  126. /*  MMEnterInList creates an entry containing the specified key */
  127. /*  and data and inserts it into the keyed list.                */
  128. /*                                                              */
  129. /*  Possible status codes:                                      */
  130. /*      MMSS_Success, MMSK_NoMem, MMSF_Dupl                     */
  131. /*                                                              */
  132. /****************************************************************/
  133.  
  134. KKStatus  MMEnterInList( fList,   /* Keyed Queue */
  135.                          fKey,    /* Search key  */
  136.                          fData1,  /* Entry data  */
  137.                          fData2
  138.                        )
  139.   KeyedQueue        fList;
  140.   UnsignedInteger   fKey;
  141.   integer           fData1, fData2;
  142. {
  143.   int         index;
  144.   KeyedEltPtr old;
  145.   KeyedEltPtr new;
  146.  
  147.  
  148.   MXTraceMsg(5, "MMEnterInList( %d, %d, %d, %d )\n", fList,
  149.                         fKey, fData1, fData2);
  150.  
  151.   if ( mSUCCESS(FindEntry( fList, fKey, &old, &new )) )
  152.     return MMSF_Dupl;
  153.   if ( ! mSUCCESS(MMAllocateData(sizeof(KeyedElt), (char **) &new)) )
  154.     return MMSK_NoMem;
  155.   new->KeyedKey = fKey;
  156.   new->KeyedData[0] = fData1;
  157.   new->KeyedData[1] = fData2;
  158.   if ( old == NULL )
  159.     { index = mHashKey(fKey);
  160.       new->KeyedNext = fList[index];
  161.       fList[index] = new;
  162.     }
  163.   else
  164.     { new->KeyedNext = old->KeyedNext;
  165.       old->KeyedNext = new;
  166.     };
  167.   return MMSS_Success;
  168. }
  169.  
  170. /****************************************************************/
  171. /*                                                              */
  172. /*                        MMGetFromList                         */
  173. /*                                                              */
  174. /*  MMGetFromList searches the queue for an entry with the      */
  175. /*  specified key.  If the key is found, the entry is removed   */
  176. /*  from the queue and the data is returned.  If the key is not */
  177. /*  found, an error status is returned.                         */
  178. /*                                                              */
  179. /*  Possible status codes:                                      */
  180. /*      MMSS_Success, MMSF_NoEntry                              */
  181. /*                                                              */
  182. /****************************************************************/
  183.  
  184. KKStatus  MMGetFromList( fList,   /* Keyed Queue */
  185.                          fKey,    /* Search key  */
  186.                          fData1,  /* Entry Data  */
  187.                          fData2
  188.                        )
  189.   KeyedQueue        fList;
  190.   UnsignedInteger   fKey;
  191.   integer          *fData1, *fData2;
  192. {
  193.   KeyedEltPtr prev, entry;
  194.  
  195.  
  196.     MXTraceMsg(5, "MMGetFromList( %d, %d )\n", fList, fKey);
  197.  
  198.   if ( ! mSUCCESS(FindEntry( fList, fKey, &prev, &entry )) )
  199.     return MMSF_NoEntry;
  200.   if ( prev == NULL )
  201.     fList[mHashKey(fKey)] = entry->KeyedNext;
  202.   else
  203.     prev->KeyedNext = entry->KeyedNext;
  204.   if ( fData1 != NULL )
  205.     *fData1 = entry->KeyedData[0];
  206.   if ( fData2 != NULL )
  207.     *fData2 = entry->KeyedData[1];
  208.   MMDeallocateData( sizeof(KeyedElt), (char *) entry );
  209.  
  210.   return MMSS_Success;
  211. }
  212.  
  213. /****************************************************************/
  214. /*                                                              */
  215. /*                      MMFindInList                            */
  216. /*                                                              */
  217. /*  MMFindInList searches the queue for an entry with the      */
  218. /*  specified key.  If the key is found, the entry data is      */
  219. /*  returned, but the entry is not removed from the queue.      */
  220. /*  If the key is not found, an error status is returned.       */
  221. /*                                                              */
  222. /*  Possible status codes:                                      */
  223. /*      MMSS_Success, MMSF_NoEntry                              */
  224. /*                                                              */
  225. /****************************************************************/
  226.  
  227. KKStatus  MMFindInList( fList,   /* Keyed Queue */
  228.                         fKey,    /* Search Key  */
  229.                         fData1,  /* Entry Data  */
  230.                         fData2
  231.                       )
  232.   KeyedQueue        fList;
  233.   UnsignedInteger   fKey;
  234.   integer          *fData1, *fData2;
  235. {
  236.   KeyedEltPtr prev, entry;
  237.  
  238.  
  239.     MXTraceMsg(5, "MMFindInList( %d, %d )\n", fList, fKey);
  240.  
  241.   if ( ! mSUCCESS(FindEntry( fList, fKey, &prev, &entry )) )
  242.     return MMSF_NoEntry;
  243.   if ( fData1 != NULL )
  244.     *fData1 = entry->KeyedData[0];
  245.   if ( fData2 != NULL )
  246.     *fData2 = entry->KeyedData[1];
  247.  
  248.  
  249.     MXTraceMsg(6, "Found: %d, %d\n", *fData1, *fData2);
  250.  
  251.   return MMSS_Success;
  252. }
  253. /****************************************************************/
  254. /* End of Message Module Keyed Queue Library                    */
  255. /****************************************************************/
  256.