Robust/src/Benchmarks/SingleTM/Yada/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     public List_Node head;
  78     int size;
  79
  80     public List_t() {
  81         head = new List_Node();
  82     }
  83
  84
  85     /* =======================================================================
  86      * allocNode
  87      * -- Returns null on failure
  88      * =======================================================================
  89      */
  90     private List_Node allocNode(Object dataPtr)
  91     {
  92         List_Node nodePtr = new List_Node();
  93
  94         if(nodePtr == null) {
  95             return null;
  96         }
  97
  98         nodePtr.dataPtr = dataPtr;
  99         nodePtr.nextPtr = null;
 100
 101         return nodePtr;
 102     }
 103
 104
 105 /* =============================================================================
 106  * list_alloc
 107  * -- If NULL passed for 'compare' function, will compare data pointer addresses
 108  * -- Returns NULL on failure
 109  * =============================================================================
 110  * list_t* list_alloc (long (*compare)(const void*, const void*));
 111  *
 112  *
 113  */
 114
 115   public static List_t alloc()
 116     {
 117         List_t listPtr = new List_t();
 118
 119         if(listPtr  == null) {
 120             return null;
 121         }
 122
 123         listPtr.head.dataPtr = null;
 124         listPtr.head.nextPtr = null;
 125         listPtr.size = 0;
 126
 127         return listPtr;
 128     }
 129
 130 /* =============================================================================
 131  * list_free
 132  * -- If NULL passed for 'compare' function, will compare data pointer addresses
 133  * -- Returns NULL on failure
 134  * =============================================================================
 135  * void list_free (list_t* listPtr);
 136  */
 137     public static void free(List_t listPtr)
 138     {
 139         listPtr = null;
 140     }
 141
 142 //    privae freeList
 143
 144 /* =============================================================================
 145  * list_isEmpty
 146  * -- Return TRUE if list is empty, else FALSE
 147  * =============================================================================
 148  * bool_t list_isEmpty (list_t* listPtr);
 149  */
 150     public boolean isEmpty()
 151     {
 152         return (head.nextPtr == null);
 153     }
 154
 155 /* =============================================================================
 156  * list_getSize
 157  * -- Returns size of list
 158  * =============================================================================
 159  * long list_getSize (list_t* listPtr);
 160  */
 161     public int getSize() {
 162         return size;
 163     }
 164
 165 /* =============================================================================
 166  * findPrevious
 167  * =============================================================================
 168  * void* list_find (list_t* listPtr, void* dataPtr);
 169  */
 170     private List_Node findPrevious(Object dataPtr)
 171     {
 172         List_Node prevPtr = head;
 173         List_Node nodePtr = prevPtr.nextPtr;
 174
 175         for(; nodePtr != null; nodePtr = nodePtr.nextPtr) {
 176             if (compare(nodePtr.dataPtr,dataPtr) >= 0) {
 177                 return prevPtr;
 178             }
 179             prevPtr = nodePtr;
 180         }
 181
 182         return prevPtr;
 183     }
 184
 185     /* =============================================================================
 186      * list_find
 187      * -- Returns NULL if not found, else returns pointer to data
 188      * =============================================================================
 189      * void* list_find (list_t* listPtr, void* dataPtr);
 190      */
 191     public Object find(Object dataPtr) {
 192         List_Node nodePtr;
 193         List_Node prevPtr = findPrevious(dataPtr);
 194
 195         nodePtr = prevPtr.nextPtr;
 196
 197         if((nodePtr == null) ||
 198                 (compare(nodePtr.dataPtr,dataPtr) != 0)) {
 199             return null;
 200         }
 201
 202         return (nodePtr.dataPtr);
 203     }
 204
 205     public int compare(Object obj1,Object obj2)
 206     {
 207       Reservation_Info aPtr=(Reservation_Info)obj1;
 208       Reservation_Info bPtr=(Reservation_Info)obj2;
 209       int typeDiff;
 210
 211       typeDiff = aPtr.type - bPtr.type;
 212
 213       return ((typeDiff != 0) ? (typeDiff) : (aPtr.id - bPtr.id));
 214     }
 215
 216 /* =============================================================================
 217  * list_insert
 218  * -- Return TRUE on success, else FALSE
 219  * =============================================================================
 220  * bool_t list_insert (list_t* listPtr, void* dataPtr);
 221  */
 222     public boolean insert(Object dataPtr) {
 223         List_Node prevPtr;
 224         List_Node nodePtr;
 225         List_Node currPtr;
 226
 227         prevPtr = findPrevious(dataPtr);
 228         currPtr = prevPtr.nextPtr;
 229
 230         nodePtr = allocNode(dataPtr);
 231         if (nodePtr == null) {
 232             return false;
 233         }
 234
 235         nodePtr.nextPtr = currPtr;
 236         prevPtr.nextPtr = nodePtr;
 237         size++;
 238
 239         return true;
 240     }
 241
 242
 243 /* =============================================================================
 244  * list_remove
 245  * -- Returns TRUE if successful, else FALSE
 246  * =============================================================================
 247  * bool_t list_remove (list_t* listPtr, void* dataPtr);
 248  */
 249     public boolean remove(Object dataPtr)
 250     {
 251         List_Node prevPtr;
 252         List_Node nodePtr;
 253
 254         prevPtr = findPrevious(dataPtr);
 255
 256         nodePtr = prevPtr.nextPtr;
 257
 258         if((nodePtr != null) &&
 259             (compare(nodePtr.dataPtr,dataPtr) == 0))
 260         {
 261             prevPtr.nextPtr = nodePtr.nextPtr;
 262             nodePtr.nextPtr = null;
 263             nodePtr = null;
 264             size--;
 265
 266             return true;
 267         }
 268
 269         return false;
 270     }
 271
 272     int compareObject(Object obj1,Object obj2) {
 273         return 1;
 274     }
 275
 276
 277 /* =============================================================================
 278  * list_clear
 279  * -- Removes all elements
 280  * =============================================================================
 281  * void list_clear (list_t* listPtr);
 282  */
 283     public void clear() {
 284         head = new List_Node();
 285         size = 0;
 286     }
 287
 288 /* =============================================================================
 289  *
 290  * End of list.java
 291  *
 292  * =============================================================================
 293  */
 294
 295  /* Test list */
 296
 297  public static void main(String[] argv) {
 298      List_t listPtr;
 299      int[] data1 = new int[5];
 300      int[] data2 = new int[6];
 301
 302      int i;
 303
 304      System.out.println("Starting...");
 305         }
 306
 307 }
 308
 309
 310