001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.wicket.pageStore.disk;
018
019import java.io.Serializable;
020import java.util.ArrayList;
021import java.util.List;
022
023import org.apache.wicket.pageStore.IPersistedPage;
024import org.apache.wicket.util.collections.IntHashMap;
025import org.apache.wicket.util.lang.Bytes;
026
027/**
028 * Manages positions and size of chunks of data in a file.
029 * <p>
030 * The data is stored inside the file in a cyclic way. Newer pages are placed after older ones,
031 * until the maximum file size is reached. After that, the next page is stored in the beginning of
032 * the file.
033 * 
034 * @author Matej Knopp
035 */
036public class PageWindowManager implements Serializable
037{
038        private static final long serialVersionUID = 1L;
039
040        /**
041         * Contains information about a page inside the file.
042         * 
043         * @author Matej Knopp
044         */
045        public static class FileWindow implements IPersistedPage, Serializable
046        {
047                private static final long serialVersionUID = 1L;
048
049                /** id of data or -1 if the window is empty */
050                private int id;
051
052                private String type;
053
054                /** offset in the file where the serialized page data begins */
055                private int filePartOffset;
056
057                /** size of serialized page data */
058                private int filePartSize;
059
060                @Override
061                public int getPageId()
062                {
063                        return id;
064                }
065
066                @Override
067                public String getPageType()
068                {
069                        return type;
070                }
071                
072                @Override
073                public Bytes getPageSize()
074                {
075                        return Bytes.bytes(filePartSize);
076                }
077
078                public int getFilePartOffset()
079                {
080                        return filePartOffset;
081                }
082                
083                public int getFilePartSize()
084                {
085                        return filePartSize;
086                }
087        }
088
089        private final List<FileWindow> windows = new ArrayList<>();
090
091        /**
092         * map from page id to list of pagewindow indices (referring to the windows list) - to improve
093         * searching speed the index must be cleaned when the instances in the windows list change their
094         * indexes (e.g. items are shifted on page window removal)
095         */
096        private IntHashMap<Integer> idToWindowIndex = null;
097
098        /**
099         * Inversed index of #idToWindowIndex
100         */
101        private IntHashMap<Integer> windowIndexToPageId = null;
102
103        /** index of last added page */
104        private int indexPointer = -1;
105
106        private int totalSize = 0;
107
108        /**
109         * Maximum page size. After this size is exceeded, the pages will be saved starting at the
110         * beginning of file.
111         */
112        private final long maxSize;
113
114        /**
115         * 
116         * @param pageId
117         * @param windowIndex
118         */
119        private void putWindowIndex(int pageId, int windowIndex)
120        {
121                if (idToWindowIndex != null && pageId != -1 && windowIndex != -1)
122                {
123                        Integer oldPageId = windowIndexToPageId.remove(windowIndex);
124                        if (oldPageId != null)
125                        {
126                                idToWindowIndex.remove(oldPageId);
127                        }
128                        idToWindowIndex.put(pageId, windowIndex);
129                        windowIndexToPageId.put(windowIndex, pageId);
130                }
131        }
132
133        /**
134         * 
135         * @param pageId
136         */
137        private void removeWindowIndex(int pageId)
138        {
139                Integer windowIndex = idToWindowIndex.remove(pageId);
140                if (windowIndex != null)
141                {
142                        windowIndexToPageId.remove(windowIndex);
143                }
144        }
145
146        /**
147         * 
148         */
149        private void rebuildIndices()
150        {
151                idToWindowIndex = null;
152                idToWindowIndex = new IntHashMap<>();
153                windowIndexToPageId = null;
154                windowIndexToPageId = new IntHashMap<>();
155                for (int i = 0; i < windows.size(); ++i)
156                {
157                        FileWindow window = windows.get(i);
158                        putWindowIndex(window.id, i);
159                }
160        }
161
162        /**
163         * Returns the index of the given page in the {@link #windows} list.
164         * 
165         * @param pageId
166         * @return window index
167         */
168        private int getWindowIndex(int pageId)
169        {
170                if (idToWindowIndex == null)
171                {
172                        rebuildIndices();
173                }
174
175                Integer result = idToWindowIndex.get(pageId);
176                return result != null ? result : -1;
177        }
178
179        /**
180         * Increments the {@link #indexPointer}. If the maximum file size has been reached, the
181         * {@link #indexPointer} is set to 0.
182         * 
183         * @return new index pointer
184         */
185        private int incrementIndexPointer()
186        {
187                if ((maxSize > 0) && (totalSize >= maxSize) && (indexPointer == windows.size() - 1))
188                {
189                        indexPointer = 0;
190                }
191                else
192                {
193                        ++indexPointer;
194                }
195                return indexPointer;
196        }
197
198        /**
199         * Returns the offset in file of the window on given index. The offset is counted by getting the
200         * previous page offset and adding the previous page size to it.
201         * 
202         * @param index
203         * @return window file offset
204         */
205        private int getWindowFileOffset(int index)
206        {
207                if (index > 0)
208                {
209                        FileWindow window = windows.get(index - 1);
210                        return window.filePartOffset + window.filePartSize;
211                }
212                return 0;
213        }
214
215        /**
216         * Splits the window with given index to two windows. First of those will have size specified by
217         * the argument, the other one will fill up the rest of the original window.
218         * 
219         * @param index
220         * @param size
221         */
222        private void splitWindow(int index, int size)
223        {
224                FileWindow window = windows.get(index);
225                int delta = window.filePartSize - size;
226
227                if (index == windows.size() - 1)
228                {
229                        // if this is last window
230                        totalSize -= delta;
231                        window.filePartSize = size;
232                }
233                else if (window.filePartSize != size)
234                {
235                        FileWindow newWindow = new FileWindow();
236                        newWindow.id = -1;
237                        window.filePartSize = size;
238
239                        windows.add(index + 1, newWindow);
240
241                        newWindow.filePartOffset = getWindowFileOffset(index + 1);
242                        newWindow.filePartSize = delta;
243                }
244
245                idToWindowIndex = null;
246                windowIndexToPageId = null;
247        }
248
249        /**
250         * Merges the window with given index with the next window. The resulting window will have size
251         * of the two windows summed together.
252         * 
253         * @param index
254         */
255        private void mergeWindowWithNext(int index)
256        {
257                if (index < windows.size() - 1)
258                {
259                        FileWindow window = windows.get(index);
260                        FileWindow next = windows.get(index + 1);
261                        window.filePartSize += next.filePartSize;
262
263                        windows.remove(index + 1);
264                        idToWindowIndex = null; // reset index
265                        windowIndexToPageId = null;
266                }
267        }
268
269        /**
270         * Adjusts the window on given index to the specified size. If the new size is smaller than the
271         * window size, the window will be split. Otherwise the window will be merged with as many
272         * subsequent window as necessary. In case the window is last window in the file, the size will
273         * be adjusted without splitting or merging.
274         * 
275         * @param index
276         * @param size
277         */
278        private void adjustWindowSize(int index, int size)
279        {
280                FileWindow window = windows.get(index);
281
282                // last window, just adjust size
283                if (index == windows.size() - 1)
284                {
285                        int delta = size - window.filePartSize;
286                        totalSize += delta;
287                        window.filePartSize = size;
288                }
289                else
290                {
291                        // merge as many times as necessary
292                        while (window.filePartSize < size && index < windows.size() - 1)
293                        {
294                                mergeWindowWithNext(index);
295                        }
296
297                        // done merging - do we have enough room ?
298                        if (window.filePartSize < size)
299                        {
300                                // no, this is the last window
301                                int delta = size - window.filePartSize;
302                                totalSize += delta;
303                                window.filePartSize = size;
304                        }
305                        else
306                        {
307                                // yes, we might want to split the window, so that we don't lose
308                                // space when the created window was too big
309                                splitWindow(index, size);
310                        }
311                }
312
313                window.id = -1;
314        }
315
316        /**
317         * Allocates window on given index with to size. If the index is pointing to existing window,
318         * the window size will be adjusted. Otherwise a new window with appropriated size will be
319         * created.
320         * 
321         * @param index
322         * @param size
323         * @return page window
324         */
325        private FileWindow allocatePageWindow(int index, int size)
326        {
327                final FileWindow window;
328
329                // new window
330                if (index == windows.size())
331                {
332                        // new page window
333                        window = new FileWindow();
334                        window.filePartOffset = getWindowFileOffset(index);
335                        totalSize += size;
336                        window.filePartSize = size;
337                        windows.add(window);
338                }
339                else
340                {
341                        // get the window
342                        window = windows.get(index);
343
344                        // adjust if necessary
345                        if (window.filePartSize != size)
346                        {
347                                adjustWindowSize(index, size);
348                        }
349                }
350
351                return window;
352        }
353
354        /**
355         * Creates and returns a new page window for given page.
356         * 
357         * @param pageId
358         * @param pageType
359         * @param size
360         * @return page window
361         */
362        public synchronized FileWindow createPageWindow(int pageId, String pageType, int size)
363        {
364                int index = getWindowIndex(pageId);
365
366                // if we found the page window, mark it as invalid
367                if (index != -1)
368                {
369                        removeWindowIndex(pageId);
370                        (windows.get(index)).id = -1;
371                }
372
373                // if we are not going to reuse a page window (because it's not on
374                // indexPointer position or because we didn't find it), increment the
375                // indexPointer
376                if (index == -1 || index != indexPointer)
377                {
378                        index = incrementIndexPointer();
379                }
380
381                FileWindow window = allocatePageWindow(index, size);
382                window.id = pageId;
383                window.type = pageType;
384
385                putWindowIndex(pageId, index);
386                return window;
387        }
388
389        /**
390         * Returns the page window for given page or null if no window was found.
391         * 
392         * @param pageId
393         * @return page window or null
394         */
395        public synchronized FileWindow getPageWindow(int pageId)
396        {
397                int index = getWindowIndex(pageId);
398                if (index != -1)
399                {
400                        return windows.get(index);
401                }
402                return null;
403        }
404
405        /**
406         * Removes the page window for given page.
407         * 
408         * @param pageId
409         */
410        public synchronized void removePage(int pageId)
411        {
412                int index = getWindowIndex(pageId);
413                if (index != -1)
414                {
415                        FileWindow window = windows.get(index);
416                        removeWindowIndex(pageId);
417                        if (index == windows.size() - 1)
418                        {
419                                windows.remove(index);
420                                totalSize -= window.filePartSize;
421                                if (indexPointer == index)
422                                {
423                                        --indexPointer;
424                                }
425                        }
426                        else
427                        {
428                                window.id = -1;
429                        }
430                }
431        }
432
433        /**
434         * Returns last n saved page windows.
435         * 
436         * @return list of page windows
437         */
438        public synchronized List<FileWindow> getFileWindows()
439        {
440                List<FileWindow> result = new ArrayList<>();
441
442                // start from current index to 0
443                int currentIndex = indexPointer;
444
445                do
446                {
447                        if (currentIndex == -1)
448                        {
449                                break;
450                        }
451
452                        if (currentIndex < windows.size())
453                        {
454                                FileWindow window = windows.get(currentIndex);
455                                if (window.id != -1)
456                                {
457                                        result.add(window);
458                                }
459                        }
460
461                        --currentIndex;
462                        if (currentIndex == -1)
463                        {
464                                // rewind to the last entry and collect all entries until current index
465                                currentIndex = windows.size() - 1;
466                        }
467                }
468                while (currentIndex != indexPointer);
469
470                return result;
471        }
472
473        /**
474         * Creates a new PageWindowManager.
475         * 
476         * @param maxSize
477         *            maximum page size. After this size is exceeded, the pages will be saved starting
478         *            at the beginning of file
479         */
480        public PageWindowManager(long maxSize)
481        {
482                this.maxSize = maxSize;
483        }
484
485        /**
486         * Returns the size of all saved pages
487         * 
488         * @return total size
489         */
490        public synchronized int getTotalSize()
491        {
492                return totalSize;
493        }
494}