001package org.apache.commons.jcs.utils.struct; 002 003/* 004 * Licensed to the Apache Software Foundation (ASF) under one 005 * or more contributor license agreements. See the NOTICE file 006 * distributed with this work for additional information 007 * regarding copyright ownership. The ASF licenses this file 008 * to you under the Apache License, Version 2.0 (the 009 * "License"); you may not use this file except in compliance 010 * with the License. You may obtain a copy of the License at 011 * 012 * http://www.apache.org/licenses/LICENSE-2.0 013 * 014 * Unless required by applicable law or agreed to in writing, 015 * software distributed under the License is distributed on an 016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 017 * KIND, either express or implied. See the License for the 018 * specific language governing permissions and limitations 019 * under the License. 020 */ 021 022import org.apache.commons.logging.Log; 023import org.apache.commons.logging.LogFactory; 024 025/** 026 * This is a generic thread safe double linked list. It's very simple and all the operations are so 027 * quick that course grained synchronization is more than acceptable. 028 */ 029@SuppressWarnings({ "unchecked", "rawtypes" }) // Don't know how to resolve this with generics 030public class DoubleLinkedList<T extends DoubleLinkedListNode> 031{ 032 /** record size to avoid having to iterate */ 033 private int size = 0; 034 035 /** The logger */ 036 private static final Log log = LogFactory.getLog( DoubleLinkedList.class ); 037 038 /** LRU double linked list head node */ 039 private T first; 040 041 /** LRU double linked list tail node */ 042 private T last; 043 044 /** 045 * Default constructor. 046 */ 047 public DoubleLinkedList() 048 { 049 super(); 050 } 051 052 /** 053 * Adds a new node to the end of the link list. 054 * <p> 055 * @param me The feature to be added to the Last 056 */ 057 public synchronized void addLast(T me) 058 { 059 if ( first == null ) 060 { 061 // empty list. 062 first = me; 063 } 064 else 065 { 066 last.next = me; 067 me.prev = last; 068 } 069 last = me; 070 size++; 071 } 072 073 /** 074 * Adds a new node to the start of the link list. 075 * <p> 076 * @param me The feature to be added to the First 077 */ 078 public synchronized void addFirst(T me) 079 { 080 if ( last == null ) 081 { 082 // empty list. 083 last = me; 084 } 085 else 086 { 087 first.prev = me; 088 me.next = first; 089 } 090 first = me; 091 size++; 092 } 093 094 /** 095 * Returns the last node from the link list, if there are any nodes. 096 * <p> 097 * @return The last node. 098 */ 099 public synchronized T getLast() 100 { 101 if ( log.isDebugEnabled() ) 102 { 103 log.debug( "returning last node" ); 104 } 105 return last; 106 } 107 108 /** 109 * Removes the specified node from the link list. 110 * <p> 111 * @return DoubleLinkedListNode, the first node. 112 */ 113 public synchronized T getFirst() 114 { 115 if ( log.isDebugEnabled() ) 116 { 117 log.debug( "returning first node" ); 118 } 119 return first; 120 } 121 122 /** 123 * Moves an existing node to the start of the link list. 124 * <p> 125 * @param ln The node to set as the head. 126 */ 127 public synchronized void makeFirst(T ln) 128 { 129 if ( ln.prev == null ) 130 { 131 // already the first node. or not a node 132 return; 133 } 134 // splice: remove it from the list 135 ln.prev.next = ln.next; 136 137 if ( ln.next == null ) 138 { 139 // last but not the first. 140 last = (T) ln.prev; 141 last.next = null; 142 } 143 else 144 { 145 // neither the last nor the first. 146 ln.next.prev = ln.prev; 147 } 148 first.prev = ln; 149 ln.next = first; 150 ln.prev = null; 151 first = ln; 152 } 153 154 /** 155 * Moves an existing node to the end of the link list. 156 * <p> 157 * @param ln The node to set as the head. 158 */ 159 public synchronized void makeLast(T ln) 160 { 161 if ( ln.next == null ) 162 { 163 // already the last node. or not a node 164 return; 165 } 166 // splice: remove it from the list 167 if ( ln.prev != null ) 168 { 169 ln.prev.next = ln.next; 170 } 171 else 172 { 173 // first 174 first = last; 175 } 176 177 if ( last != null ) 178 { 179 last.next = ln; 180 } 181 ln.prev = last; 182 ln.next = null; 183 last = ln; 184 } 185 186 /** 187 * Remove all of the elements from the linked list implementation. 188 */ 189 public synchronized void removeAll() 190 { 191 for (T me = first; me != null; ) 192 { 193 if ( me.prev != null ) 194 { 195 me.prev = null; 196 } 197 T next = (T) me.next; 198 me = next; 199 } 200 first = last = null; 201 // make sure this will work, could be add while this is happening. 202 size = 0; 203 } 204 205 /** 206 * Removes the specified node from the link list. 207 * <p> 208 * @param me Description of the Parameter 209 * @return true if an element was removed. 210 */ 211 public synchronized boolean remove(T me) 212 { 213 if ( log.isDebugEnabled() ) 214 { 215 log.debug( "removing node" ); 216 } 217 218 if ( me.next == null ) 219 { 220 if ( me.prev == null ) 221 { 222 // Make sure it really is the only node before setting head and 223 // tail to null. It is possible that we will be passed a node 224 // which has already been removed from the list, in which case 225 // we should ignore it 226 227 if ( me == first && me == last ) 228 { 229 first = last = null; 230 } 231 } 232 else 233 { 234 // last but not the first. 235 last = (T) me.prev; 236 last.next = null; 237 me.prev = null; 238 } 239 } 240 else if ( me.prev == null ) 241 { 242 // first but not the last. 243 first = (T) me.next; 244 first.prev = null; 245 me.next = null; 246 } 247 else 248 { 249 // neither the first nor the last. 250 me.prev.next = me.next; 251 me.next.prev = me.prev; 252 me.prev = me.next = null; 253 } 254 size--; 255 256 return true; 257 } 258 259 /** 260 * Removes the specified node from the link list. 261 * <p> 262 * @return The last node if there was one to remove. 263 */ 264 public synchronized T removeLast() 265 { 266 if ( log.isDebugEnabled() ) 267 { 268 log.debug( "removing last node" ); 269 } 270 T temp = last; 271 if ( last != null ) 272 { 273 remove( last ); 274 } 275 return temp; 276 } 277 278 /** 279 * Returns the size of the list. 280 * <p> 281 * @return int 282 */ 283 public synchronized int size() 284 { 285 return size; 286 } 287 288 // /////////////////////////////////////////////////////////////////// 289 /** 290 * Dump the cache entries from first to list for debugging. 291 */ 292 public synchronized void debugDumpEntries() 293 { 294 if ( log.isDebugEnabled() ) 295 { 296 log.debug( "dumping Entries" ); 297 for (T me = first; me != null; me = (T) me.next) 298 { 299 log.debug( "dump Entries> payload= '" + me.getPayload() + "'" ); 300 } 301 } 302 } 303}