1    /*
     2     * Copyright (c) 2013-2015, Texas Instruments Incorporated
     3     * All rights reserved.
     4     *
     5     * Redistribution and use in source and binary forms, with or without
     6     * modification, are permitted provided that the following conditions
     7     * are met:
     8     *
     9     * *  Redistributions of source code must retain the above copyright
    10     *    notice, this list of conditions and the following disclaimer.
    11     *
    12     * *  Redistributions in binary form must reproduce the above copyright
    13     *    notice, this list of conditions and the following disclaimer in the
    14     *    documentation and/or other materials provided with the distribution.
    15     *
    16     * *  Neither the name of Texas Instruments Incorporated nor the names of
    17     *    its contributors may be used to endorse or promote products derived
    18     *    from this software without specific prior written permission.
    19     *
    20     * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    21     * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
    22     * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    23     * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
    24     * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    25     * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    26     * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
    27     * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
    28     * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
    29     * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
    30     * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    31     */
    32    /*
    33     *  ======== Queue.xdc ========
    34     *
    35     */
    36    package ti.sysbios.knl;
    37    
    38    import xdc.rov.ViewInfo;
    39    
    40    /*!
    41     *  ======== Queue ========
    42     *  Queue manager.
    43     *
    44     *  The Queue module makes available a set of functions that manipulate
    45     *  queue objects accessed through handles of type Queue_Handle.
    46     *  Each queue contains a linked sequence of zero or more elements
    47     *  referenced through variables of type Queue_Elem, which are
    48     *  embedded as the first field within a structure.
    49     *
    50     *  In the Queue API descriptions, the APIs which disable interrupts before 
    51     *  modifying the Queue are noted as "atomic", while APIs that do not disable
    52     *  interrupts are "non-atomic".
    53     *
    54     *  Queues are represented as doubly-linked lists, so calls to Queue_next 
    55     *  or Queue_prev can loop continuously over the Queue. The following code
    56     *  demonstrates one way to iterate over a Queue once from beginning to end.
    57     *  In this example, 'myQ' is a Queue_Handle. 
    58     *  
    59     *  @p(code)
    60     *  Queue_Elem *elem;
    61     *
    62     *  for (elem = Queue_head(myQ); 
    63     *      elem != (Queue_Elem *)myQ; 
    64     *      elem = Queue_next(elem)) {
    65     *      ...
    66     *  }
    67     *  @p
    68     * 
    69     *  Below is a simple example of how to create a Queue, enqueue two elements,
    70     *  and dequeue the elements until the queue is empty:
    71     *
    72     *  @p(code)
    73     *  #include <xdc/std.h>
    74     *  #include <xdc/runtime/System.h>
    75     *  
    76     *  #include <ti/sysbios/knl/Queue.h>
    77     *  
    78     *  typedef struct Rec {
    79     *      Queue_Elem _elem;
    80     *      Int data;
    81     *  } Rec;
    82     *  
    83     *  Int main(Int argc, Char *argv[])
    84     *  {
    85     *      Queue_Handle q;
    86     *      Rec r1, r2;
    87     *      Rec* rp;
    88     *  
    89     *      r1.data = 100;
    90     *      r2.data = 200;
    91     *  
    92     *  
    93     *      // create a Queue instance 'q'
    94     *      q = Queue_create(NULL, NULL);
    95     *  
    96     *  
    97     *      // enQ a couple of records
    98     *      Queue_enqueue(q, &r1._elem);
    99     *      Queue_enqueue(q, &r2._elem);
   100     *  
   101     *  
   102     *      // deQ the records and print their data values until Q is empty
   103     *      while (!Queue_empty(q)) {
   104     *          rp = Queue_dequeue(q);
   105     *          System_printf("rec: %d\n", rp->data);
   106     *      }
   107     *  
   108     *      System_exit(0);
   109     *      return (0);
   110     *  }
   111     *  @p
   112     *
   113     *
   114     *
   115     *  Unconstrained Functions
   116     *  All functions are unconstrained
   117     *
   118     *  @p(html)
   119     *  <h3> Calling Context </h3>
   120     *  <table border="1" cellpadding="3">
   121     *    <colgroup span="1"></colgroup> <colgroup span="5" align="center">
   122     *    </colgroup>
   123     *
   124     *    <tr><th> Function                 </th><th>  Hwi   </th><th>  Swi   </th>
   125     *    <th>  Task  </th><th>  Main  </th><th>  Startup  </th></tr>
   126     *    <!--                                                        -->
   127     *    <tr><td> {@link #create}          </td><td>   N    </td><td>   N    </td>
   128     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   129     *    <tr><td> {@link #insert}          </td><td>   Y    </td><td>   Y    </td>
   130     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   131     *    <tr><td> {@link #next}            </td><td>   Y    </td><td>   Y    </td>
   132     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   133     *    <tr><td> {@link #Params_init}     </td><td>   Y    </td><td>   Y    </td>
   134     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   135     *    <tr><td> {@link #prev}            </td><td>   Y    </td><td>   Y    </td>
   136     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   137     *    <tr><td> {@link #remove}          </td><td>   Y    </td><td>   Y    </td>
   138     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   139     *    <tr><td> {@link #construct}       </td><td>   Y    </td><td>   Y    </td>
   140     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   141     *    <tr><td> {@link #delete}          </td><td>   N    </td><td>   N    </td>
   142     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   143     *    <tr><td> {@link #dequeue}         </td><td>   Y    </td><td>   Y    </td>
   144     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   145     *    <tr><td> {@link #destruct}        </td><td>   Y    </td><td>   Y    </td>
   146     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   147     *    <tr><td> {@link #empty}           </td><td>   Y    </td><td>   Y    </td>
   148     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   149     *    <tr><td> {@link #enqueue}         </td><td>   Y    </td><td>   Y    </td>
   150     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   151     *    <tr><td> {@link #get}                     </td><td>   Y    </td><td>   Y    </td>
   152     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   153     *    <tr><td> {@link #head}            </td><td>   Y    </td><td>   Y    </td>
   154     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   155     *    <tr><td> {@link #put}                     </td><td>   Y    </td><td>   Y    </td>
   156     *    <td>   Y    </td><td>   Y    </td><td>   N    </td></tr>
   157     *    <tr><td colspan="6"> Definitions: <br />
   158     *       <ul>
   159     *         <li> <b>Hwi</b>: API is callable from a Hwi thread. </li>
   160     *         <li> <b>Swi</b>: API is callable from a Swi thread. </li>
   161     *         <li> <b>Task</b>: API is callable from a Task thread. </li>
   162     *         <li> <b>Main</b>: API is callable during any of these phases: </li>
   163     *           <ul>
   164     *             <li> In your module startup after this module is started 
   165     *    (e.g. Queue_Module_startupDone() returns TRUE). </li>
   166     *             <li> During xdc.runtime.Startup.lastFxns. </li>
   167     *             <li> During main().</li>
   168     *             <li> During BIOS.startupFxns.</li>
   169     *           </ul>
   170     *         <li> <b>Startup</b>: API is callable during any of these phases:</li>
   171     *           <ul>
   172     *             <li> During xdc.runtime.Startup.firstFxns.</li>
   173     *             <li> In your module startup before this module is started 
   174     *    (e.g. Queue_Module_startupDone() returns FALSE).</li>
   175     *           </ul>
   176     *       </ul>
   177     *    </td></tr>
   178     *
   179     *  </table>
   180     *  @p
   181     */
   182    
   183    @DirectCall
   184    @InstanceInitStatic /* Construct/Destruct CAN be called at runtime */
   185    module Queue
   186    {
   187    
   188        /*!
   189         *  ======== BasicView ========
   190         *  @_nodoc
   191         */
   192        metaonly struct BasicView {
   193            String  label;
   194            Ptr     elems[];
   195        }
   196        
   197        /*!
   198         *  ======== rovViewInfo ========
   199         *  @_nodoc
   200         */
   201        @Facet
   202        metaonly config ViewInfo.Instance rovViewInfo = 
   203            ViewInfo.create({
   204                viewMap: [
   205                    ['Basic', {type: ViewInfo.INSTANCE, viewInitFxn: 'viewInitInstance', structName: 'BasicView'}]
   206                ]
   207            });
   208        
   209        /*!
   210         *  ======== Elem ========
   211         *  Opaque queue element.
   212         *
   213         *  A field of this type is placed at the head of client structs.
   214         */
   215        struct Elem {
   216            Elem *volatile next;
   217            Elem *volatile prev;
   218        };
   219    
   220        /*!
   221         *  @_nodoc
   222         *  ======== elemClear ========
   223         *  Clears a Queue element's pointers so that if isQueued() is called on
   224         *  the element it will return FALSE. When a Queue element is dequeued or
   225         *  removed from a Queue, this API must be called on the element for 
   226         *  isQueued() to return FALSE.     
   227         *
   228         *  To be clear, this API is not for removing elements from a queue, and
   229         *  should never be called on an element in a queue--only on dequeued 
   230         *  elements.
   231         *
   232         *  @param(qelem)           element to be cleared
   233         */
   234        Void elemClear(Elem *qelem); 
   235    
   236        /*!
   237         *  ======== elemClearMeta ========
   238         *  @_nodoc
   239         *  Clears a Queue element's pointers so that if isQueued() is called on
   240         *  the element it will return FALSE. When a Queue element is dequeued or
   241         *  removed from a Queue, this API must be called on the element for 
   242         *  isQueued() to return FALSE.     
   243         *
   244         *  To be clear, this API is not for removing elements from a queue, and
   245         *  should never be called on an element in a queue--only on dequeued 
   246         *  elements.
   247         *
   248         *  @param(qelem)           element to be cleared
   249         */
   250        metaonly Void elemClearMeta(Elem *qelem); 
   251    
   252        /*!
   253         *  ======== insert ========
   254         *  Insert `elem` in the queue in front of `qelem`.
   255         *
   256         *  @param(qelem)           element already in queue
   257         *
   258         *  @param(elem)            element to be inserted in queue
   259         */
   260        Void insert(Elem *qelem, Elem *elem); 
   261    
   262        /*!
   263         *  ======== insertMeta ========
   264         *  @_nodoc
   265         *  Insert `elem` in the queue in front of `qelem`.
   266         *
   267         *  @param(qelem)           element already in queue
   268         *
   269         *  @param(elem)            element to be inserted in queue
   270         */
   271        metaonly Void insertMeta(Elem *qelem, Elem *elem); 
   272    
   273        /*!
   274         *  ======== next ========
   275         *  Return next element in queue (non-atomically).
   276         *
   277         *  This function returns a pointer to an Elem object in the queue 
   278         *  after `qelem`. A Queue is represented internally as a doubly-linked
   279         *  list, so 'next' can be called in a continuous loop over the queue.
   280         *  See the module description for an example of iterating once over a
   281         *  Queue.
   282         *
   283         *  @param(qelem)           element in queue
   284         *
   285         *  @b(returns)             next element in queue
   286         */
   287        Ptr next(Elem *qelem);
   288    
   289        /*!
   290         *  ======== prev ========
   291         *  Return previous element in queue (non-atomically).
   292         *
   293         *  This function returns a pointer to an Elem object in the queue 
   294         *  before `qelem`. A Queue is represented internally as a doubly-linked
   295         *  list, so 'prev' can be called in a continuous loop over the queue.
   296         *  See the module description for an example of iterating once over a
   297         *  Queue.
   298         *
   299         *  @param(qelem)           element in queue
   300         *
   301         *  @b(returns)             previous element in queue
   302         */
   303        Ptr prev(Elem *qelem);
   304    
   305        /*!
   306         *  ======== remove ========
   307         *  Remove qelem from middle of queue (non-atomically).
   308         *
   309         *  The `qelem` parameter is a pointer to an existing element to be removed
   310         *  from the Queue.
   311         *
   312         *  @param(qelem)           element in queue
   313         */
   314        Void remove (Elem *qelem);
   315    
   316        /*!
   317         *  @_nodoc
   318         *  ======== isQueued ========
   319         *  Check if the elem is on any queue. 
   320         *  
   321         *  In order for this API to return false on an element that has been
   322         *  dequeued or removed from a Queue, elemClear must have been called on
   323         *  the element.
   324         *
   325         *  @param(qelem)           element in queue
   326         */
   327        Bool isQueued (Elem *qelem);
   328    
   329    instance:
   330    
   331        /*!
   332         *  @_nodoc
   333         *  Added to get the Grace instance view to work.
   334         */
   335        metaonly config UInt dummy = 0;
   336    
   337        /*!
   338         *  ======== create ========
   339         *  Create a Queue object
   340         */
   341        create();
   342    
   343        /*!
   344         *  ======== dequeue ========
   345         *  Remove the element from the front of queue and return elem.  If the
   346         *  queue is empty, the return value of Queue_dequeue() will be non-NULL,
   347         *  due to the Queue implementation.  Use Queue_empty() to determine
   348         *  whether or not the Queue is empty before calling Queue_dequeue().
   349         *
   350         *  @b(returns)             pointer to former first element
   351         */
   352        Ptr dequeue();
   353    
   354        /*!
   355         *  ======== empty ========
   356         *  Test for an empty queue.
   357         *
   358         *  @b(returns)             TRUE if this queue is empty
   359         */
   360        Bool empty();
   361    
   362        /*!
   363         *  ======== enqueue ========
   364         *  Insert at end of queue (non-atomically).
   365         *
   366         *  @param(elem)            pointer to an element
   367         */
   368        Void enqueue(Elem *elem);
   369    
   370        /*!
   371         *  ======== get ========
   372         *  Get element from front of queue (atomically).
   373         *
   374         *  This function removes the element from the front of queue and returns
   375         *  a pointer to it.  If the queue is empty, the return value of
   376         *  Queue_get() will be non-NULL, due to the Queue implementation.
   377         *  Use Queue_empty() to determine whether or not the Queue is empty before
   378         *  calling Queue_get().
   379         *
   380         *  @b(returns)             pointer to former first element
   381         */
   382        Ptr get();
   383    
   384        /*!
   385         *  ======== getTail ========
   386         *  Get the element at the end of the queue (atomically).
   387         *
   388         *  This function removes the element at the end of queue and returns
   389         *  a pointer to it.  If the queue is empty, the return value of
   390         *  Queue_getTail() will be non-NULL, due to the Queue implementation.
   391         *  Use Queue_empty() to determine whether or not the Queue is empty before
   392         *  calling Queue_getTail().
   393         *
   394         *  @b(returns)             pointer to former end element
   395         */
   396        Ptr getTail();
   397    
   398        /*!
   399         *  ======== head ========
   400         *  Return element at front of queue.
   401         *
   402         *  This function returns a pointer to the element at the front of queue.
   403         *  The element is not removed from the queue.
   404         *  Due to the Queue implementation, the return value will be non-NULL
   405         *  if the Queue is empty.  Use Queue_empty() to determine whether or
   406         *  not the Queue is empty before calling Queue_head().
   407         *
   408         *  @b(returns)             pointer to first element
   409         */
   410        Ptr head();
   411    
   412        /*!
   413         *  ======== headMeta ========
   414         *  @_nodoc
   415         *  Return element at front of queue. Returns null if queue is empty.
   416         *
   417         *  This function returns a pointer to the element at the front of queue.
   418         *  The element is not removed from the queue.
   419         *
   420         *  @b(returns)             pointer to first element
   421         */
   422        metaonly Ptr headMeta();
   423    
   424        /*!
   425         *  ======== put ========
   426         *  Put element at end of queue (atomically).
   427         *
   428         *  @param(elem)            pointer to new queue element
   429         */
   430        Void put(Elem *elem);
   431        
   432        /*!
   433         *  ======== putMeta ========
   434         *  @_nodoc
   435         *  Put element at end of queue.
   436         *
   437         *  @param(elem)            pointer to new queue element
   438         */
   439        metaonly Void putMeta(Elem* elem);
   440    
   441        /*!
   442         *  ======== putHead ========
   443         *  Put element at the front of the queue (atomically).
   444         *
   445         *  @param(elem)            pointer to new queue element
   446         */
   447        Void putHead(Elem *elem);
   448    
   449        /*!
   450         *  ======== nextMeta ========
   451         *  @_nodoc
   452         *  Return next element in queue. Returns null if end of queue.
   453         *
   454         *  This function returns a pointer to an Elem object in the queue 
   455         *  after `qelem`.
   456         *
   457         *  @param(qelem)           element in queue
   458         *
   459         *  @b(returns)             next element in queue
   460         */
   461        metaonly Ptr nextMeta(Elem *qelem);
   462    
   463    internal:   // not for client use
   464    
   465        // instance object
   466        struct Instance_State {
   467                Elem elem;
   468        };
   469    }