1    /* --COPYRIGHT--,TI
     2     * Copyright (c) $(CPYYEAR)
     3     * Texas Instruments
     4     *
     5     *  All rights reserved.  Property of Texas Instruments
     6     *  Restricted rights to use, duplicate or disclose this code are
     7     *  granted through contract.
     8     * 
     9     * --/COPYRIGHT--*/
    10    /*
    11     *  ======== List.xdc ========
    12     *
    13     *! Revision History
    14     *! ================
    15     *! 07-Aug-2009 toddm   Added enqueue and dequeue
    16     *! 16-Apr-2009 toddm   Code review comments
    17     *! 02-May-2008 nitya   created
    18     */
    19    
    20    import xdc.rov.ViewInfo;
    21    
    22    /*!
    23     *  ======== List ========
    24     *  Doubly Linked List Manager
    25     *
    26     *  The List module makes available a set of functions that manipulate
    27     *  List objects accessed through handles of type List_Handle.
    28     *  Each List contains a linked sequence of zero or more elements
    29     *  referenced through variables of type List_Elem, which are typically
    30     *  embedded as the first field within a structure.
    31     *
    32     *  All List function are atomic unless noted otherwise in the API
    33     *  descriptions. An atomic API means that the API completes in core 
    34     *  functionality without being interrupted. Therefore, atomic APIs are
    35     *  thread-safe. An example is {@link #put}. Multiple threads can call
    36     *  {@link #put} at the same time. The threads do not have to manage the
    37     *  synchronization.
    38     *
    39     *  The {@link xdc.runtime.Gate#enterSystem}/{@link xdc.runtime.Gate#leaveSystem}
    40     *  calls are used to make the APIs atomic. This Gate calls internally use 
    41     *  {@link xdc.runtime.System}'s gate.
    42     *
    43     *  The List module can be used both as a queue (i.e. First In First Out),
    44     *  as a stack (i.e. Last In First Out), or as a general purpose linked list.
    45     *
    46     *  Lists are represented as doubly-linked lists, so calls to {@link #next}
    47     *  or {@link #prev} can loop continuously over the List. 
    48     *  Refer to {@link #next} and {@link #prev} for examples.
    49     *
    50     *  @a(List as a Queue)
    51     *
    52     *  To treat the list object as a queue:
    53     *  @p(blist)
    54     *  -Use {@link #put} to put at the tail of the queue
    55     *  -Use {@link #get} to get from the head of the queue
    56     *  @p
    57     *
    58     *  Here is sample code that acts on a List instance (listHandle) as a queue
    59     *  in a FIFO manner.
    60     *
    61     *  @p(code)
    62     *  List_Elem  elem[4];
    63     *  List_Elem *tmpElem;
    64     *
    65     *  // place at the tail of the queue
    66     *  for (i = 0; i < 4; i++) {
    67     *      List_put(listHandle, &(elem[i]));  
    68     *  }
    69     *
    70     *  // remove the buffers from the head
    71     *  while((tmpElem = List_get(listHandle)) != NULL) {
    72     *      // process tmpElem
    73     *  }
    74     *  @p
    75     *
    76     *  @a(List as a Stack)
    77     *
    78     *  To treat the list object as a stack:
    79     *  @p(blist)
    80     *  -Use {@link #putHead} to put at the top of the stack
    81     *  -Use {@link #get} to get from the top of the stack
    82     *  @p
    83     *
    84     *  Here is sample code that acts on a List instance (listHandle) as a stack
    85     *  in a LIFO manner.
    86     *
    87     *  @p(code)
    88     *  List_Elem  elem[4];
    89     *  List_Elem *tmpElem;
    90     *
    91     *  // push onto the top (i.e. head)
    92     *  for (i = 0; i < 4; i++) {
    93     *      List_putHead(listHandle, &(elem[i]));
    94     *  }
    95     *
    96     *  // remove the buffers in FIFO order.
    97     *  while((tmpElem = List_get(listHandle)) != NULL) {
    98     *      // process tmpElem
    99     *  }
   100     *  @p
   101     */
   102    
   103    module List
   104    {
   105        metaonly struct BasicView {
   106            String  label;
   107            Ptr     elems[];
   108        }
   109    
   110        @Facet
   111        metaonly config ViewInfo.Instance rovViewInfo = 
   112            ViewInfo.create({
   113                viewMap: [
   114                    ['Basic', {type: ViewInfo.INSTANCE, viewInitFxn: 'viewInitInstance', structName: 'BasicView'}]
   115                ]
   116            });
   117    
   118        /*!
   119         *  ======== Elem ========
   120         *  Opaque List element
   121         *
   122         *  A field of this type is placed at the head of client structs.
   123         */
   124        @Opaque struct Elem {
   125            Elem *volatile next;    /* must be volatile for whole_program */
   126            Elem *volatile prev;    /* must be volatile for whole_program */
   127        };
   128        
   129        /*!
   130         *  ======== elemClearMeta ========
   131         *  Clears a List element's pointers
   132         *
   133         *  This API is not for removing elements from a List, and
   134         *  should never be called on an element in a List--only on deListed
   135         *  elements.
   136         *
   137         *  @param(elem)            element to be cleared
   138         */
   139        metaonly Void elemClearMeta(Elem *elem);
   140        
   141        /*!
   142         *  ======== elemClear ========
   143         *  Clears a List element's pointers
   144         *
   145         *  This API does not removing elements from a List, and
   146         *  should never be called on an element in a List--only on deListed
   147         *  elements.
   148         *
   149         *  @param(elem)            element to be cleared
   150         */
   151        Void elemClear(Elem *elem);
   152    
   153    instance:
   154    
   155        /*!
   156         *  ======== metaList ========
   157         *  @_nodoc
   158         *  Used to store elem before the object is initialized.
   159         */
   160        metaonly config any metaList[];
   161    
   162        /*!
   163         *  ======== create ========
   164         *  Create a List object
   165         */
   166        create();
   167    
   168        /*!
   169         *  ======== empty ========
   170         *  Test for an empty List (atomic)
   171         *
   172         *  @b(returns)     TRUE if this List is empty
   173         */
   174        Bool empty();
   175    
   176        /*!
   177         *  ======== get ========
   178         *  Get element from front of List (atomic)
   179         *
   180         *  This function atomically removes the element from the front of a
   181         *  List and returns a pointer to it.
   182         *
   183         *  @b(returns)     pointer to former first element or NULL if empty
   184         */
   185        Ptr get();
   186    
   187        /*!
   188         *  ======== put ========
   189         *  Put element at end of List (atomic)
   190         *
   191         *  This function atomically places the element at the end of 
   192         *  List.     
   193         *
   194         *  @param(elem)    pointer to new List element
   195         */
   196        Void put(Elem *elem);
   197        
   198        /*!
   199         *  ======== putHead ========
   200         *  Put element at head of List (atomic)
   201         *
   202         *  This function atomically places the element at the front of 
   203         *  List.     
   204         *
   205         *  @param(elem)    pointer to new List element
   206         */
   207        Void putHead(Elem *elem);
   208    
   209        /*!
   210         *  ======== putMeta ========
   211         *  @_nodoc
   212         *  Put element at end of List.
   213         *
   214         *  This meta function can be used to place an element onto
   215         *  the end of a list during configuration. There currently 
   216         *  is no meta API to place the elem at the head of the list
   217         *  during configuration.
   218         *
   219         *  @param(elem)            pointer to new List element
   220         */
   221        metaonly Void putMeta(Elem* elem);
   222    
   223        /*!
   224         *  ======== next ========
   225         *  Return next element in List (non-atomic)
   226         *
   227         *  This function returns the next element on a list. It does not
   228         *  remove any items from the list. The caller should protect the 
   229         *  list from being changed while using this call since it is non-atomic.
   230         *
   231         *  To look at the first elem on the list, use NULL as the elem argument. 
   232         *
   233         *  This function is useful in searching a list. The following code shows
   234         *  an example. The scanning of a list should be protected against other
   235         *  threads that modify the list.
   236         *
   237         *  @p(code)
   238         *  List_Elem  *elem = NULL;
   239         *
   240         *  // Begin protection against modification of the list.
   241         *
   242         *  while ((elem = List_next(listHandle, elem)) != NULL) {
   243         *      //act elem as needed. For example call List_remove().
   244         *  }
   245         *
   246         *  // End protection against modification of the list.
   247         *  @p
   248         *
   249         *  @param(elem)    element in list or NULL to start at the head
   250         *
   251         *  @b(returns)     next element in list or NULL to denote end
   252         */
   253        Ptr next(Elem *elem);
   254    
   255        /*!
   256         *  ======== prev ========
   257         *  Return previous element in List (non-atomic)
   258         *
   259         *  This function returns the previous element on a list. It does not
   260         *  remove any items from the list. The caller should protect the 
   261         *  list from being changed while using this call since it is non-atomic.
   262         *
   263         *  To look at the last elem on the list, use NULL as the elem argument. 
   264         *
   265         *  This function is useful in searching a list in reverse order. The 
   266         *  following code shows an example. The scanning of a list should be 
   267         *  protected against other threads that modify the list.
   268         *
   269         *  @p(code)
   270         *  List_Elem  *elem = NULL;
   271         *
   272         *  // Begin protection against modification of the list.
   273         *
   274         *  while ((elem = List_prev(listHandle, elem)) != NULL) {
   275         *      //act elem as needed. For example call List_remove().
   276         *  }
   277         *
   278         *  // End protection against modification of the list.
   279         *  @p
   280         *
   281         *  @param(elem)    element in list or NULL to start at the end (i.e. tail)
   282         *
   283         *  @b(returns)     previous element in list or NULL to denote 
   284         *                  no previous elem
   285         */
   286        Ptr prev(Elem *elem);
   287    
   288        /*!
   289         *  ======== insert ========
   290         *  Insert element at into a List (non-atomic)
   291         *
   292         *  This function inserts `newElem` in the queue in 
   293         *  front of `curElem`. The caller should protect the 
   294         *  list from being changed while using this call since it is non-atomic.
   295         *
   296         *  To place an elem at the end of the list, use {@link #put}.
   297         *  To place a elem at the front of the list, use {@link #putHead}.
   298         *
   299         *  @param(newElem)         element to insert
   300         *
   301         *  @param(curElem)         element to insert in front of
   302         */
   303        Void insert(Elem *newElem, Elem *curElem);
   304    
   305        /*!
   306         *  ======== remove ========
   307         *  Remove elem from middle of list (non-atomic)
   308         *
   309         *  This function removes an elem from a list.
   310         *  The `elem` parameter is a pointer to an existing element to be removed
   311         *  from the List.  The caller should protect the 
   312         *  list from being changed while using this call since it is non-atomic.
   313         *
   314         *  @param(elem)            element in list
   315         */
   316        Void remove(Elem *elem);
   317        
   318        /*!
   319         *  ======== dequeue ========
   320         *  Get element from front of List (non-atomic)
   321         *
   322         *  This function atomically removes the element from the front of a
   323         *  List and returns a pointer to it.
   324         *
   325         *  @b(returns)     pointer to former first element or NULL if empty
   326         */
   327        Ptr dequeue();
   328    
   329        /*!
   330         *  ======== enqueue ========
   331         *  Put element at end of List (non-atomic)
   332         *
   333         *  This function atomically places the element at the end of 
   334         *  List.     
   335         *
   336         *  @param(elem)    pointer to new List element
   337         */
   338        Void enqueue(Elem *elem);
   339        
   340        /*!
   341         *  ======== enqueueHead ========
   342         *  Put element at head of List (non-atomic)
   343         *
   344         *  This function atomically places the element at the front of 
   345         *  List.     
   346         *
   347         *  @param(elem)    pointer to new List element
   348         */
   349        Void enqueueHead(Elem *elem);
   350    
   351    internal:   
   352    
   353        /* instance object */
   354        struct Instance_State {
   355            Elem elem;
   356        };
   357    }