src/com/owncloud/android/files/services/IndexedForest.java

   1 /* ownCloud Android client application
   2  *
   3  *   @author David A. Velasco
   4  *   Copyright (C) 2015 ownCloud Inc.
   5  *
   6  *   This program is free software: you can redistribute it and/or modify
   7  *   it under the terms of the GNU General Public License version 2,
   8  *   as published by the Free Software Foundation.
   9  *
  10  *   This program is distributed in the hope that it will be useful,
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *   GNU General Public License for more details.
  14  *
  15  *   You should have received a copy of the GNU General Public License
  16  *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  *
  18  */
  19
  20 package com.owncloud.android.files.services;
  21
  22 import android.accounts.Account;
  23 import android.util.Pair;
  24
  25 import com.owncloud.android.datamodel.OCFile;
  26 import com.owncloud.android.lib.common.utils.Log_OC;
  27
  28 import java.io.File;
  29 import java.util.HashSet;
  30 import java.util.Iterator;
  31 import java.util.Set;
  32 import java.util.concurrent.ConcurrentHashMap;
  33 import java.util.concurrent.ConcurrentMap;
  34
  35 /**
  36  *  Helper structure to keep the trees of folders containing any file downloading or synchronizing.
  37  *
  38  *  A map provides the indexation based in hashing.
  39  *
  40  *  A tree is created per account.
  41  */
  42 public class IndexedForest<V> {
  43
  44     private ConcurrentMap<String, Node<V>> mMap = new ConcurrentHashMap<String, Node<V>>();
  45
  46     private class Node<V> {
  47         String mKey = null;
  48         Node<V> mParent = null;
  49         Set<Node<V>> mChildren = new HashSet<Node<V>>();    // TODO be careful with hash()
  50         V mPayload = null;
  51
  52         // payload is optional
  53         public Node(String key, V payload) {
  54             if (key == null) {
  55                 throw new IllegalArgumentException("Argument key MUST NOT be null");
  56             }
  57             mKey = key;
  58             mPayload = payload;
  59         }
  60
  61         public Node<V> getParent() {
  62             return mParent;
  63         };
  64
  65         public Set<Node<V>> getChildren() {
  66             return mChildren;
  67         }
  68
  69         public String getKey() {
  70             return mKey;
  71         }
  72
  73         public V getPayload() {
  74             return mPayload;
  75         }
  76
  77         public void addChild(Node<V> child) {
  78             mChildren.add(child);
  79             child.setParent(this);
  80         }
  81
  82         private void setParent(Node<V> parent) {
  83             mParent = parent;
  84         }
  85
  86         public boolean hasChildren() {
  87             return mChildren.size() > 0;
  88         }
  89
  90         public void removeChild(Node<V> removed) {
  91             mChildren.remove(removed);
  92         }
  93
  94         public void clearPayload() {
  95             mPayload = null;
  96         }
  97     }
  98
  99
 100     public /* synchronized */ Pair<String, String> putIfAbsent(Account account, String remotePath, V value) {
 101         String targetKey = buildKey(account, remotePath);
 102         Node<V> valuedNode = new Node(targetKey, value);
 103         mMap.putIfAbsent(
 104                 targetKey,
 105                 valuedNode
 106         );
 107
 108         String currentPath = remotePath, parentPath = null, parentKey = null;
 109         Node<V> currentNode = valuedNode, parentNode = null;
 110         boolean linked = false;
 111         while (!OCFile.ROOT_PATH.equals(currentPath) && !linked) {
 112             parentPath = new File(currentPath).getParent();
 113             if (!parentPath.endsWith(OCFile.PATH_SEPARATOR)) {
 114                 parentPath += OCFile.PATH_SEPARATOR;
 115             }
 116             parentKey = buildKey(account, parentPath);
 117             parentNode = mMap.get(parentKey);
 118             if (parentNode == null) {
 119                 parentNode = new Node(parentKey, null);
 120                 parentNode.addChild(currentNode);
 121                 mMap.put(parentKey, parentNode);
 122             } else {
 123                 parentNode.addChild(currentNode);
 124                 linked = true;
 125             }
 126             currentPath = parentPath;
 127             currentNode = parentNode;
 128         }
 129
 130         String linkedTo = OCFile.ROOT_PATH;
 131         if (linked) {
 132             linkedTo = parentNode.getKey().substring(account.name.length());
 133         }
 134         return new Pair<String, String>(targetKey, linkedTo);
 135     };
 136
 137
 138     public Pair<V, String> removePayload(Account account, String remotePath) {
 139         String targetKey = buildKey(account, remotePath);
 140         Node<V> target = mMap.get(targetKey);
 141         if (target != null) {
 142             target.clearPayload();
 143             if (!target.hasChildren()) {
 144                 return remove(account, remotePath);
 145             }
 146         }
 147         return new Pair<V, String>(null, null);
 148     }
 149
 150
 151     public /* synchronized */ Pair<V, String> remove(Account account, String remotePath) {
 152         String targetKey = buildKey(account, remotePath);
 153         Node<V> firstRemoved = mMap.remove(targetKey);
 154         String unlinkedFrom = null;
 155
 156         if (firstRemoved != null) {
 157             /// remove children
 158             removeDescendants(firstRemoved);
 159
 160             /// remove ancestors if only here due to firstRemoved
 161             Node<V> removed = firstRemoved;
 162             Node<V> parent = removed.getParent();
 163             boolean unlinked = false;
 164             while (parent != null) {
 165                 parent.removeChild(removed);
 166                 if (!parent.hasChildren()) {
 167                     removed = mMap.remove(parent.getKey());
 168                     parent = removed.getParent();
 169                 } else {
 170                     break;
 171                 }
 172             }
 173
 174             if (parent != null) {
 175                 unlinkedFrom = parent.getKey().substring(account.name.length());
 176             }
 177
 178             return new Pair<V, String>(firstRemoved.getPayload(), unlinkedFrom);
 179         }
 180
 181         return new Pair<V, String>(null, null);
 182     }
 183
 184     private void removeDescendants(Node<V> removed) {
 185         Iterator<Node<V>> childrenIt = removed.getChildren().iterator();
 186         Node<V> child = null;
 187         while (childrenIt.hasNext()) {
 188             child = childrenIt.next();
 189             mMap.remove(child.getKey());
 190             removeDescendants(child);
 191         }
 192     }
 193
 194     public boolean contains(Account account, String remotePath) {
 195         String targetKey = buildKey(account, remotePath);
 196         return mMap.containsKey(targetKey);
 197     }
 198
 199     public /* synchronized */ V get(String key) {
 200         Node<V> node = mMap.get(key);
 201         if (node != null) {
 202             return node.getPayload();
 203         } else {
 204             return null;
 205         }
 206     }
 207
 208     public V get(Account account, String remotePath) {
 209         String key = buildKey(account, remotePath);
 210         return get(key);
 211     }
 212
 213
 214     /**
 215      * Remove the elements that contains account as a part of its key
 216      * @param account
 217      */
 218     public void remove(Account account){
 219         Iterator<String> it = mMap.keySet().iterator();
 220         while (it.hasNext()) {
 221             String key = it.next();
 222             Log_OC.d("IndexedForest", "Number of pending downloads= "  + mMap.size());
 223             if (key.startsWith(account.name)) {
 224                 mMap.remove(key);
 225             }
 226         }
 227     }
 228
 229     /**
 230      * Builds a key to index files
 231      *
 232      * @param account       Account where the file to download is stored
 233      * @param remotePath    Path of the file in the server
 234      */
 235     private String buildKey(Account account, String remotePath) {
 236         return account.name + remotePath;
 237     }
 238
 239 }