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