1
// Copyright 2013 The Closure Library Authors. All Rights Reserved.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS-IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
/**
16
 * @fileoverview Provides a convenient API for data persistence with data
17
 * expiration and number of items limit.
18
 *
19
 * Setting and removing values keeps a max number of items invariant.
20
 * Collecting values can be user initiated. If oversize, first removes
21
 * expired items, if still oversize than removes the oldest items until a size
22
 * constraint is fulfilled.
23
 *
24
 */
25

26
goog.provide('goog.labs.storage.BoundedCollectableStorage');
27

28
goog.require('goog.array');
29
goog.require('goog.asserts');
30
goog.require('goog.iter');
31
goog.require('goog.storage.CollectableStorage');
32
goog.require('goog.storage.ErrorCode');
33
goog.require('goog.storage.ExpiringStorage');
34

35

36

37
/**
38
 * Provides a storage with bounded number of elements, expiring keys and
39
 * a collection method.
40
 *
41
 * @param {!goog.storage.mechanism.IterableMechanism} mechanism The underlying
42
 *     storage mechanism.
43
 * @param {number} maxItems Maximum number of items in storage.
44
 * @constructor
45
 * @struct
46
 * @extends {goog.storage.CollectableStorage}
47
 * @final
48
 */
49
goog.labs.storage.BoundedCollectableStorage = function(mechanism, maxItems) {
50
  goog.labs.storage.BoundedCollectableStorage.base(
51
      this, 'constructor', mechanism);
52

53
  /**
54
   * A maximum number of items that should be stored.
55
   * @private {number}
56
   */
57
  this.maxItems_ = maxItems;
58
};
59
goog.inherits(
60
    goog.labs.storage.BoundedCollectableStorage,
61
    goog.storage.CollectableStorage);
62

63

64
/**
65
 * An item key used to store a list of keys.
66
 * @const
67
 * @private
68
 */
69
goog.labs.storage.BoundedCollectableStorage.KEY_LIST_KEY_ =
70
    'bounded-collectable-storage';
71

72

73
/**
74
 * Recreates a list of keys in order of creation.
75
 *
76
 * @return {!Array<string>} a list of unexpired keys.
77
 * @private
78
 */
79
goog.labs.storage.BoundedCollectableStorage.prototype.rebuildIndex_ =
80
    function() {
81
  var keys = [];
82
  goog.iter.forEach(
83
      /** @type {goog.storage.mechanism.IterableMechanism} */ (this.mechanism)
84
          .__iterator__(true),
85
      function(key) {
86
        if (goog.labs.storage.BoundedCollectableStorage.KEY_LIST_KEY_ == key) {
87
          return;
88
        }
89

90
        var wrapper;
91

92
        try {
93
          wrapper = this.getWrapper(key, true);
94
        } catch (ex) {
95
          if (ex == goog.storage.ErrorCode.INVALID_VALUE) {
96
            // Skip over bad wrappers and continue.
97
            return;
98
          }
99
          // Unknown error, escalate.
100
          throw ex;
101
        }
102
        goog.asserts.assert(wrapper);
103

104
        var creationTime =
105
            goog.storage.ExpiringStorage.getCreationTime(wrapper);
106
        keys.push({key: key, created: creationTime});
107
      },
108
      this);
109

110
  goog.array.sort(keys, function(a, b) { return a.created - b.created; });
111

112
  return goog.array.map(keys, function(v) { return v.key; });
113
};
114

115

116
/**
117
 * Gets key list from a local storage. If an item does not exist,
118
 * may recreate it.
119
 *
120
 * @param {boolean} rebuild Whether to rebuild a index if no index item exists.
121
 * @return {!Array<string>} a list of keys if index exist, otherwise undefined.
122
 * @private
123
 */
124
goog.labs.storage.BoundedCollectableStorage.prototype.getKeys_ = function(
125
    rebuild) {
126
  var keys =
127
      goog.labs.storage.BoundedCollectableStorage.superClass_.get.call(
128
          this, goog.labs.storage.BoundedCollectableStorage.KEY_LIST_KEY_) ||
129
      null;
130
  if (!keys || !goog.isArray(keys)) {
131
    if (rebuild) {
132
      keys = this.rebuildIndex_();
133
    } else {
134
      keys = [];
135
    }
136
  }
137
  return /** @type {!Array<string>} */ (keys);
138
};
139

140

141
/**
142
 * Saves a list of keys in a local storage.
143
 *
144
 * @param {Array<string>} keys a list of keys to save.
145
 * @private
146
 */
147
goog.labs.storage.BoundedCollectableStorage.prototype.setKeys_ = function(
148
    keys) {
149
  goog.labs.storage.BoundedCollectableStorage.superClass_.set.call(
150
      this, goog.labs.storage.BoundedCollectableStorage.KEY_LIST_KEY_, keys);
151
};
152

153

154
/**
155
 * Remove subsequence from a sequence.
156
 *
157
 * @param {!Array<string>} keys is a sequence.
158
 * @param {!Array<string>} keysToRemove subsequence of keys, the order must
159
 *     be kept.
160
 * @return {!Array<string>} a keys sequence after removing keysToRemove.
161
 * @private
162
 */
