Robust/src/Benchmarks/SingleTM/Intruder/List_t.java

   1 /* =============================================================================
   2  *
   3  * List_t.java
   4  * -- Sorted singly linked list
   5  * -- Options: duplicate allowed
   6  *    (DLIST_NO_DUPLICATES) is no implemented yet (default: allow duplicates)
   7  *
   8  * =============================================================================
   9  *
  10  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
  11  * Author: Chi Cao Minh
  12  *
  13  * =============================================================================
  14  *
  15  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  16  * of the files.
  17  *
  18  * ------------------------------------------------------------------------
  19  *
  20  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  21  *
  22  * ------------------------------------------------------------------------
  23  *
  24  * For the license of ssca2, please see ssca2/COPYRIGHT
  25  *
  26  * ------------------------------------------------------------------------
  27  *
  28  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  29  * header of the files.
  30  *
  31  * ------------------------------------------------------------------------
  32  *
  33  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  34  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  35  *
  36  * ------------------------------------------------------------------------
  37  *
  38  * Unless otherwise noted, the following license applies to STAMP files:
  39  *
  40  * Copyright (c) 2007, Stanford University
  41  * All rights reserved.
  42  *
  43  * Redistribution and use in source and binary forms, with or without
  44  * modification, are permitted provided that the following conditions are
  45  * met:
  46  *
  47  *     * Redistributions of source code must retain the above copyright
  48  *       notice, this list of conditions and the following disclaimer.
  49  *
  50  *     * Redistributions in binary form must reproduce the above copyright
  51  *       notice, this list of conditions and the following disclaimer in
  52  *       the documentation and/or other materials provided with the
  53  *       distribution.
  54  *
  55  *     * Neither the name of Stanford University nor the names of its
  56  *       contributors may be used to endorse or promote products derived
  57  *       from this software without specific prior written permission.
  58  *
  59  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  60  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  62  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  64  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  65  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  66  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  67  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  68  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  69  * THE POSSIBILITY OF SUCH DAMAGE.
  70  *
  71  * =============================================================================
  72  */
  73
  74
  75 public class List_t {
  76
  77     List_Node head;
  78     int chk;
  79     int size;
  80
  81     public List_t() {
  82         head = new List_Node();
  83     }
  84
  85
  86     /* =======================================================================
  87      * allocNode
  88      * -- Returns null on failure
  89      * =======================================================================
  90      */
  91     private List_Node allocNode(Object dataPtr)
  92     {
  93         List_Node nodePtr = new List_Node();
  94         nodePtr.dataPtr = dataPtr;
  95         return nodePtr;
  96     }
  97
  98
  99 /* =============================================================================
 100  * list_alloc
 101  * -- If NULL passed for 'compare' function, will compare data pointer addresses
 102  * -- Returns NULL on failure
 103  * =============================================================================
 104  * list_t* list_alloc (long (*compare)(const void*, const void*));
 105  *
 106  *
 107  */
 108
 109   public List_t(int chk) {
 110     this.head = new List_Node();
 111     this.chk=chk;
 112   }
 113
 114 /* =============================================================================
 115  * list_free
 116  * -- If NULL passed for 'compare' function, will compare data pointer addresses
 117  * -- Returns NULL on failure
 118  * =============================================================================
 119  * void list_free (list_t* listPtr);
 120  */
 121
 122 /* =============================================================================
 123  * list_isEmpty
 124  * -- Return TRUE if list is empty, else FALSE
 125  * =============================================================================
 126  * bool_t list_isEmpty (list_t* listPtr);
 127  */
 128     public boolean isEmpty()
 129     {
 130         return (head.nextPtr == null);
 131     }
 132
 133 /* =============================================================================
 134  * list_getSize
 135  * -- Returns size of list
 136  * =============================================================================
 137  * long list_getSize (list_t* listPtr);
 138  */
 139     public int getSize() {
 140         return size;
 141     }
 142
 143 /* =============================================================================
 144  * findPrevious
 145  * =============================================================================
 146  * void* list_find (list_t* listPtr, void* dataPtr);
 147  */
 148     private List_Node findPrevious(Object dataPtr)
 149     {
 150         List_Node prevPtr = head;
 151         List_Node nodePtr = prevPtr.nextPtr;
 152
 153         for(; nodePtr != null; nodePtr = nodePtr.nextPtr) {
 154             if (compare(nodePtr.dataPtr,dataPtr) >= 0) {
 155                 return prevPtr;
 156             }
 157             prevPtr = nodePtr;
 158         }
 159
 160         return prevPtr;
 161     }
 162
 163     /* =============================================================================
 164      * list_find
 165      * -- Returns NULL if not found, else returns pointer to data
 166      * =============================================================================
 167      * void* list_find (list_t* listPtr, void* dataPtr);
 168      */
 169     public Object find(Object dataPtr) {
 170         List_Node nodePtr;
 171         List_Node prevPtr = findPrevious(dataPtr);
 172
 173         nodePtr = prevPtr.nextPtr;
 174
 175         if((nodePtr == null) ||
 176                 (compare(nodePtr.dataPtr,dataPtr) != 0)) {
 177             return null;
 178         }
 179
 180         return (nodePtr.dataPtr);
 181     }
 182
 183     public int compare(Object obj1,Object obj2)
 184     {
 185         if(chk == 1)
 186         {
 187             return Packet.compareFragmentID((Packet)obj1,(Packet)obj2);
 188         }
 189         else
 190             return compareObject(obj1,obj2);
 191     }
 192
 193 /* =============================================================================
 194  * list_insert
 195  * -- Return TRUE on success, else FALSE
 196  * =============================================================================
 197  * bool_t list_insert (list_t* listPtr, void* dataPtr);
 198  */
 199     public boolean insert(Object dataPtr) {
 200         List_Node prevPtr;
 201         List_Node nodePtr;
 202         List_Node currPtr;
 203
 204         prevPtr = findPrevious(dataPtr);
 205         currPtr = prevPtr.nextPtr;
 206
 207         nodePtr = allocNode(dataPtr);
 208         if (nodePtr == null) {
 209             return false;
 210         }
 211
 212         nodePtr.nextPtr = currPtr;
 213         prevPtr.nextPtr = nodePtr;
 214         size++;
 215
 216         return true;
 217     }
 218
 219
 220 /* =============================================================================
 221  * list_remove
 222  * -- Returns TRUE if successful, else FALSE
 223  * =============================================================================
 224  * bool_t list_remove (list_t* listPtr, void* dataPtr);
 225  */
 226     public boolean remove(Object dataPtr)
 227     {
 228         List_Node prevPtr;
 229         List_Node nodePtr;
 230
 231         prevPtr = findPrevious(dataPtr);
 232
 233         nodePtr = prevPtr.nextPtr;
 234
 235         if((nodePtr != null) &&
 236             (compare(nodePtr.dataPtr,dataPtr) == 0))
 237         {
 238             prevPtr.nextPtr = nodePtr.nextPtr;
 239             nodePtr.nextPtr = null;
 240             nodePtr = null;
 241             size--;
 242
 243             return true;
 244         }
 245
 246         return false;
 247     }
 248
 249     int compareObject(Object obj1,Object obj2) {
 250         return 1;
 251     }
 252
 253
 254 /* =============================================================================
 255  * list_clear
 256  * -- Removes all elements
 257  * =============================================================================
 258  * void list_clear (list_t* listPtr);
 259  */
 260     public void clear() {
 261         head = new List_Node();
 262         size = 0;
 263     }
 264
 265 /* =============================================================================
 266  *
 267  * End of list.java
 268  *
 269  * =============================================================================
 270  */
 271
 272
 273
 274 }