src/main/gov/nasa/jpf/util/SparseClusterArray.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.util;
  19
  20 import java.util.ConcurrentModificationException;
  21 import java.util.Iterator;
  22 import java.util.NoSuchElementException;
  23
  24 /**
  25  * A generic sparse reference array that assumes clusters, and more
  26  * frequent intra-cluster access.
  27  *
  28  * This is motivated by looking for a more suitable ADT to model a heap address
  29  * space, where reference values consist of segment/offset pairs, we have
  30  * reasonably dense and very dynamic population inside of well separated segment
  31  * clusters, and intra-cluster access is more likely than inter-cluster access.
  32  *
  33  * An especially important feature is to be able to iterate efficiently over
  34  * set/unset elements in index intervals (cluster sizes).
  35  *
  36  * The result should find a compromise between the fast element access & iteration
  37  * of a simple, dense array, and the efficient memory storage of a HashMap
  38  * (if only it could avoid box objects).
  39  *
  40  * <2do> so far, we are totally ignorant of population constraints
  41  */
  42 public class SparseClusterArray <E> implements Iterable<E> {
  43
  44   public static final int CHUNK_BITS = 8;
  45   public static final int CHUNK_SIZE = 256;
  46   public static final int N_ELEM = 1 << CHUNK_BITS;     // 8 bits chunk index -> 24 bits segment key (3x8bits / 256 segs)
  47   protected static final int ELEM_MASK = 0xff;
  48   protected static final int BM_ENTRIES = N_ELEM / 64;     // number of bitmap long entries
  49   protected static final int MAX_BM_INDEX = BM_ENTRIES-1;
  50
  51
  52   // 8 bits per segment -> 256 children
  53   public static final int SEG_BITS = 8;
  54   public static final int N_SEG = 1 << SEG_BITS;
  55   protected static final int SEG_MASK = 0xff;
  56   public static final int S1 = 32-SEG_BITS; // L1 shift
  57   public static final int S2 = S1-SEG_BITS; // L2 shift
  58   public static final int S3 = S2-SEG_BITS; // L3 shift
  59   protected static final int CHUNK_BASEMASK = ~SEG_MASK;
  60
  61   public static final int MAX_CLUSTERS = CHUNK_SIZE;      // max int with CHUNK_BITS bits (8)
  62   public static final int MAX_CLUSTER_ENTRIES = 0xffffff; // max int with 32-CHUNK_BITS bits (24) = 16,777,215 elements
  63
  64   protected Root root;
  65   protected Chunk lastChunk;
  66   protected Chunk head;   // linked list for traversal
  67   protected int   nSet; // number of set elements;
  68
  69   protected boolean trackChanges = false;
  70   protected Entry changes; // on demand change (LIFO) queue
  71
  72   //------------------------------------ public types
  73   public static class Snapshot<T,E> {
  74     Object[] values;
  75     int[] indices;
  76
  77     public Snapshot (int size){
  78       values = new Object[size];
  79       indices = new int[size];
  80     }
  81
  82     public int size() {
  83       return indices.length;
  84     }
  85     public T getValue(int i){
  86       return (T) values[i];
  87     }
  88     public int getIndex(int i){
  89       return indices[i];
  90     }
  91   }
  92
  93
  94   public static class Entry<E> {  // queued element
  95     int index;
  96     E value;
  97
  98     Entry<E> next;
  99
 100     Entry (int index, E value){
 101       this.index = index;
 102       this.value = value;
 103     }
 104   }
 105
 106   //------------------------------------ internal types
 107
 108   //--- how we keep our data - index based trie
 109   protected static class Root {
 110     public Node[] seg = new Node[N_SEG];
 111   }
 112
 113   /**
 114    * this corresponds to a toplevel cluster (e.g. thread heap)
 115    */
 116   protected static class Node  {
 117     public ChunkNode[] seg = new ChunkNode[N_SEG];
 118     //int minNextFree; // where to start looking for free elements, also used to determine if Node is full
 119   }
 120
 121   protected static class ChunkNode  {
 122     public Chunk[] seg  = new Chunk[N_SEG];
 123     //int minNextFree; // where to start looking for free elements, also used to determine if ChunkNode is full
 124   }
 125
 126   protected static class Chunk implements Cloneable { // with some extra info to optimize in-chunk access
 127     public int base, top;
 128     public Chunk next;
 129     public Object[] elements;  // it's actually E[], but of course we can't create arrays of a generic type
 130     public long[] bitmap;
 131
 132     //int minNextFree; // where to start looking for free elements, also used to determine if Chunk is full
 133
 134     protected Chunk() {}
 135
 136     protected Chunk(int base){
 137       this.base = base;
 138       this.top = base + N_ELEM;
 139
 140       elements = new Object[N_ELEM];
 141       bitmap = new long[BM_ENTRIES];
 142     }
 143
 144     @Override
 145         public String toString() {
 146       return "Chunk [base=" + base + ",top=" + top + ']';
 147     }
 148
 149     @SuppressWarnings("unchecked")
 150     public <E> Chunk deepCopy( Cloner<E> cloner) throws CloneNotSupportedException {
 151       Chunk nc = (Chunk) super.clone();
 152
 153       E[] elem = (E[])elements;   // bad, but we have to cope with type erasure
 154       Object[] e = new Object[N_ELEM];
 155
 156       for (int i=nextSetBit(0); i>=0; i=nextSetBit(i+1)) {
 157         e[i] = cloner.clone(elem[i]);
 158       }
 159
 160       nc.elements = e;
 161       nc.bitmap = bitmap.clone();
 162
 163       return nc;
 164     }
 165
 166     protected int nextSetBit (int iStart) {
 167       if (iStart < CHUNK_SIZE){
 168         long[] bm = bitmap;
 169         int j = (iStart >> 6); // bm word : iStart/64
 170         long l = bm[j] & (0xffffffffffffffffL << iStart);
 171
 172         while (true) {
 173           if (l != 0) {
 174             return Long.numberOfTrailingZeros(l) + (j << 6);
 175           } else {
 176             if (++j < BM_ENTRIES) {
 177               l = bm[j];
 178             } else {
 179               return -1;
 180             }
 181           }
 182         }
 183       } else {
 184         return -1;
 185       }
 186     }
 187
 188     protected int nextClearBit (int iStart) {
 189       if (iStart < CHUNK_SIZE){
 190         long[] bm = bitmap;
 191         int j = (iStart >> 6); // bm word : iStart/64
 192         long l = ~bm[j] & (0xffffffffffffffffL << iStart);
 193
 194         while (true) {
 195           if (l != 0) {
 196             return Long.numberOfTrailingZeros(l) + (j << 6);
 197           } else {
 198             if (++j < BM_ENTRIES) {
 199               l = ~bm[j];
 200             } else {
 201               return -1;
 202             }
 203           }
 204         }
 205       } else {
 206         return -1;
 207       }
 208     }
 209
 210
 211     public boolean isEmpty() {
 212       long[] bm = bitmap;
 213
 214       for (int i=0; i<BM_ENTRIES; i++){
 215         if (bm[i] != 0) return false;
 216       }
 217
 218       return true;
 219     }
 220   }
 221
 222   //--- iteration over set elements
 223
 224   protected class ElementIterator<T>  implements Iterator<T>, Iterable<T> {
 225     int idx;    // next chunk index
 226     Chunk cur;  // next chunk
 227
 228     public ElementIterator () {
 229       for (Chunk c = head; c != null; c = c.next){
 230         int i = c.nextSetBit(0);
 231         if (i>=0){
 232           cur = c;
 233           idx = i;
 234           return;
 235         }
 236       }
 237     }
 238
 239     @Override
 240         public boolean hasNext() {
 241       return (cur != null);
 242     }
 243
 244     @Override
 245         @SuppressWarnings("unchecked")
 246     public T next() {
 247       Chunk c = cur;
 248       int i = idx;
 249
 250       if (i < 0 || c == null){
 251         throw new NoSuchElementException();
 252       }
 253
 254       Object ret = c.elements[i];
 255       cur = null;
 256
 257       while (c!=null){
 258         i = c.nextSetBit(i+1);
 259         if (i>= 0){
 260           idx = i;
 261           cur = c;
 262
 263           if (ret == null){
 264             // try to recover from a concurrent modification, maybe there is one left
 265             ret = c.elements[i];
 266             continue;
 267           } else {
 268             break;
 269           }
 270         } else {
 271           i = -1;
 272         }
 273         c = c.next;
 274       }
 275
 276       if (ret == null){
 277         // somebody pulled the rug under our feet
 278         throw new ConcurrentModificationException();
 279       }
 280       return (T)ret;
 281     }
 282
 283     @Override
 284         public void remove() {
 285       throw new UnsupportedOperationException();
 286     }
 287
 288     @Override
 289         public Iterator<T> iterator() {
 290       return this;
 291     }
 292   }
 293
 294   protected class ElementIndexIterator implements IndexIterator {
 295     int idx;
 296     Chunk cur;
 297
 298     public ElementIndexIterator () {
 299       for (Chunk c = head; c != null; c = c.next){
 300         int i = c.nextSetBit(0);
 301         if (i>=0){
 302           cur = c;
 303           idx = i;
 304           return;
 305         }
 306       }
 307     }
 308
 309     public ElementIndexIterator (int startIdx){
 310       // locate the start chunk (they are sorted)
 311       Chunk c;
 312       int i;
 313
 314       // get the first chunk at or above the startIdx
 315       for (c=head; c!= null; c=c.next) {
 316         if (c.top > startIdx) {
 317           cur = c;
 318           break;
 319         }
 320       }
 321
 322       if (c.base < startIdx){
 323         i = startIdx & ELEM_MASK;
 324       } else {
 325         i = 0;
 326       }
 327
 328       for (; c != null; c = c.next){
 329         i = c.nextSetBit(i);
 330         if (i>=0){
 331           cur = c;
 332           idx = i;
 333           return;
 334         } else {
 335           i = 0;
 336         }
 337       }
 338     }
 339
 340
 341     @Override
 342         public int next () {
 343       Chunk c = cur;
 344       int i = idx;
 345
 346       if (i < 0 || c == null){
 347         return -1;
 348       }
 349
 350       int iRet = (c.elements[i] != null) ? c.base + i : -1;
 351       cur = null;
 352
 353       while (c!=null){
 354         i = c.nextSetBit(i+1);
 355         if (i>= 0){
 356           idx = i;
 357           cur = c;
 358
 359           if (iRet < 0){
 360             // try to recover from a concurrent modification, maybe there is one left
 361             iRet = c.base + i;
 362             continue;
 363           } else {
 364             break;
 365           }
 366         } else {
 367           i = -1;
 368         }
 369         c = c.next;
 370       }
 371
 372       if (iRet < 0){
 373         // somebody pulled the rug under our feet
 374         throw new ConcurrentModificationException();
 375       }
 376       return iRet;
 377     }
 378
 379   }
 380
 381
 382   //------------------------------------ internal methods
 383
 384   void sortInChunk (Chunk newChunk) {
 385     if (head == null) {
 386       head = newChunk;
 387     } else {
 388       int base = newChunk.base;
 389       if (base < head.base) {
 390         newChunk.next = head;
 391         head = newChunk;
 392       } else {
 393         Chunk cprev, c;
 394         for (cprev=head, c=cprev.next; c != null; cprev=c, c=c.next) {
 395           if (base < c.base) {
 396             newChunk.next = c;
 397             break;
 398           }
 399         }
 400         cprev.next = newChunk;
 401       }
 402     }
 403   }
 404
 405   //------------------------------------ public API
 406
 407   public SparseClusterArray (){
 408     root = new Root();
 409   }
 410
 411   /**
 412    * be careful, this should only be used to get old stored elements during
 413    * a Snapshot restore
 414    */
 415   protected SparseClusterArray (SparseClusterArray base){
 416     root = base.root;
 417     nSet = base.nSet;
 418     head = base.head;
 419   }
 420
 421   @SuppressWarnings("unchecked")
 422   public E get (int i) {
 423     Node l1;
 424     ChunkNode l2;
 425     Chunk l3 = lastChunk;
 426
 427     if (i < 0){
 428       throw new IndexOutOfBoundsException();
 429     }
 430
 431     if (l3 != null && (l3.base == (i & CHUNK_BASEMASK))) {  // cache optimization for in-cluster access
 432       return (E) l3.elements[i & ELEM_MASK];
 433     }
 434
 435     int  j = i >>>  S1;
 436     if ((l1 = root.seg[j]) != null) {           // L1
 437       j = (i >>> S2) & SEG_MASK;
 438       if ((l2 = l1.seg[j]) != null) {           // L2
 439         j = (i >>> S3) & SEG_MASK;
 440         if ((l3 = l2.seg[j]) != null) {         // L3
 441           // too bad we can't get rid of this cast
 442           lastChunk = l3;
 443           return  (E) l3.elements[i & ELEM_MASK];
 444         }
 445       }
 446     }
 447
 448     lastChunk = null;
 449     return null;
 450   }
 451
 452
 453   public void set (int i, E e) {
 454     Node l1;
 455     ChunkNode l2;
 456     Chunk l3 = lastChunk;
 457     int j;
 458
 459     if (i < 0){
 460       throw new IndexOutOfBoundsException();
 461     }
 462
 463     if (l3 == null || (l3.base != (i & CHUNK_BASEMASK))) { // cache optimization for in-cluster access
 464       j = i >>>  S1;
 465       if ((l1 = root.seg[j]) == null) {         // new L1 -> new L2,L3
 466         l1 = new Node();
 467         root.seg[j] = l1;
 468
 469         j = (i >>> S2) & SEG_MASK;
 470         l2 = new ChunkNode();
 471         l1.seg[j] = l2;
 472
 473         j = (i >>> S3) & SEG_MASK;
 474         l3 = new Chunk(i & ~ELEM_MASK);
 475         sortInChunk(l3);
 476         l2.seg[j] = l3;
 477
 478       } else {                                  // had L1
 479         j = (i >>> S2) & SEG_MASK;
 480         if ((l2 = l1.seg[j]) == null) {         // new L2 -> new L3
 481           l2 = new ChunkNode();
 482           l1.seg[j] = l2;
 483
 484           j = (i >>> S3) & SEG_MASK;
 485           l3 = new Chunk(i & ~ELEM_MASK);
 486           sortInChunk(l3);
 487           l2.seg[j] = l3;
 488
 489         } else {                                // had L2
 490           j = (i >>> S3) & SEG_MASK;
 491           if ((l3 = l2.seg[j]) == null) {       // new L3
 492             l3 = new Chunk(i & ~ELEM_MASK);
 493             sortInChunk(l3);
 494             l2.seg[j] = l3;
 495           }
 496         }
 497       }
 498
 499       lastChunk = l3;
 500     }
 501
 502     j = i & ELEM_MASK;
 503
 504     long[] bm = l3.bitmap;
 505     int u = (j >> 6);    // j / 64 (64 bits per bm entry)
 506     int v = (i & 0x7f);  // index into bm[u] bitset
 507     boolean isSet = ((bm[u] >> v) & 0x1) > 0;
 508
 509     if (trackChanges) {
 510       Entry entry = new Entry(i,l3.elements[j]);
 511       entry.next = changes;
 512       changes = entry;
 513     }
 514
 515     if (e != null) {
 516       if (!isSet) {
 517         l3.elements[j] = e;
 518         bm[u] |= (1L<<v);
 519         nSet++;
 520       }
 521
 522     } else {
 523       if (isSet) {
 524         l3.elements[j] = null;
 525         bm[u] &= ~(1L<<v);
 526         nSet--;
 527         // <2do> discard upwards if chunk is empty ? (maybe as an option)
 528       }
 529     }
 530   }
 531
 532   /**
 533    * find first null element within given range [i, i+length[
 534    * @return -1 if there is none
 535    */
 536   public int firstNullIndex (int i, int length) {
 537     Node l1;
 538     ChunkNode l2;
 539     Chunk l3 = lastChunk;
 540     int j;
 541     int iMax = i + length;
 542
 543     if (l3 == null || (l3.base != (i & CHUNK_BASEMASK))) { // cache optimization for in-cluster access
 544       j = i >>>  S1;
 545       if ((l1 = root.seg[j]) != null) {         // new L1 -> new L2,L3
 546         j = (i >>> S2) & SEG_MASK;
 547         if ((l2 = l1.seg[j]) != null) {         // new L2 -> new L3
 548           j = (i >>> S3) & SEG_MASK;
 549           if ((l3 = l2.seg[j]) == null){
 550             return i; // no such l3 segment -> index is free
 551           }
 552         } else {
 553           return i; // no such l2 segment yet -> index is free
 554         }
 555       } else { // we don't have that root segment yet -> index is free
 556         return i;
 557       }
 558     }
 559
 560     int k = i & SEG_MASK;
 561     while (l3 != null) {
 562       k = l3.nextClearBit(k);
 563
 564       if (k >= 0) {             // Ok, got one in the chunk
 565         lastChunk = l3;
 566         i = l3.base + k;
 567         return (i < iMax) ? i : -1;
 568
 569       } else {                  // chunk full
 570         Chunk l3Next = l3.next;
 571         int nextBase = l3.base + CHUNK_SIZE;
 572         if ((l3Next != null) && (l3Next.base == nextBase)) {
 573           if (nextBase < iMax) {
 574             l3 = l3Next;
 575             k=0;
 576           } else {
 577             return -1;
 578           }
 579         } else {
 580           lastChunk = null;
 581           return (nextBase < iMax) ? nextBase : -1;
 582         }
 583       }
 584     }
 585
 586     // no allocated chunk for 'i'
 587     lastChunk = null;
 588     return i;
 589   }
 590
 591   /**
 592    * deep copy
 593    * we need to do this depth first, right-to-left, to maintain the
 594    * Chunk list ordering. We also compact during cloning, i.e. remove
 595    * empty chunks and ChunkNodes/Nodes w/o descendants
 596    */
 597   public SparseClusterArray<E> deepCopy (Cloner<E> elementCloner) {
 598     SparseClusterArray<E> a = new SparseClusterArray<E>();
 599     a.nSet = nSet;
 600
 601     Node[] newNodeList = a.root.seg;
 602
 603     Node newNode = null;
 604     ChunkNode newChunkNode = null;
 605     Chunk newChunk = null, lastChunk = null;
 606
 607     Node[] nList = root.seg;
 608
 609     try {
 610       for (int i=0, i1=0; i<nList.length; i++) {
 611         Node n = nList[i];
 612         if (n != null) {
 613           ChunkNode[] cnList = n.seg;
 614
 615           for (int j=0, j1=0; j<cnList.length; j++) {
 616             ChunkNode cn = cnList[j];
 617             if (cn != null) {
 618               Chunk[] cList = cn.seg;
 619
 620               for (int k=0, k1=0; k<cList.length; k++) {
 621                 Chunk c = cList[k];
 622
 623                 if (c != null && !c.isEmpty()) {
 624                   newChunk = c.deepCopy(elementCloner);
 625                   if (lastChunk == null) {
 626                     a.head = lastChunk = newChunk;
 627                   } else {
 628                     lastChunk.next = newChunk;
 629                     lastChunk = newChunk;
 630                   }
 631
 632                   // create the required ChunkNode/Node instances
 633                   if (newNode == null) {
 634                     newNode = new Node();
 635                     j1 = k1 = 0;
 636                     newNodeList[i1++] = newNode;
 637                   }
 638
 639                   if (newChunkNode == null) {
 640                     newChunkNode = new ChunkNode();
 641                     newNode.seg[j1++] = newChunkNode;
 642                   }
 643
 644                   newChunkNode.seg[k1++] = newChunk;
 645                 }
 646               }
 647             }
 648             newChunkNode = null;
 649           }
 650         }
 651         newNode = null;
 652       }
 653     } catch (CloneNotSupportedException cnsx) {
 654       return null; // maybe we should re-raise
 655     }
 656
 657     return a;
 658   }
 659
 660   /**
 661    * create a snapshot that can be used to restore a certain state of our array
 662    * This is more suitable than cloning in case the array is very sparse, or
 663    * the elements contain a lot of transient data we don't want to store
 664    */
 665   public <T> Snapshot<E,T> getSnapshot (Transformer<E,T> transformer){
 666     Snapshot<E,T> snap = new Snapshot<E,T>(nSet);
 667     populateSnapshot(snap, transformer);
 668
 669     return snap;
 670   }
 671
 672   protected <T> void populateSnapshot (Snapshot<E,T> snap, Transformer<E,T> transformer){
 673     int n = nSet;
 674
 675     Object[] values = snap.values;
 676     int[] indices = snap.indices;
 677
 678     int j=0;
 679     for (Chunk c = head; c != null; c = c.next) {
 680       int base = c.base;
 681       int i=-1;
 682       while ((i=c.nextSetBit(i+1)) >= 0) {
 683         Object val = transformer.transform((E)c.elements[i]);
 684         values[j] = val;
 685         indices[j] = base + i;
 686
 687         if (++j >= n) {
 688           break;
 689         }
 690       }
 691     }
 692   }
 693
 694   @SuppressWarnings("unchecked")
 695   public <T> void restore (Snapshot<E,T> snap, Transformer<T,E> transformer) {
 696     // <2do> - there are more efficient ways to restore small changes,
 697     // but since snapshot elements are ordered it should be reasonably fast
 698     clear();
 699
 700     T[] values = (T[])snap.values;
 701     int[] indices = snap.indices;
 702     int len = indices.length;
 703
 704     for (int i=0; i<len; i++){
 705       E obj = transformer.transform(values[i]);
 706       int index = indices[i];
 707
 708       set(index,obj);
 709     }
 710   }
 711
 712   public void clear() {
 713     lastChunk = null;
 714     head = null;
 715     root = new Root();
 716     nSet = 0;
 717
 718     changes = null;
 719   }
 720
 721   public void trackChanges () {
 722     trackChanges = true;
 723   }
 724
 725   public void stopTrackingChanges() {
 726     trackChanges = false;
 727   }
 728
 729   public boolean isTrackingChanges() {
 730     return trackChanges;
 731   }
 732
 733   public Entry<E> getChanges() {
 734     return changes;
 735   }
 736
 737   public void resetChanges() {
 738     changes = null;
 739   }
 740
 741   public void revertChanges (Entry<E> changes) {
 742     for (Entry<E> e = changes; e != null; e = e.next) {
 743       set(e.index, e.value);
 744     }
 745   }
 746
 747   @Override
 748   public String toString() {
 749     return "SparseClusterArray [nSet=" + nSet + ']';
 750   }
 751
 752   public int numberOfElements() {
 753     return nSet;
 754   }
 755
 756   public int numberOfChunks() {
 757     // that's only for debugging purposes, we should probably cache
 758     int n = 0;
 759     for (Chunk c = head; c != null; c = c.next) {
 760       n++;
 761     }
 762     return n;
 763   }
 764
 765   //--- iteration over set elements
 766
 767   public IndexIterator getElementIndexIterator () {
 768     return new ElementIndexIterator();
 769   }
 770
 771   public IndexIterator getElementIndexIterator (int fromIndex) {
 772     return new ElementIndexIterator(fromIndex);
 773   }
 774
 775   @Override
 776   public Iterator<E> iterator() {
 777     return new ElementIterator<E>();
 778   }
 779
 780   public int cardinality () {
 781     return nSet;
 782   }
 783 }