163
goog.labs.storage.BoundedCollectableStorage.removeSubsequence_ = function(
164
    keys, keysToRemove) {
165
  if (keysToRemove.length == 0) {
166
    return goog.array.clone(keys);
167
  }
168
  var keysToKeep = [];
169
  var keysIdx = 0;
170
  var keysToRemoveIdx = 0;
171

172
  while (keysToRemoveIdx < keysToRemove.length && keysIdx < keys.length) {
173
    var key = keysToRemove[keysToRemoveIdx];
174
    while (keysIdx < keys.length && keys[keysIdx] != key) {
175
      keysToKeep.push(keys[keysIdx]);
176
      ++keysIdx;
177
    }
178
    ++keysToRemoveIdx;
179
  }
180

181
  goog.asserts.assert(keysToRemoveIdx == keysToRemove.length);
182
  goog.asserts.assert(keysIdx < keys.length);
183
  return goog.array.concat(keysToKeep, goog.array.slice(keys, keysIdx + 1));
184
};
185

186

187
/**
188
 * Keeps the number of items in storage under maxItems. Removes elements in the
189
 * order of creation.
190
 *
191
 * @param {!Array<string>} keys a list of keys in order of creation.
192
 * @param {number} maxSize a number of items to keep.
193
 * @return {!Array<string>} keys left after removing oversize data.
194
 * @private
195
 */
196
goog.labs.storage.BoundedCollectableStorage.prototype.collectOversize_ =
197
    function(keys, maxSize) {
198
  if (keys.length <= maxSize) {
199
    return goog.array.clone(keys);
200
  }
201
  var keysToRemove = goog.array.slice(keys, 0, keys.length - maxSize);
202
  goog.array.forEach(keysToRemove, function(key) {
203
    goog.labs.storage.BoundedCollectableStorage.superClass_.remove.call(
204
        this, key);
205
  }, this);
206
  return goog.labs.storage.BoundedCollectableStorage.removeSubsequence_(
207
      keys, keysToRemove);
208
};
209

210

211
/**
212
 * Cleans up the storage by removing expired keys.
213
 *
214
 * @param {boolean=} opt_strict Also remove invalid keys.
215
 * @override
216
 */
217
goog.labs.storage.BoundedCollectableStorage.prototype.collect = function(
218
    opt_strict) {
219
  var keys = this.getKeys_(true);
220
  var keysToRemove = this.collectInternal(keys, opt_strict);
221
  keys = goog.labs.storage.BoundedCollectableStorage.removeSubsequence_(
222
      keys, keysToRemove);
223
  this.setKeys_(keys);
224
};
225

226

227
/**
228
 * Ensures that we keep only maxItems number of items in a local storage.
229
 * @param {boolean=} opt_skipExpired skip removing expired items first.
230
 * @param {boolean=} opt_strict Also remove invalid keys.
231
 */
232
goog.labs.storage.BoundedCollectableStorage.prototype.collectOversize =
233
    function(opt_skipExpired, opt_strict) {
234
  var keys = this.getKeys_(true);
235
  if (!opt_skipExpired) {
236
    var keysToRemove = this.collectInternal(keys, opt_strict);
237
    keys = goog.labs.storage.BoundedCollectableStorage.removeSubsequence_(
238
        keys, keysToRemove);
239
  }
240
  keys = this.collectOversize_(keys, this.maxItems_);
241
  this.setKeys_(keys);
242
};
243

244

245
/**
246
 * Set an item in the storage.
247
 *
248
 * @param {string} key The key to set.
249
 * @param {*} value The value to serialize to a string and save.
250
 * @param {number=} opt_expiration The number of miliseconds since epoch
251
 *     (as in goog.now()) when the value is to expire. If the expiration
252
 *     time is not provided, the value will persist as long as possible.
253
 * @override
254
 */
255
goog.labs.storage.BoundedCollectableStorage.prototype.set = function(
256
    key, value, opt_expiration) {
257
  goog.labs.storage.BoundedCollectableStorage.base(
258
      this, 'set', key, value, opt_expiration);
259
  var keys = this.getKeys_(true);
260
  goog.array.remove(keys, key);
261

262
  if (goog.isDef(value)) {
263
    keys.push(key);
264
    if (keys.length >= this.maxItems_) {
265
      var keysToRemove = this.collectInternal(keys);
266
      keys = goog.labs.storage.BoundedCollectableStorage.removeSubsequence_(
267
          keys, keysToRemove);
268
      keys = this.collectOversize_(keys, this.maxItems_);
269
    }
270
  }
271
  this.setKeys_(keys);
272
};
273

274

275
/**
276
 * Remove an item from the data storage.
277
 *
278
 * @param {string} key The key to remove.
279
 * @override
280
 */
281
goog.labs.storage.BoundedCollectableStorage.prototype.remove = function(key) {
282
  goog.labs.storage.BoundedCollectableStorage.base(this, 'remove', key);
283

284
  var keys = this.getKeys_(false);
285
  if (goog.isDef(keys)) {
286
    goog.array.remove(keys, key);
287
    this.setKeys_(keys);
288
  }
289
};
290

291