Java > Open Source Codes > com > caucho > quercus > env > ArrayValueImpl


1 /*
2  * Copyright (c) 1998-2006 Caucho Technology -- all rights reserved
3  *
4  * This file is part of Resin(R) Open Source
5  *
6  * Each copy or derived work must preserve the copyright notice and this
7  * notice unmodified.
8  *
9  * Resin Open Source is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation; either version 2 of the License, or
12  * (at your option) any later version.
13  *
14  * Resin Open Source is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
17  * of NON-INFRINGEMENT. See the GNU General Public License for more
18  * details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with Resin Open Source; if not, write to the
22  *
23  * Free Software Foundation, Inc.
24  * 59 Temple Place, Suite 330
25  * Boston, MA 02111-1307 USA
26  *
27  * @author Scott Ferguson
28  */
29
30 package com.caucho.quercus.env;
31
32 import com.caucho.util.RandomUtil;
33
34 import java.io.IOException ;
35 import java.io.ObjectInputStream ;
36 import java.io.ObjectOutputStream ;
37 import java.io.Serializable ;
38 import java.util.IdentityHashMap ;
39 import java.util.Map ;
40 import java.util.logging.Logger ;
41
42 /**
43  * Represents a PHP array value.
44  */
45 public class ArrayValueImpl extends ArrayValue
46   implements Serializable
47 {
48   private static final Logger log
49     = Logger.getLogger(ArrayValueImpl.class.getName());
50
51   private static final StringValue KEY = new StringValueImpl("key");
52   private static final StringValue VALUE = new StringValueImpl("value");
53   
54   private static final int DEFAULT_SIZE = 16;
55   
56   private static final int SORT_REGULAR = 0;
57   private static final int SORT_NUMERIC = 1;
58   private static final int SORT_STRING = 2;
59   private static final int SORT_LOCALE_STRING = 5;
60   
61   private Entry []_entries;
62   private int _hashMask;
63
64   private int _size;
65   private long _nextAvailableIndex;
66   private boolean _isDirty;
67
68   private Entry _head;
69   private Entry _tail;
70
71   public ArrayValueImpl()
72   {
73     _entries = new Entry[DEFAULT_SIZE];
74     _hashMask = _entries.length - 1;
75   }
76
77   public ArrayValueImpl(int size)
78   {
79     int capacity = DEFAULT_SIZE;
80
81     while (capacity < 4 * size)
82       capacity *= 2;
83     
84     _entries = new Entry[capacity];
85     _hashMask = _entries.length - 1;
86   }
87
88   public ArrayValueImpl(ArrayValue copy)
89   {
90     this(copy.getSize());
91
92     for (Entry ptr = copy.getHead(); ptr != null; ptr = ptr._next) {
93       // php/0662 for copy
94 put(ptr._key, ptr._value.copyArrayItem());
95     }
96   }
97
98   public ArrayValueImpl(ArrayValueImpl copy)
99   {
100     copy._isDirty = true;
101     _isDirty = true;
102     
103     _size = copy._size;
104     _entries = copy._entries;
105     _hashMask = copy._hashMask;
106
107     _head = copy._head;
108     _current = copy._current;
109     _tail = copy._tail;
110     _nextAvailableIndex = copy._nextAvailableIndex;
111   }
112
113   public ArrayValueImpl(Env env,
114             IdentityHashMap <Value,Value> map,
115             ArrayValue copy)
116   {
117     this();
118     
119     map.put(copy, this);
120
121     for (Entry ptr = copy.getHead(); ptr != null; ptr = ptr._next) {
122       put(ptr._key, ptr._value.toValue().copy(env, map));
123     }
124   }
125
126   public ArrayValueImpl(Value []keys, Value []values)
127   {
128     this();
129
130     for (int i = 0; i < keys.length; i++) {
131       if (keys[i] != null)
132     put(keys[i], values[i]);
133       else
134     put(values[i]);
135     }
136   }
137
138   private void copyOnWrite()
139   {
140     if (! _isDirty)
141       return;
142
143     _isDirty = false;
144     
145     Entry []entries = new Entry[_entries.length];
146     
147     Entry prev = null;
148     for (Entry ptr = _head; ptr != null; ptr = ptr._next) {
149       Entry ptrCopy = new Entry(ptr._key, ptr._value.copyArrayItem());
150       
151       entries[ptr._index] = ptrCopy;
152       ptrCopy._index = ptr._index;
153
154       if (prev == null)
155     _head = _current = ptrCopy;
156       else {
157     prev._next = ptrCopy;
158     ptrCopy._prev = prev;
159       }
160
161       prev = ptrCopy;
162     }
163
164     _tail = prev;
165
166     _entries = entries;
167   }
168   
169   /**
170    * Returns the type.
171    */
172   public String getType()
173   {
174     return "array";
175   }
176
177   /**
178    * Converts to a boolean.
179    */
180   public boolean toBoolean()
181   {
182     return _size != 0;
183   }
184   
185   /**
186    * Converts to a string.
187    * @param env
188    */
189   public StringValue toString(Env env)
190   {
191     return new StringValueImpl("Array");
192   }
193   
194   /**
195    * Converts to an object.
196    */
197   public Object toObject()
198   {
199     return null;
200   }
201   
202   /**
203    * Copy for assignment.
204    */
205   public Value copy()
206   {
207     _isDirty = true;
208     
209     return new ArrayValueImpl(this);
210   }
211   
212   /**
213    * Copy for assignment.
214    */
215   public Value copyReturn()
216   {
217     _isDirty = true;
218     
219     return new ArrayValueImpl(this);
220   }
221   
222   /**
223    * Copy for serialization
224    */
225   public Value copy(Env env, IdentityHashMap <Value,Value> map)
226   {
227     Value oldValue = map.get(this);
228
229     if (oldValue != null)
230       return oldValue;
231
232     return new ArrayValueImpl(env, map, this);
233   }
234   
235   /**
236    * Convert to an argument value.
237    */
238   @Override
239   public Value toArgValue()
240   {
241     return copy();
242   }
243   
244   /**
245    * Convert to an argument declared as a reference
246    */
247   @Override
248   public Value toRefValue()
249   {
250     return this;
251   }
252
253   /**
254    * Returns the size.
255    */
256   public int size()
257   {
258     return _size;
259   }
260
261   /**
262    * Returns the size.
263    */
264   public int getSize()
265   {
266     return size();
267   }
268
269   /**
270    * Clears the array
271    */
272   public void clear()
273   {
274     if (_isDirty) {
275       _entries = new Entry[_entries.length];
276       _isDirty = false;
277     }
278     
279     _size = 0;
280     _head = _tail = _current = null;
281
282     _nextAvailableIndex = 0;
283     for (int j = _entries.length - 1; j >= 0; j--) {
284       _entries[j] = null;
285     }
286   }
287
288   /**
289    * Returns true for an array.
290    */
291   public boolean isArray()
292   {
293     return true;
294   }
295   
296   /**
297    * Adds a new value.
298    */
299   public Value put(Value key, Value value)
300   {
301     if (_isDirty)
302       copyOnWrite();
303     
304     Entry entry = createEntry(key);
305
306     // php/0434
307 Value oldValue = entry._value;
308
309     if (value instanceof Var) {
310       // php/0a59
311 Var var = (Var) value;
312       var.setReference();
313
314       entry._value = var;
315     }
316     else if (oldValue instanceof Var) {
317       oldValue.set(value);
318     }
319     else {
320       entry._value = value;
321     }
322
323     return value;
324   }
325
326   /**
327    * Add to the beginning
328    */
329   public ArrayValue unshift(Value value)
330   {
331     if (_isDirty)
332       copyOnWrite();
333     
334     _size++;
335     
336     if (_entries.length <= 2 * _size)
337       expand();
338
339     Value key = createTailKey();
340
341     Entry entry = new Entry(key, value.toArgValue());
342
343     addEntry(entry);
344
345     if (_head != null) {
346       _head._prev = entry;
347       entry._next = _head;
348       _head = entry;
349     }
350     else {
351       _head = _tail = entry;
352     }
353
354     return this;
355   }
356
357   /**
358    * Replace a section of the array.
359    */
360   public ArrayValue splice(int start, int end, ArrayValue replace)
361   {
362     if (_isDirty)
363       copyOnWrite();
364
365     int index = 0;
366
367     ArrayValueImpl result = new ArrayValueImpl();
368
369     Entry ptr = _head;
370     Entry next = null;
371     for (; ptr != null; ptr = next) {
372       next = ptr._next;
373       
374       Value key = ptr.getKey();
375       
376       if (index < start) {
377       }
378       else if (index < end) {
379     _size--;
380     
381     if (ptr._prev != null)
382       ptr._prev._next = ptr._next;
383     else
384       _head = ptr._next;
385     
386     if (ptr._next != null)
387       ptr._next._prev = ptr._prev;
388     else
389       _tail = ptr._prev;
390
391     if (ptr.getKey() instanceof StringValue)
392       result.put(ptr.getKey(), ptr.getValue());
393     else
394       result.put(ptr.getValue());
395       }
396       else if (replace == null) {
397     return result;
398       }
399       else {
400     for (Entry replaceEntry = replace.getHead();
401          replaceEntry != null;
402          replaceEntry = replaceEntry._next) {
403       _size++;
404       
405       if (_entries.length <= 2 * _size)
406         expand();
407
408       Entry entry = new Entry(createTailKey(), replaceEntry.getValue());
409
410       addEntry(entry);
411
412       entry._next = ptr;
413       entry._prev = ptr._prev;
414
415       if (ptr._prev != null)
416         ptr._prev._next = entry;
417       else
418         _head = entry;
419
420       ptr._prev = entry;
421     }
422
423     return result;
424       }
425
426       index++;
427     }
428
429     if (replace != null) {
430       for (Entry replaceEntry = replace.getHead();
431        replaceEntry != null;
432        replaceEntry = replaceEntry._next) {
433     put(replaceEntry.getValue());
434       }
435     }
436
437     return result;
438   }
439
440   /**
441    * Returns the value as an argument which may be a reference.
442    */
443   public Value getArg(Value index)
444   {
445     if (_isDirty) // XXX: needed?
446 copyOnWrite();
447     
448     Entry entry = getEntry(index);
449
450     if (entry != null) {
451       // php/3d48, php/39aj
452 Value arg = entry.toArg();
453
454       return arg;
455     }
456     else {
457       // php/3d49
458 return new ArgGetValue(this, index);
459     }
460   }
461
462   /**
463    * Returns the field value, creating an object if it's unset.
464    */
465   public Value getObject(Env env, Value fieldName)
466   {
467     Value value = get(fieldName);
468
469     if (! value.isset()) {
470       value = env.createObject();
471
472       put(fieldName, value);
473     }
474     
475     return value;
476   }
477
478   /**
479    * Returns the value as an array.
480    */
481   public Value getArray(Value index)
482   {
483     if (_isDirty)
484       copyOnWrite();
485     
486     Value value = get(index);
487
488     Value array = value.toAutoArray();
489     
490     if (value != array) {
491       value = array;
492
493       put(index, value);
494     }
495
496     return value;
497   }
498
499   /**
500    * Returns the value as an array, using copy on write if necessary.
501    */
502   public Value getDirty(Value index)
503   {
504     if (_isDirty)
505       copyOnWrite();
506     
507     return get(index);
508   }
509
510   /**
511    * Add
512    */
513   public Value put(Value value)
514   {
515     if (_isDirty)
516       copyOnWrite();
517     
518     Value key = createTailKey();
519
520     put(key, value);
521
522     return value;
523   }
524
525   /**
526    * Sets the array ref.
527    */
528   public Value putRef()
529   {
530     if (_isDirty)
531       copyOnWrite();
532     
533     // 0d0d
534 Value tailKey = createTailKey();
535     
536     return getRef(tailKey);
537   }
538
539   /**
540    * Creatse a tail index.
541    */
542   public Value createTailKey()
543   {
544     return LongValue.create(_nextAvailableIndex);
545   }
546
547   /**
548    * Gets a new value.
549    */
550   public Value get(Value key)
551   {
552     int capacity = _entries.length;
553
554     key = key.toKey();
555
556     int hashMask = _hashMask;
557     int hash = key.hashCode() & hashMask;
558
559     int count = capacity;
560     for (; count >= 0; count--) {
561       Entry entry = _entries[hash];
562
563       if (entry == null)
564     return UnsetValue.UNSET;
565       else if (key.equals(entry._key))
566     return entry._value.toValue(); // quercus/39a1
567
568       hash = (hash + 1) & hashMask;
569     }
570
571     return UnsetValue.UNSET;
572   }
573
574   /**
575    * Gets a new value.
576    */
577   public Value containsKey(Value key)
578   {
579     Entry entry = getEntry(key);
580
581     if (entry != null)
582       return entry.getValue();
583     else
584       return null;
585   }
586
587   /**
588    * Gets a new value.
589    */
590   private Entry getEntry(Value key)
591   {
592     int capacity = _entries.length;
593
594     key = key.toKey();
595
596     int hash = key.hashCode() & _hashMask;
597
598     int count = capacity;
599     for (; count >= 0; count--) {
600       Entry entry = _entries[hash];
601
602       if (entry == null)
603     return null;
604       else if (key.equals(entry._key))
605     return entry;
606
607       hash = (hash + 1) & _hashMask;
608     }
609
610     return null;
611   }
612
613   /**
614    * Removes a value.
615    */
616   public Value remove(Value key)
617   {
618     if (_isDirty)
619       copyOnWrite();
620     
621     int capacity = _entries.length;
622
623     key = key.toKey();
624
625     int hash = key.hashCode() & _hashMask;
626
627     int count = capacity;
628     for (; count >= 0; count--) {
629       Entry entry = _entries[hash];
630
631       if (entry == null)
632     return UnsetValue.UNSET;
633       else if (key.equals(entry._key)) {
634     if (entry._prev != null)
635       entry._prev._next = entry._next;
636     else
637       _head = entry._next;
638     
639     if (entry._next != null)
640       entry._next._prev = entry._prev;
641     else
642       _tail = entry._prev;
643
644     entry._prev = null;
645     entry._next = null;
646
647     _current = _head;
648
649     _size--;
650
651     Value value = entry.getValue();
652
653     _entries[hash] = null;
654     shiftEntries(hash + 1);
655
656     if (key instanceof LongValue
657         && key.toLong() + 1 == _nextAvailableIndex) {
658       updateNextAvailableIndex();
659     }
660
661     return value;
662       }
663
664       hash = (hash + 1) & _hashMask;
665     }
666     
667     return UnsetValue.UNSET;
668   }
669
670   /**
671    * Shift entries after a delete.
672    */
673   private void shiftEntries(int index)
674   {
675     int capacity = _entries.length;
676
677     for (; index < capacity; index++) {
678       Entry entry = _entries[index];
679
680       if (entry == null)
681     return;
682
683       _entries[index] = null;
684
685       addEntry(entry);
686     }
687   }
688
689   /**
690    * Returns the array ref.
691    */
692   public Var getRef(Value index)
693   {
694     if (_isDirty)
695       copyOnWrite();
696     
697     Entry entry = createEntry(index);
698     // quercus/0431
699 Value value = entry._value;
700
701     if (value instanceof Var)
702       return (Var) value;
703
704     Var var = new Var(value);
705
706     entry.setValue(var);
707     
708     return var;
709   }
710
711   /**
712    * Creates the entry for a key.
713    */
714   private Entry createEntry(Value key)
715   {
716     // XXX: "A key may be either an integer or a string. If a key is
717 // the standard representation of an integer, it will be
718 // interpreted as such (i.e. "8" will be interpreted as 8,
719 // while "08" will be interpreted as "08")."
720 //
721 // http://us3.php.net/types.array
722
723     if (_isDirty)
724       copyOnWrite();
725     
726     int capacity = _entries.length;
727
728     key = key.toKey();
729     
730     int hashMask = _hashMask;
731
732     int hash = key.hashCode() & hashMask;
733
734     int count = capacity;
735     for (; count >= 0; count--) {
736       Entry entry = _entries[hash];
737
738       if (entry == null)
739     break;
740       else if (key.equals(entry._key))
741     return entry;
742
743       hash = (hash + 1) & hashMask;
744     }
745     
746     _size++;
747
748     Entry newEntry = new Entry(key);
749     updateNextAvailableIndex(newEntry);
750     _entries[hash] = newEntry;
751     newEntry._index = hash;
752
753     if (_head == null) {
754       newEntry._prev = null;
755       newEntry._next = null;
756       
757       _head = newEntry;
758       _tail = newEntry;
759       _current = newEntry;
760     }
761     else {
762       newEntry._prev = _tail;
763       newEntry._next = null;
764       
765       _tail._next = newEntry;
766       _tail = newEntry;
767     }
768
769     if (_entries.length <= 2 * _size)
770       expand();
771
772     return newEntry;
773   }
774
775   private void expand()
776   {
777     Entry []entries = _entries;
778     
779     _entries = new Entry[2 * entries.length];
780     _hashMask = _entries.length - 1;
781
782     for (Entry entry = _head; entry != null; entry = entry._next) {
783       addEntry(entry);
784     }
785   }
786
787   private void addEntry(Entry entry)
788   {
789     int capacity = _entries.length;
790
791     int hash = entry._key.hashCode() & _hashMask;
792
793     for (int i = capacity; i >= 0; i--) {
794       if (_entries[hash] == null) {
795     _entries[hash] = entry;
796     updateNextAvailableIndex(entry);
797     entry._index = hash;
798     return;
799       }
800
801       hash = (hash + 1) & _hashMask;
802     }
803   }
804
805   /**
806    * Updates _nextAvailableIndex on a remove of the highest value
807    */
808   private void updateNextAvailableIndex()
809   {
810     _nextAvailableIndex = 0;
811
812     for (Entry entry = _head; entry != null; entry = entry._next) {
813       updateNextAvailableIndex(entry);
814     }
815   }
816
817   /**
818    * Updates _nextAvailableIndex; this must be invoked for every insertion
819    */
820   private void updateNextAvailableIndex(Entry entry)
821   {
822     if (entry._key instanceof LongValue) {
823       long key = entry._key.toLong();
824     
825       if (_nextAvailableIndex <= key)
826     _nextAvailableIndex = key + 1;
827     }
828   }
829
830
831   /**
832    * Pops the top value.
833    */
834   public Value pop()
835   {
836     if (_isDirty)
837       copyOnWrite();
838     
839     if (_tail != null) {
840       Value value = remove(_tail._key);
841       
842       return value;
843     }
844     else
845       return BooleanValue.FALSE;
846   }
847
848   public Entry getHead()
849   {
850     return _head;
851   }
852
853   protected Entry getTail()
854   {
855     return _tail;
856   }
857
858   /**
859    * Shuffles the array
860    */
861   public void shuffle()
862   {
863     if (_isDirty)
864       copyOnWrite();
865     
866     Entry []values = new Entry[size()];
867
868     int length = values.length;
869
870     if (length == 0)
871       return;
872
873     int i = 0;
874     for (Entry ptr = _head; ptr != null; ptr = ptr._next)
875       values[i++] = ptr;
876
877     for (i = 0; i < length; i++) {
878       int rand = RandomUtil.nextInt(length);
879
880       Entry temp = values[rand];
881       values[rand] = values[i];
882       values[i] = temp;
883     }
884
885     _head = values[0];
886     _head._prev = null;
887     
888     _tail = values[values.length - 1];
889     _tail._next = null;
890     
891     for (i = 0; i < length; i++) {
892       if (i > 0)
893     values[i]._prev = values[i - 1];
894       if (i < length - 1)
895     values[i]._next = values[i + 1];
896     }
897
898     _current = _head;
899   }
900
901   //
902 // Java serialization code
903 //
904
905   private void writeObject(ObjectOutputStream out)
906     throws IOException
907   {
908     out.writeInt(_size);
909     
910     for (Map.Entry <Value,Value> entry : entrySet()) {
911       out.writeObject(entry.getKey());
912       out.writeObject(entry.getValue());
913     }
914   }
915   
916   private void readObject(ObjectInputStream in)
917     throws ClassNotFoundException , IOException
918   {
919     int size = in.readInt();
920     
921     int capacity = DEFAULT_SIZE;
922
923     while (capacity < 4 * size) {
924       capacity *= 2;
925     }
926
927     _entries = new Entry[capacity];
928     _hashMask = _entries.length - 1;
929
930     for (int i = 0; i < size; i++) {
931       put((Value) in.readObject(), (Value) in.readObject());
932     }
933   }
934
935 }
936
937

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags