001package org.apache.commons.jcs3.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.jcs3.log.Log; 023import org.apache.commons.jcs3.log.LogManager; 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; 034 035 /** The logger */ 036 private static final Log log = LogManager.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 } 050 051 /** 052 * Adds a new node to the end of the link list. 053 * <p> 054 * @param me The feature to be added to the Last 055 */ 056 public synchronized void addLast(final T me) 057 { 058 if ( first == null ) 059 { 060 // empty list. 061 first = me; 062 } 063 else 064 { 065 last.next = me; 066 me.prev = last; 067 } 068 last = me; 069 size++; 070 } 071 072 /** 073 * Adds a new node to the start of the link list. 074 * <p> 075 * @param me The feature to be added to the First 076 */ 077 public synchronized void addFirst(final T me) 078 { 079 if ( last == null ) 080 { 081 // empty list. 082 last = me; 083 } 084 else 085 { 086 first.prev = me; 087 me.next = first; 088 } 089 first = me; 090 size++; 091 } 092 093 /** 094 * Returns the last node from the link list, if there are any nodes. 095 * <p> 096 * @return The last node. 097 */ 098 public synchronized T getLast() 099 { 100 log.debug( "returning last node" ); 101 return last; 102 } 103 104 /** 105 * Removes the specified node from the link list. 106 * <p> 107 * @return DoubleLinkedListNode, the first node. 108 */ 109 public synchronized T getFirst() 110 { 111 log.debug( "returning first node" ); 112 return first; 113 } 114 115 /** 116 * Moves an existing node to the start of the link list. 117 * <p> 118 * @param ln The node to set as the head. 119 */ 120 public synchronized void makeFirst(final T ln) 121 { 122 if ( ln.prev == null ) 123 { 124 // already the first node. or not a node 125 return; 126 } 127 // splice: remove it from the list 128 ln.prev.next = ln.next; 129 130 if ( ln.next == null ) 131 { 132 // last but not the first. 133 last = (T) ln.prev; 134 last.next = null; 135 } 136 else 137 { 138 // neither the last nor the first. 139 ln.next.prev = ln.prev; 140 } 141 first.prev = ln; 142 ln.next = first; 143 ln.prev = null; 144 first = ln; 145 } 146 147 /** 148 * Moves an existing node to the end of the link list. 149 * <p> 150 * @param ln The node to set as the head. 151 */ 152 public synchronized void makeLast(final T ln) 153 { 154 if ( ln.next == null ) 155 { 156 // already the last node. or not a node 157 return; 158 } 159 // splice: remove it from the list 160 if ( ln.prev != null ) 161 { 162 ln.prev.next = ln.next; 163 } 164 else 165 { 166 // first 167 first = last; 168 } 169 170 if ( last != null ) 171 { 172 last.next = ln; 173 } 174 ln.prev = last; 175 ln.next = null; 176 last = ln; 177 } 178 179 /** 180 * Remove all of the elements from the linked list implementation. 181 */ 182 public synchronized void removeAll() 183 { 184 for (T me = first; me != null; ) 185 { 186 if ( me.prev != null ) 187 { 188 me.prev = null; 189 } 190 me = (T) me.next; 191 } 192 first = last = null; 193 // make sure this will work, could be add while this is happening. 194 size = 0; 195 } 196 197 /** 198 * Removes the specified node from the link list. 199 * <p> 200 * @param me Description of the Parameter 201 * @return true if an element was removed. 202 */ 203 public synchronized boolean remove(final T me) 204 { 205 log.debug( "removing node" ); 206 207 if ( me.next == null ) 208 { 209 if ( me.prev == null ) 210 { 211 // Make sure it really is the only node before setting head and 212 // tail to null. It is possible that we will be passed a node 213 // which has already been removed from the list, in which case 214 // we should ignore it 215 216 if ( me == first && me == last ) 217 { 218 first = last = null; 219 } 220 } 221 else 222 { 223 // last but not the first. 224 last = (T) me.prev; 225 last.next = null; 226 me.prev = null; 227 } 228 } 229 else if ( me.prev == null ) 230 { 231 // first but not the last. 232 first = (T) me.next; 233 first.prev = null; 234 me.next = null; 235 } 236 else 237 { 238 // neither the first nor the last. 239 me.prev.next = me.next; 240 me.next.prev = me.prev; 241 me.prev = me.next = null; 242 } 243 size--; 244 245 return true; 246 } 247 248 /** 249 * Removes the specified node from the link list. 250 * <p> 251 * @return The last node if there was one to remove. 252 */ 253 public synchronized T removeLast() 254 { 255 log.debug( "removing last node" ); 256 final T temp = last; 257 if ( last != null ) 258 { 259 remove( last ); 260 } 261 return temp; 262 } 263 264 /** 265 * Returns the size of the list. 266 * <p> 267 * @return int 268 */ 269 public synchronized int size() 270 { 271 return size; 272 } 273 274 // /////////////////////////////////////////////////////////////////// 275 /** 276 * Dump the cache entries from first to list for debugging. 277 */ 278 public synchronized void debugDumpEntries() 279 { 280 if ( log.isDebugEnabled() ) 281 { 282 log.debug( "dumping Entries" ); 283 for (T me = first; me != null; me = (T) me.next) 284 { 285 log.debug( "dump Entries> payload= \"{0}\"", me.getPayload() ); 286 } 287 } 288 } 289}