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