You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2009/07/30 17:30:27 UTC

svn commit: r799331 [18/29] - in /incubator/cassandra/trunk: ./ src/java/org/apache/cassandra/concurrent/ src/java/org/apache/cassandra/config/ src/java/org/apache/cassandra/db/ src/java/org/apache/cassandra/dht/ src/java/org/apache/cassandra/gms/ src/...

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/io/SequenceFile.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/io/SequenceFile.java?rev=799331&r1=799330&r2=799331&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/io/SequenceFile.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/io/SequenceFile.java Thu Jul 30 15:30:21 2009
@@ -1,545 +1,545 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.cassandra.io;
-
-import java.io.*;
-import java.util.*;
-
-import org.apache.cassandra.config.DatabaseDescriptor;
-import org.apache.cassandra.utils.BloomFilter;
-import org.apache.cassandra.db.marshal.AbstractType;
-
-import org.apache.log4j.Logger;
-import org.apache.commons.lang.ArrayUtils;
-
-/**
- * This class writes key/value pairs sequentially to disk. It is
- * also used to read sequentially from disk. However one could
- * jump to random positions to read data from the file. This class
- * also has many implementations of the IFileWriter and IFileReader
- * interfaces which are exposed through factory methods.
- */
-
-public class SequenceFile
-{
-    /**
-     *  This is a reader that finds the block for a starting column and returns
-     *  blocks before/after it for each next call. This function assumes that
-     *  the CF is sorted by name and exploits the name index.
-     */
-    public static class ColumnGroupReader extends BufferReader
-    {
-        private String key_;
-        private String cfName_;
-        private String cfType_;
-        private AbstractType comparator_;
-        private String subComparatorName_;
-        private boolean isAscending_;
-
-        private List<IndexHelper.ColumnIndexInfo> columnIndexList_;
-        private long columnStartPosition_;
-        private int curRangeIndex_;
-        private int allColumnsSize_;
-        private int localDeletionTime_;
-        private long markedForDeleteAt_;
-
-        ColumnGroupReader(String filename, String key, String cfName, AbstractType comparator, byte[] startColumn, boolean isAscending, long position) throws IOException
-        {
-            super(filename, 128 * 1024);
-            this.cfName_ = cfName;
-            this.comparator_ = comparator;
-            this.subComparatorName_ = DatabaseDescriptor.getSubComparator(SSTableReader.parseTableName(filename), cfName).getClass().getCanonicalName();
-            this.key_ = key;
-            this.isAscending_ = isAscending;
-            init(startColumn, position);
-        }
-
-        /**
-         *   Build a list of index entries ready for search.
-         */
-        private List<IndexHelper.ColumnIndexInfo> getFullColumnIndexList(List<IndexHelper.ColumnIndexInfo> columnIndexList, int totalNumCols)
-        {
-            if (columnIndexList.size() == 0)
-            {
-                /* if there is no column index, add an index entry that covers the full space. */
-                return Arrays.asList(new IndexHelper.ColumnIndexInfo(ArrayUtils.EMPTY_BYTE_ARRAY, 0, totalNumCols, comparator_));
-            }
-
-            List<IndexHelper.ColumnIndexInfo> fullColIndexList = new ArrayList<IndexHelper.ColumnIndexInfo>();
-            int accumulatededCols = 0;
-            for (IndexHelper.ColumnIndexInfo colPosInfo : columnIndexList)
-                accumulatededCols += colPosInfo.count();
-            int remainingCols = totalNumCols - accumulatededCols;
-
-            fullColIndexList.add(new IndexHelper.ColumnIndexInfo(ArrayUtils.EMPTY_BYTE_ARRAY, 0, columnIndexList.get(0).count(), comparator_));
-            for (int i = 0; i < columnIndexList.size() - 1; i++)
-            {
-                IndexHelper.ColumnIndexInfo colPosInfo = columnIndexList.get(i);
-                fullColIndexList.add(new IndexHelper.ColumnIndexInfo(colPosInfo.name(),
-                                                                     colPosInfo.position(),
-                                                                     columnIndexList.get(i + 1).count(),
-                                                                     comparator_));
-            }
-            byte[] columnName = columnIndexList.get(columnIndexList.size() - 1).name();
-            fullColIndexList.add(new IndexHelper.ColumnIndexInfo(columnName,
-                                                                 columnIndexList.get(columnIndexList.size() - 1).position(),
-                                                                 remainingCols,
-                                                                 comparator_));
-            return fullColIndexList;
-        }
-
-        private void init(byte[] startColumn, long position) throws IOException
-        {
-            String keyInDisk = null;
-            if (seekTo(position) >= 0)
-                keyInDisk = file_.readUTF();
-
-            if ( keyInDisk != null && keyInDisk.equals(key_))
-            {
-                /* read off the size of this row */
-                int dataSize = file_.readInt();
-                /* skip the bloomfilter */
-                int totalBytesRead = IndexHelper.skipBloomFilter(file_);
-                /* read off the index flag, it has to be true */
-                boolean hasColumnIndexes = file_.readBoolean();
-                totalBytesRead += 1;
-
-                /* read the index */
-                List<IndexHelper.ColumnIndexInfo> colIndexList = new ArrayList<IndexHelper.ColumnIndexInfo>();
-                if (hasColumnIndexes)
-                    totalBytesRead += IndexHelper.deserializeIndex(getTableName(), cfName_, file_, colIndexList);
-
-                /* need to do two things here.
-                 * 1. move the file pointer to the beginning of the list of stored columns
-                 * 2. calculate the size of all columns */
-                String cfName = file_.readUTF();
-                cfType_ = file_.readUTF();
-                String comparatorName = file_.readUTF();
-                assert comparatorName.equals(comparator_.getClass().getCanonicalName());
-                String subComparatorName = file_.readUTF(); // subcomparator
-                localDeletionTime_ = file_.readInt();
-                markedForDeleteAt_ = file_.readLong();
-                int totalNumCols = file_.readInt();
-                allColumnsSize_ = dataSize - (totalBytesRead + 4 * utfPrefix_ + cfName.length() + cfType_.length() + comparatorName.length() + subComparatorName.length() + 4 + 8 + 4);
-
-                columnStartPosition_ = file_.getFilePointer();
-                columnIndexList_ = getFullColumnIndexList(colIndexList, totalNumCols);
-
-                int index = Collections.binarySearch(columnIndexList_, new IndexHelper.ColumnIndexInfo(startColumn, 0, 0, comparator_));
-                curRangeIndex_ = index < 0 ? (++index) * (-1) - 1 : index;
-            }
-            else
-            {
-                /* no keys found in this file because of a false positive in BF */
-                curRangeIndex_ = -1;
-                columnIndexList_ = new ArrayList<IndexHelper.ColumnIndexInfo>();
-            }
-        }
-
-        private boolean getBlockFromCurIndex(DataOutputBuffer bufOut) throws IOException
-        {
-            if (curRangeIndex_ < 0 || curRangeIndex_ >= columnIndexList_.size())
-                return false;
-            IndexHelper.ColumnIndexInfo curColPostion = columnIndexList_.get(curRangeIndex_);
-            long start = curColPostion.position();
-            long end = curRangeIndex_ < columnIndexList_.size() - 1
-                       ? columnIndexList_.get(curRangeIndex_+1).position()
-                       : allColumnsSize_;
-
-            /* seek to the correct offset to the data, and calculate the data size */
-            file_.seek(columnStartPosition_ + start);
-            long dataSize = end - start;
-
-            bufOut.reset();
-            // write CF info
-            bufOut.writeUTF(cfName_);
-            bufOut.writeUTF(cfType_);
-            bufOut.writeUTF(comparator_.getClass().getCanonicalName());
-            bufOut.writeUTF(subComparatorName_);
-            bufOut.writeInt(localDeletionTime_);
-            bufOut.writeLong(markedForDeleteAt_);
-            // now write the columns
-            bufOut.writeInt(curColPostion.count());
-            bufOut.write(file_, (int)dataSize);
-            return true;
-        }
-
-        public boolean getNextBlock(DataOutputBuffer outBuf) throws IOException
-        {
-            boolean result = getBlockFromCurIndex(outBuf);
-            if (isAscending_)
-                curRangeIndex_++;
-            else
-                curRangeIndex_--;
-            return result;
-        }
-    }
-
-    public static abstract class AbstractReader implements IFileReader
-    {
-        private static final short utfPrefix_ = 2;
-        protected RandomAccessFile file_;
-        protected String filename_;
-
-        AbstractReader(String filename)
-        {
-            filename_ = filename;
-        }
-
-        String getTableName()
-        {
-            return SSTable.parseTableName(filename_);
-        }
-
-        public String getFileName()
-        {
-            return filename_;
-        }
-
-        long seekTo(long position) throws IOException
-        {
-            if (position >= 0)
-                seek(position);
-            return position;
-        }
-
-        /**
-         * Defreeze the bloom filter.
-         *
-         * @return bloom filter summarizing the column information
-         * @throws IOException
-         */
-        private BloomFilter defreezeBloomFilter() throws IOException
-        {
-            int size = file_.readInt();
-            byte[] bytes = new byte[size];
-            file_.readFully(bytes);
-            DataInputBuffer bufIn = new DataInputBuffer();
-            bufIn.reset(bytes, bytes.length);
-            BloomFilter bf = BloomFilter.serializer().deserialize(bufIn);
-            return bf;
-        }
-
-        /**
-         * Reads the column name indexes if present. If the
-         * indexes are based on time then skip over them.
-         *
-         * @param cfName
-         * @return
-         */
-        private int handleColumnNameIndexes(String cfName, List<IndexHelper.ColumnIndexInfo> columnIndexList) throws IOException
-        {
-            /* check if we have an index */
-            boolean hasColumnIndexes = file_.readBoolean();
-            int totalBytesRead = 1;
-            /* if we do then deserialize the index */
-            if (hasColumnIndexes)
-            {
-                String tableName = getTableName();
-                /* read the index */
-                totalBytesRead += IndexHelper.deserializeIndex(tableName, cfName, file_, columnIndexList);
-            }
-            return totalBytesRead;
-        }
-
-        /**
-         * This method dumps the next key/value into the DataOuputStream
-         * passed in. Always use this method to query for application
-         * specific data as it will have indexes.
-         *
-         * @param key       key we are interested in.
-         * @param bufOut    DataOutputStream that needs to be filled.
-         * @param columnFamilyName name of the columnFamily
-         * @param columnNames columnNames we are interested in
-         */
-        public long next(String key, DataOutputBuffer bufOut, String columnFamilyName, SortedSet<byte[]> columnNames, long position) throws IOException
-        {
-            assert columnNames != null;
-
-            long bytesRead = -1L;
-            if (isEOF() || seekTo(position) < 0)
-                return bytesRead;
-
-            /* note the position where the key starts */
-            long startPosition = file_.getFilePointer();
-            String keyInDisk = file_.readUTF();
-            if (keyInDisk != null)
-            {
-                /*
-                 * If key on disk is greater than requested key
-                 * we can bail out since we exploit the property
-                 * of the SSTable format.
-                */
-                if (keyInDisk.compareTo(key) > 0)
-                    return bytesRead;
-
-                /*
-                 * If we found the key then we populate the buffer that
-                 * is passed in. If not then we skip over this key and
-                 * position ourselves to read the next one.
-                */
-                if (keyInDisk.equals(key))
-                {
-                    readColumns(key, bufOut, columnFamilyName, columnNames);
-                }
-                else
-                {
-                    /* skip over data portion */
-                    int dataSize = file_.readInt();
-                    file_.seek(dataSize + file_.getFilePointer());
-                }
-
-                long endPosition = file_.getFilePointer();
-                bytesRead = endPosition - startPosition;
-            }
-
-            return bytesRead;
-        }
-
-        private void readColumns(String key, DataOutputBuffer bufOut, String columnFamilyName, SortedSet<byte[]> cNames)
-        throws IOException
-        {
-            int dataSize = file_.readInt();
-
-            /* write the key into buffer */
-            bufOut.writeUTF(key);
-
-            /* if we need to read the all the columns do not read the column indexes */
-            if (cNames == null || cNames.size() == 0)
-            {
-                int bytesSkipped = IndexHelper.skipBloomFilterAndIndex(file_);
-                /*
-                       * read the correct number of bytes for the column family and
-                       * write data into buffer
-                      */
-                dataSize -= bytesSkipped;
-                /* write the data size */
-                bufOut.writeInt(dataSize);
-                /* write the data into buffer, except the boolean we have read */
-                bufOut.write(file_, dataSize);
-            }
-            else
-            {
-                /* Read the bloom filter summarizing the columns */
-                long preBfPos = file_.getFilePointer();
-                BloomFilter bf = defreezeBloomFilter();
-                long postBfPos = file_.getFilePointer();
-                dataSize -= (postBfPos - preBfPos);
-
-                List<IndexHelper.ColumnIndexInfo> columnIndexList = new ArrayList<IndexHelper.ColumnIndexInfo>();
-                /* read the column name indexes if present */
-                int totalBytesRead = handleColumnNameIndexes(columnFamilyName, columnIndexList);
-                dataSize -= totalBytesRead;
-
-                /* read the column family name */
-                String cfName = file_.readUTF();
-                dataSize -= (utfPrefix_ + cfName.length());
-
-                String cfType = file_.readUTF();
-                dataSize -= (utfPrefix_ + cfType.length());
-
-                String comparatorName = file_.readUTF();
-                dataSize -= (utfPrefix_ + comparatorName.length());
-
-                String subComparatorName = file_.readUTF();
-                dataSize -= (utfPrefix_ + subComparatorName.length());
-
-                /* read local deletion time */
-                int localDeletionTime = file_.readInt();
-                dataSize -=4;
-
-                /* read if this cf is marked for delete */
-                long markedForDeleteAt = file_.readLong();
-                dataSize -= 8;
-
-                /* read the total number of columns */
-                int totalNumCols = file_.readInt();
-                dataSize -= 4;
-
-                // TODO: this is name sorted - but eventually this should be sorted by the same criteria as the col index
-                /* get the various column ranges we have to read */
-                List<IndexHelper.ColumnRange> columnRanges = IndexHelper.getMultiColumnRangesFromNameIndex(cNames, columnIndexList, dataSize, totalNumCols);
-
-                /* calculate the data size */
-                int numColsReturned = 0;
-                int dataSizeReturned = 0;
-                for (IndexHelper.ColumnRange columnRange : columnRanges)
-                {
-                    numColsReturned += columnRange.count();
-                    Coordinate coordinate = columnRange.coordinate();
-                    dataSizeReturned += coordinate.end_ - coordinate.start_;
-                }
-
-                // returned data size
-                bufOut.writeInt(dataSizeReturned + utfPrefix_ * 4 + cfName.length() + cfType.length() + comparatorName.length() + subComparatorName.length() + 4 + 4 + 8 + 4);
-                // echo back the CF data we read
-                bufOut.writeUTF(cfName);
-                bufOut.writeUTF(cfType);
-                bufOut.writeUTF(comparatorName);
-                bufOut.writeUTF(subComparatorName);
-                bufOut.writeInt(localDeletionTime);
-                bufOut.writeLong(markedForDeleteAt);
-                /* write number of columns */
-                bufOut.writeInt(numColsReturned);
-                int prevPosition = 0;
-                /* now write all the columns we are required to write */
-                for (IndexHelper.ColumnRange columnRange : columnRanges)
-                {
-                    /* seek to the correct offset to the data */
-                    Coordinate coordinate = columnRange.coordinate();
-                    file_.skipBytes((int) (coordinate.start_ - prevPosition));
-                    bufOut.write(file_, (int) (coordinate.end_ - coordinate.start_));
-                    prevPosition = (int) coordinate.end_;
-                }
-            }
-        }
-
-        /**
-         * This method dumps the next key/value into the DataOuputStream
-         * passed in.
-         *
-         * @param bufOut DataOutputStream that needs to be filled.
-         * @return total number of bytes read/considered
-         */
-        public long next(DataOutputBuffer bufOut) throws IOException
-        {
-            long bytesRead = -1L;
-            if (isEOF())
-                return bytesRead;
-
-            long startPosition = file_.getFilePointer();
-            String key = file_.readUTF();
-            if (key != null)
-            {
-                /* write the key into buffer */
-                bufOut.writeUTF(key);
-                int dataSize = file_.readInt();
-                /* write data size into buffer */
-                bufOut.writeInt(dataSize);
-                /* write the data into buffer */
-                bufOut.write(file_, dataSize);
-                long endPosition = file_.getFilePointer();
-                bytesRead = endPosition - startPosition;
-            }
-
-            return bytesRead;
-        }
-    }
-
-    public static class Reader extends AbstractReader
-    {
-        Reader(String filename) throws IOException
-        {
-            super(filename);
-            init(filename);
-        }
-
-        protected void init(String filename) throws IOException
-        {
-            file_ = new RandomAccessFile(filename, "r");
-        }
-
-        public long getEOF() throws IOException
-        {
-            return file_.length();
-        }
-
-        public long getCurrentPosition() throws IOException
-        {
-            return file_.getFilePointer();
-        }
-
-        public boolean isHealthyFileDescriptor() throws IOException
-        {
-            return file_.getFD().valid();
-        }
-
-        public void seek(long position) throws IOException
-        {
-            file_.seek(position);
-        }
-
-        public boolean isEOF() throws IOException
-        {
-            return (getCurrentPosition() == getEOF());
-        }
-
-        /**
-         * Be extremely careful while using this API. This currently
-         * used to read the commit log header from the commit logs.
-         * Treat this as an internal API.
-         *
-         * @param bytes read from the buffer into the this array
-         */
-        public void readDirect(byte[] bytes) throws IOException
-        {
-            file_.readFully(bytes);
-        }
-
-        public long readLong() throws IOException
-        {
-            return file_.readLong();
-        }
-
-        public void close() throws IOException
-        {
-            file_.close();
-        }
-    }
-
-    public static class BufferReader extends Reader
-    {
-        private int size_;
-
-        BufferReader(String filename, int size) throws IOException
-        {
-            super(filename);
-            size_ = size;
-        }
-
-        protected void init(String filename) throws IOException
-        {
-            file_ = new BufferedRandomAccessFile(filename, "r", size_);
-        }
-    }
-
-    private static Logger logger_ = Logger.getLogger(SequenceFile.class);
-    public static final short utfPrefix_ = 2;
-    public static final String marker_ = "Bloom-Filter";
-
-    public static AbstractWriter writer(String filename) throws IOException
-    {
-        return new AbstractWriter.Writer(filename);
-    }
-
-    public static AbstractWriter bufferedWriter(String filename, int size) throws IOException
-    {
-        return new AbstractWriter.BufferWriter(filename, size);
-    }
-
-    public static IFileReader reader(String filename) throws IOException
-    {
-        return new Reader(filename);
-    }
-
-    public static IFileReader bufferedReader(String filename, int size) throws IOException
-    {
-        return new BufferReader(filename, size);
-    }
-}
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.cassandra.io;
+
+import java.io.*;
+import java.util.*;
+
+import org.apache.cassandra.config.DatabaseDescriptor;
+import org.apache.cassandra.utils.BloomFilter;
+import org.apache.cassandra.db.marshal.AbstractType;
+
+import org.apache.log4j.Logger;
+import org.apache.commons.lang.ArrayUtils;
+
+/**
+ * This class writes key/value pairs sequentially to disk. It is
+ * also used to read sequentially from disk. However one could
+ * jump to random positions to read data from the file. This class
+ * also has many implementations of the IFileWriter and IFileReader
+ * interfaces which are exposed through factory methods.
+ */
+
+public class SequenceFile
+{
+    /**
+     *  This is a reader that finds the block for a starting column and returns
+     *  blocks before/after it for each next call. This function assumes that
+     *  the CF is sorted by name and exploits the name index.
+     */
+    public static class ColumnGroupReader extends BufferReader
+    {
+        private String key_;
+        private String cfName_;
+        private String cfType_;
+        private AbstractType comparator_;
+        private String subComparatorName_;
+        private boolean isAscending_;
+
+        private List<IndexHelper.ColumnIndexInfo> columnIndexList_;
+        private long columnStartPosition_;
+        private int curRangeIndex_;
+        private int allColumnsSize_;
+        private int localDeletionTime_;
+        private long markedForDeleteAt_;
+
+        ColumnGroupReader(String filename, String key, String cfName, AbstractType comparator, byte[] startColumn, boolean isAscending, long position) throws IOException
+        {
+            super(filename, 128 * 1024);
+            this.cfName_ = cfName;
+            this.comparator_ = comparator;
+            this.subComparatorName_ = DatabaseDescriptor.getSubComparator(SSTableReader.parseTableName(filename), cfName).getClass().getCanonicalName();
+            this.key_ = key;
+            this.isAscending_ = isAscending;
+            init(startColumn, position);
+        }
+
+        /**
+         *   Build a list of index entries ready for search.
+         */
+        private List<IndexHelper.ColumnIndexInfo> getFullColumnIndexList(List<IndexHelper.ColumnIndexInfo> columnIndexList, int totalNumCols)
+        {
+            if (columnIndexList.size() == 0)
+            {
+                /* if there is no column index, add an index entry that covers the full space. */
+                return Arrays.asList(new IndexHelper.ColumnIndexInfo(ArrayUtils.EMPTY_BYTE_ARRAY, 0, totalNumCols, comparator_));
+            }
+
+            List<IndexHelper.ColumnIndexInfo> fullColIndexList = new ArrayList<IndexHelper.ColumnIndexInfo>();
+            int accumulatededCols = 0;
+            for (IndexHelper.ColumnIndexInfo colPosInfo : columnIndexList)
+                accumulatededCols += colPosInfo.count();
+            int remainingCols = totalNumCols - accumulatededCols;
+
+            fullColIndexList.add(new IndexHelper.ColumnIndexInfo(ArrayUtils.EMPTY_BYTE_ARRAY, 0, columnIndexList.get(0).count(), comparator_));
+            for (int i = 0; i < columnIndexList.size() - 1; i++)
+            {
+                IndexHelper.ColumnIndexInfo colPosInfo = columnIndexList.get(i);
+                fullColIndexList.add(new IndexHelper.ColumnIndexInfo(colPosInfo.name(),
+                                                                     colPosInfo.position(),
+                                                                     columnIndexList.get(i + 1).count(),
+                                                                     comparator_));
+            }
+            byte[] columnName = columnIndexList.get(columnIndexList.size() - 1).name();
+            fullColIndexList.add(new IndexHelper.ColumnIndexInfo(columnName,
+                                                                 columnIndexList.get(columnIndexList.size() - 1).position(),
+                                                                 remainingCols,
+                                                                 comparator_));
+            return fullColIndexList;
+        }
+
+        private void init(byte[] startColumn, long position) throws IOException
+        {
+            String keyInDisk = null;
+            if (seekTo(position) >= 0)
+                keyInDisk = file_.readUTF();
+
+            if ( keyInDisk != null && keyInDisk.equals(key_))
+            {
+                /* read off the size of this row */
+                int dataSize = file_.readInt();
+                /* skip the bloomfilter */
+                int totalBytesRead = IndexHelper.skipBloomFilter(file_);
+                /* read off the index flag, it has to be true */
+                boolean hasColumnIndexes = file_.readBoolean();
+                totalBytesRead += 1;
+
+                /* read the index */
+                List<IndexHelper.ColumnIndexInfo> colIndexList = new ArrayList<IndexHelper.ColumnIndexInfo>();
+                if (hasColumnIndexes)
+                    totalBytesRead += IndexHelper.deserializeIndex(getTableName(), cfName_, file_, colIndexList);
+
+                /* need to do two things here.
+                 * 1. move the file pointer to the beginning of the list of stored columns
+                 * 2. calculate the size of all columns */
+                String cfName = file_.readUTF();
+                cfType_ = file_.readUTF();
+                String comparatorName = file_.readUTF();
+                assert comparatorName.equals(comparator_.getClass().getCanonicalName());
+                String subComparatorName = file_.readUTF(); // subcomparator
+                localDeletionTime_ = file_.readInt();
+                markedForDeleteAt_ = file_.readLong();
+                int totalNumCols = file_.readInt();
+                allColumnsSize_ = dataSize - (totalBytesRead + 4 * utfPrefix_ + cfName.length() + cfType_.length() + comparatorName.length() + subComparatorName.length() + 4 + 8 + 4);
+
+                columnStartPosition_ = file_.getFilePointer();
+                columnIndexList_ = getFullColumnIndexList(colIndexList, totalNumCols);
+
+                int index = Collections.binarySearch(columnIndexList_, new IndexHelper.ColumnIndexInfo(startColumn, 0, 0, comparator_));
+                curRangeIndex_ = index < 0 ? (++index) * (-1) - 1 : index;
+            }
+            else
+            {
+                /* no keys found in this file because of a false positive in BF */
+                curRangeIndex_ = -1;
+                columnIndexList_ = new ArrayList<IndexHelper.ColumnIndexInfo>();
+            }
+        }
+
+        private boolean getBlockFromCurIndex(DataOutputBuffer bufOut) throws IOException
+        {
+            if (curRangeIndex_ < 0 || curRangeIndex_ >= columnIndexList_.size())
+                return false;
+            IndexHelper.ColumnIndexInfo curColPostion = columnIndexList_.get(curRangeIndex_);
+            long start = curColPostion.position();
+            long end = curRangeIndex_ < columnIndexList_.size() - 1
+                       ? columnIndexList_.get(curRangeIndex_+1).position()
+                       : allColumnsSize_;
+
+            /* seek to the correct offset to the data, and calculate the data size */
+            file_.seek(columnStartPosition_ + start);
+            long dataSize = end - start;
+
+            bufOut.reset();
+            // write CF info
+            bufOut.writeUTF(cfName_);
+            bufOut.writeUTF(cfType_);
+            bufOut.writeUTF(comparator_.getClass().getCanonicalName());
+            bufOut.writeUTF(subComparatorName_);
+            bufOut.writeInt(localDeletionTime_);
+            bufOut.writeLong(markedForDeleteAt_);
+            // now write the columns
+            bufOut.writeInt(curColPostion.count());
+            bufOut.write(file_, (int)dataSize);
+            return true;
+        }
+
+        public boolean getNextBlock(DataOutputBuffer outBuf) throws IOException
+        {
+            boolean result = getBlockFromCurIndex(outBuf);
+            if (isAscending_)
+                curRangeIndex_++;
+            else
+                curRangeIndex_--;
+            return result;
+        }
+    }
+
+    public static abstract class AbstractReader implements IFileReader
+    {
+        private static final short utfPrefix_ = 2;
+        protected RandomAccessFile file_;
+        protected String filename_;
+
+        AbstractReader(String filename)
+        {
+            filename_ = filename;
+        }
+
+        String getTableName()
+        {
+            return SSTable.parseTableName(filename_);
+        }
+
+        public String getFileName()
+        {
+            return filename_;
+        }
+
+        long seekTo(long position) throws IOException
+        {
+            if (position >= 0)
+                seek(position);
+            return position;
+        }
+
+        /**
+         * Defreeze the bloom filter.
+         *
+         * @return bloom filter summarizing the column information
+         * @throws IOException
+         */
+        private BloomFilter defreezeBloomFilter() throws IOException
+        {
+            int size = file_.readInt();
+            byte[] bytes = new byte[size];
+            file_.readFully(bytes);
+            DataInputBuffer bufIn = new DataInputBuffer();
+            bufIn.reset(bytes, bytes.length);
+            BloomFilter bf = BloomFilter.serializer().deserialize(bufIn);
+            return bf;
+        }
+
+        /**
+         * Reads the column name indexes if present. If the
+         * indexes are based on time then skip over them.
+         *
+         * @param cfName
+         * @return
+         */
+        private int handleColumnNameIndexes(String cfName, List<IndexHelper.ColumnIndexInfo> columnIndexList) throws IOException
+        {
+            /* check if we have an index */
+            boolean hasColumnIndexes = file_.readBoolean();
+            int totalBytesRead = 1;
+            /* if we do then deserialize the index */
+            if (hasColumnIndexes)
+            {
+                String tableName = getTableName();
+                /* read the index */
+                totalBytesRead += IndexHelper.deserializeIndex(tableName, cfName, file_, columnIndexList);
+            }
+            return totalBytesRead;
+        }
+
+        /**
+         * This method dumps the next key/value into the DataOuputStream
+         * passed in. Always use this method to query for application
+         * specific data as it will have indexes.
+         *
+         * @param key       key we are interested in.
+         * @param bufOut    DataOutputStream that needs to be filled.
+         * @param columnFamilyName name of the columnFamily
+         * @param columnNames columnNames we are interested in
+         */
+        public long next(String key, DataOutputBuffer bufOut, String columnFamilyName, SortedSet<byte[]> columnNames, long position) throws IOException
+        {
+            assert columnNames != null;
+
+            long bytesRead = -1L;
+            if (isEOF() || seekTo(position) < 0)
+                return bytesRead;
+
+            /* note the position where the key starts */
+            long startPosition = file_.getFilePointer();
+            String keyInDisk = file_.readUTF();
+            if (keyInDisk != null)
+            {
+                /*
+                 * If key on disk is greater than requested key
+                 * we can bail out since we exploit the property
+                 * of the SSTable format.
+                */
+                if (keyInDisk.compareTo(key) > 0)
+                    return bytesRead;
+
+                /*
+                 * If we found the key then we populate the buffer that
+                 * is passed in. If not then we skip over this key and
+                 * position ourselves to read the next one.
+                */
+                if (keyInDisk.equals(key))
+                {
+                    readColumns(key, bufOut, columnFamilyName, columnNames);
+                }
+                else
+                {
+                    /* skip over data portion */
+                    int dataSize = file_.readInt();
+                    file_.seek(dataSize + file_.getFilePointer());
+                }
+
+                long endPosition = file_.getFilePointer();
+                bytesRead = endPosition - startPosition;
+            }
+
+            return bytesRead;
+        }
+
+        private void readColumns(String key, DataOutputBuffer bufOut, String columnFamilyName, SortedSet<byte[]> cNames)
+        throws IOException
+        {
+            int dataSize = file_.readInt();
+
+            /* write the key into buffer */
+            bufOut.writeUTF(key);
+
+            /* if we need to read the all the columns do not read the column indexes */
+            if (cNames == null || cNames.size() == 0)
+            {
+                int bytesSkipped = IndexHelper.skipBloomFilterAndIndex(file_);
+                /*
+                       * read the correct number of bytes for the column family and
+                       * write data into buffer
+                      */
+                dataSize -= bytesSkipped;
+                /* write the data size */
+                bufOut.writeInt(dataSize);
+                /* write the data into buffer, except the boolean we have read */
+                bufOut.write(file_, dataSize);
+            }
+            else
+            {
+                /* Read the bloom filter summarizing the columns */
+                long preBfPos = file_.getFilePointer();
+                BloomFilter bf = defreezeBloomFilter();
+                long postBfPos = file_.getFilePointer();
+                dataSize -= (postBfPos - preBfPos);
+
+                List<IndexHelper.ColumnIndexInfo> columnIndexList = new ArrayList<IndexHelper.ColumnIndexInfo>();
+                /* read the column name indexes if present */
+                int totalBytesRead = handleColumnNameIndexes(columnFamilyName, columnIndexList);
+                dataSize -= totalBytesRead;
+
+                /* read the column family name */
+                String cfName = file_.readUTF();
+                dataSize -= (utfPrefix_ + cfName.length());
+
+                String cfType = file_.readUTF();
+                dataSize -= (utfPrefix_ + cfType.length());
+
+                String comparatorName = file_.readUTF();
+                dataSize -= (utfPrefix_ + comparatorName.length());
+
+                String subComparatorName = file_.readUTF();
+                dataSize -= (utfPrefix_ + subComparatorName.length());
+
+                /* read local deletion time */
+                int localDeletionTime = file_.readInt();
+                dataSize -=4;
+
+                /* read if this cf is marked for delete */
+                long markedForDeleteAt = file_.readLong();
+                dataSize -= 8;
+
+                /* read the total number of columns */
+                int totalNumCols = file_.readInt();
+                dataSize -= 4;
+
+                // TODO: this is name sorted - but eventually this should be sorted by the same criteria as the col index
+                /* get the various column ranges we have to read */
+                List<IndexHelper.ColumnRange> columnRanges = IndexHelper.getMultiColumnRangesFromNameIndex(cNames, columnIndexList, dataSize, totalNumCols);
+
+                /* calculate the data size */
+                int numColsReturned = 0;
+                int dataSizeReturned = 0;
+                for (IndexHelper.ColumnRange columnRange : columnRanges)
+                {
+                    numColsReturned += columnRange.count();
+                    Coordinate coordinate = columnRange.coordinate();
+                    dataSizeReturned += coordinate.end_ - coordinate.start_;
+                }
+
+                // returned data size
+                bufOut.writeInt(dataSizeReturned + utfPrefix_ * 4 + cfName.length() + cfType.length() + comparatorName.length() + subComparatorName.length() + 4 + 4 + 8 + 4);
+                // echo back the CF data we read
+                bufOut.writeUTF(cfName);
+                bufOut.writeUTF(cfType);
+                bufOut.writeUTF(comparatorName);
+                bufOut.writeUTF(subComparatorName);
+                bufOut.writeInt(localDeletionTime);
+                bufOut.writeLong(markedForDeleteAt);
+                /* write number of columns */
+                bufOut.writeInt(numColsReturned);
+                int prevPosition = 0;
+                /* now write all the columns we are required to write */
+                for (IndexHelper.ColumnRange columnRange : columnRanges)
+                {
+                    /* seek to the correct offset to the data */
+                    Coordinate coordinate = columnRange.coordinate();
+                    file_.skipBytes((int) (coordinate.start_ - prevPosition));
+                    bufOut.write(file_, (int) (coordinate.end_ - coordinate.start_));
+                    prevPosition = (int) coordinate.end_;
+                }
+            }
+        }
+
+        /**
+         * This method dumps the next key/value into the DataOuputStream
+         * passed in.
+         *
+         * @param bufOut DataOutputStream that needs to be filled.
+         * @return total number of bytes read/considered
+         */
+        public long next(DataOutputBuffer bufOut) throws IOException
+        {
+            long bytesRead = -1L;
+            if (isEOF())
+                return bytesRead;
+
+            long startPosition = file_.getFilePointer();
+            String key = file_.readUTF();
+            if (key != null)
+            {
+                /* write the key into buffer */
+                bufOut.writeUTF(key);
+                int dataSize = file_.readInt();
+                /* write data size into buffer */
+                bufOut.writeInt(dataSize);
+                /* write the data into buffer */
+                bufOut.write(file_, dataSize);
+                long endPosition = file_.getFilePointer();
+                bytesRead = endPosition - startPosition;
+            }
+
+            return bytesRead;
+        }
+    }
+
+    public static class Reader extends AbstractReader
+    {
+        Reader(String filename) throws IOException
+        {
+            super(filename);
+            init(filename);
+        }
+
+        protected void init(String filename) throws IOException
+        {
+            file_ = new RandomAccessFile(filename, "r");
+        }
+
+        public long getEOF() throws IOException
+        {
+            return file_.length();
+        }
+
+        public long getCurrentPosition() throws IOException
+        {
+            return file_.getFilePointer();
+        }
+
+        public boolean isHealthyFileDescriptor() throws IOException
+        {
+            return file_.getFD().valid();
+        }
+
+        public void seek(long position) throws IOException
+        {
+            file_.seek(position);
+        }
+
+        public boolean isEOF() throws IOException
+        {
+            return (getCurrentPosition() == getEOF());
+        }
+
+        /**
+         * Be extremely careful while using this API. This currently
+         * used to read the commit log header from the commit logs.
+         * Treat this as an internal API.
+         *
+         * @param bytes read from the buffer into the this array
+         */
+        public void readDirect(byte[] bytes) throws IOException
+        {
+            file_.readFully(bytes);
+        }
+
+        public long readLong() throws IOException
+        {
+            return file_.readLong();
+        }
+
+        public void close() throws IOException
+        {
+            file_.close();
+        }
+    }
+
+    public static class BufferReader extends Reader
+    {
+        private int size_;
+
+        BufferReader(String filename, int size) throws IOException
+        {
+            super(filename);
+            size_ = size;
+        }
+
+        protected void init(String filename) throws IOException
+        {
+            file_ = new BufferedRandomAccessFile(filename, "r", size_);
+        }
+    }
+
+    private static Logger logger_ = Logger.getLogger(SequenceFile.class);
+    public static final short utfPrefix_ = 2;
+    public static final String marker_ = "Bloom-Filter";
+
+    public static AbstractWriter writer(String filename) throws IOException
+    {
+        return new AbstractWriter.Writer(filename);
+    }
+
+    public static AbstractWriter bufferedWriter(String filename, int size) throws IOException
+    {
+        return new AbstractWriter.BufferWriter(filename, size);
+    }
+
+    public static IFileReader reader(String filename) throws IOException
+    {
+        return new Reader(filename);
+    }
+
+    public static IFileReader bufferedReader(String filename, int size) throws IOException
+    {
+        return new BufferReader(filename, size);
+    }
+}

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/AbstractStrategy.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/AbstractStrategy.java?rev=799331&r1=799330&r2=799331&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/AbstractStrategy.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/AbstractStrategy.java Thu Jul 30 15:30:21 2009
@@ -16,120 +16,120 @@
 * specific language governing permissions and limitations
 * under the License.
 */
-package org.apache.cassandra.locator;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.apache.log4j.Logger;
-
-import org.apache.cassandra.dht.Token;
-import org.apache.cassandra.dht.IPartitioner;
-import org.apache.cassandra.gms.FailureDetector;
-import org.apache.cassandra.net.EndPoint;
-
-/**
- * This class contains a helper method that will be used by
- * all abstraction that implement the IReplicaPlacementStrategy
- * interface.
-*/
-public abstract class AbstractStrategy implements IReplicaPlacementStrategy
-{
-    protected static Logger logger_ = Logger.getLogger(AbstractStrategy.class);
-
-    protected TokenMetadata tokenMetadata_;
-    protected IPartitioner partitioner_;
-    protected int replicas_;
-    protected int storagePort_;
-
-    AbstractStrategy(TokenMetadata tokenMetadata, IPartitioner partitioner, int replicas, int storagePort)
-    {
-        tokenMetadata_ = tokenMetadata;
-        partitioner_ = partitioner;
-        replicas_ = replicas;
-        storagePort_ = storagePort;
-    }
-
-    /*
-     * This method changes the ports of the endpoints from
-     * the control port to the storage ports.
-    */
-    protected void retrofitPorts(List<EndPoint> eps)
-    {
-        for ( EndPoint ep : eps )
-        {
-            ep.setPort(storagePort_);
-        }
-    }
-
-    protected EndPoint getNextAvailableEndPoint(EndPoint startPoint, List<EndPoint> topN, List<EndPoint> liveNodes)
-    {
-        EndPoint endPoint = null;
-        Map<Token, EndPoint> tokenToEndPointMap = tokenMetadata_.cloneTokenEndPointMap();
-        List tokens = new ArrayList(tokenToEndPointMap.keySet());
-        Collections.sort(tokens);
-        Token token = tokenMetadata_.getToken(startPoint);
-        int index = Collections.binarySearch(tokens, token);
-        if(index < 0)
-        {
-            index = (index + 1) * (-1);
-            if (index >= tokens.size())
-                index = 0;
-        }
-        int totalNodes = tokens.size();
-        int startIndex = (index+1)%totalNodes;
-        for (int i = startIndex, count = 1; count < totalNodes ; ++count, i = (i+1)%totalNodes)
-        {
-            EndPoint tmpEndPoint = tokenToEndPointMap.get(tokens.get(i));
-            if(FailureDetector.instance().isAlive(tmpEndPoint) && !topN.contains(tmpEndPoint) && !liveNodes.contains(tmpEndPoint))
-            {
-                endPoint = tmpEndPoint;
-                break;
-            }
-        }
-        return endPoint;
-    }
-
-    /*
-     * This method returns the hint map. The key is the endpoint
-     * on which the data is being placed and the value is the
-     * endpoint which is in the top N.
-     * Get the map of top N to the live nodes currently.
-     */
-    public Map<EndPoint, EndPoint> getHintedStorageEndPoints(Token token)
-    {
-        List<EndPoint> liveList = new ArrayList<EndPoint>();
-        Map<EndPoint, EndPoint> map = new HashMap<EndPoint, EndPoint>();
-        EndPoint[] topN = getStorageEndPoints( token );
-
-        for( int i = 0 ; i < topN.length ; i++)
-        {
-            if( FailureDetector.instance().isAlive(topN[i]))
-            {
-                map.put(topN[i], topN[i]);
-                liveList.add(topN[i]) ;
-            }
-            else
-            {
-                EndPoint endPoint = getNextAvailableEndPoint(topN[i], Arrays.asList(topN), liveList);
-                if(endPoint != null)
-                {
-                    map.put(endPoint, topN[i]);
-                    liveList.add(endPoint) ;
-                }
-                else
-                {
-                    // log a warning , maybe throw an exception
-                    logger_.warn("Unable to find a live Endpoint we might be out of live nodes , This is dangerous !!!!");
-                }
-            }
-        }
-        return map;
-    }
-
-    public abstract EndPoint[] getStorageEndPoints(Token token);
-}
+package org.apache.cassandra.locator;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.log4j.Logger;
+
+import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.dht.IPartitioner;
+import org.apache.cassandra.gms.FailureDetector;
+import org.apache.cassandra.net.EndPoint;
+
+/**
+ * This class contains a helper method that will be used by
+ * all abstraction that implement the IReplicaPlacementStrategy
+ * interface.
+*/
+public abstract class AbstractStrategy implements IReplicaPlacementStrategy
+{
+    protected static Logger logger_ = Logger.getLogger(AbstractStrategy.class);
+
+    protected TokenMetadata tokenMetadata_;
+    protected IPartitioner partitioner_;
+    protected int replicas_;
+    protected int storagePort_;
+
+    AbstractStrategy(TokenMetadata tokenMetadata, IPartitioner partitioner, int replicas, int storagePort)
+    {
+        tokenMetadata_ = tokenMetadata;
+        partitioner_ = partitioner;
+        replicas_ = replicas;
+        storagePort_ = storagePort;
+    }
+
+    /*
+     * This method changes the ports of the endpoints from
+     * the control port to the storage ports.
+    */
+    protected void retrofitPorts(List<EndPoint> eps)
+    {
+        for ( EndPoint ep : eps )
+        {
+            ep.setPort(storagePort_);
+        }
+    }
+
+    protected EndPoint getNextAvailableEndPoint(EndPoint startPoint, List<EndPoint> topN, List<EndPoint> liveNodes)
+    {
+        EndPoint endPoint = null;
+        Map<Token, EndPoint> tokenToEndPointMap = tokenMetadata_.cloneTokenEndPointMap();
+        List tokens = new ArrayList(tokenToEndPointMap.keySet());
+        Collections.sort(tokens);
+        Token token = tokenMetadata_.getToken(startPoint);
+        int index = Collections.binarySearch(tokens, token);
+        if(index < 0)
+        {
+            index = (index + 1) * (-1);
+            if (index >= tokens.size())
+                index = 0;
+        }
+        int totalNodes = tokens.size();
+        int startIndex = (index+1)%totalNodes;
+        for (int i = startIndex, count = 1; count < totalNodes ; ++count, i = (i+1)%totalNodes)
+        {
+            EndPoint tmpEndPoint = tokenToEndPointMap.get(tokens.get(i));
+            if(FailureDetector.instance().isAlive(tmpEndPoint) && !topN.contains(tmpEndPoint) && !liveNodes.contains(tmpEndPoint))
+            {
+                endPoint = tmpEndPoint;
+                break;
+            }
+        }
+        return endPoint;
+    }
+
+    /*
+     * This method returns the hint map. The key is the endpoint
+     * on which the data is being placed and the value is the
+     * endpoint which is in the top N.
+     * Get the map of top N to the live nodes currently.
+     */
+    public Map<EndPoint, EndPoint> getHintedStorageEndPoints(Token token)
+    {
+        List<EndPoint> liveList = new ArrayList<EndPoint>();
+        Map<EndPoint, EndPoint> map = new HashMap<EndPoint, EndPoint>();
+        EndPoint[] topN = getStorageEndPoints( token );
+
+        for( int i = 0 ; i < topN.length ; i++)
+        {
+            if( FailureDetector.instance().isAlive(topN[i]))
+            {
+                map.put(topN[i], topN[i]);
+                liveList.add(topN[i]) ;
+            }
+            else
+            {
+                EndPoint endPoint = getNextAvailableEndPoint(topN[i], Arrays.asList(topN), liveList);
+                if(endPoint != null)
+                {
+                    map.put(endPoint, topN[i]);
+                    liveList.add(endPoint) ;
+                }
+                else
+                {
+                    // log a warning , maybe throw an exception
+                    logger_.warn("Unable to find a live Endpoint we might be out of live nodes , This is dangerous !!!!");
+                }
+            }
+        }
+        return map;
+    }
+
+    public abstract EndPoint[] getStorageEndPoints(Token token);
+}

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/EndPointSnitch.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/EndPointSnitch.java?rev=799331&r1=799330&r2=799331&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/EndPointSnitch.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/EndPointSnitch.java Thu Jul 30 15:30:21 2009
@@ -1,61 +1,61 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.cassandra.locator;
-
-import java.net.*;
-
-import org.apache.cassandra.net.EndPoint;
-/**
- * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
- */
-
-public class EndPointSnitch implements IEndPointSnitch
-{
-    public boolean isOnSameRack(EndPoint host, EndPoint host2) throws UnknownHostException
-    {
-        /*
-         * Look at the IP Address of the two hosts. Compare 
-         * the 3rd octet. If they are the same then the hosts
-         * are in the same rack else different racks. 
-        */        
-        byte[] ip = getIPAddress(host.getHost());
-        byte[] ip2 = getIPAddress(host2.getHost());
-        
-        return ( ip[2] == ip2[2] );
-    }
-    
-    public boolean isInSameDataCenter(EndPoint host, EndPoint host2) throws UnknownHostException
-    {
-        /*
-         * Look at the IP Address of the two hosts. Compare 
-         * the 2nd octet. If they are the same then the hosts
-         * are in the same datacenter else different datacenter. 
-        */
-        byte[] ip = getIPAddress(host.getHost());
-        byte[] ip2 = getIPAddress(host2.getHost());
-        
-        return ( ip[1] == ip2[1] );
-    }
-    
-    private byte[] getIPAddress(String host) throws UnknownHostException
-    {
-        InetAddress ia = InetAddress.getByName(host);         
-        return ia.getAddress();
-    }
-}
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.cassandra.locator;
+
+import java.net.*;
+
+import org.apache.cassandra.net.EndPoint;
+/**
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+
+public class EndPointSnitch implements IEndPointSnitch
+{
+    public boolean isOnSameRack(EndPoint host, EndPoint host2) throws UnknownHostException
+    {
+        /*
+         * Look at the IP Address of the two hosts. Compare 
+         * the 3rd octet. If they are the same then the hosts
+         * are in the same rack else different racks. 
+        */        
+        byte[] ip = getIPAddress(host.getHost());
+        byte[] ip2 = getIPAddress(host2.getHost());
+        
+        return ( ip[2] == ip2[2] );
+    }
+    
+    public boolean isInSameDataCenter(EndPoint host, EndPoint host2) throws UnknownHostException
+    {
+        /*
+         * Look at the IP Address of the two hosts. Compare 
+         * the 2nd octet. If they are the same then the hosts
+         * are in the same datacenter else different datacenter. 
+        */
+        byte[] ip = getIPAddress(host.getHost());
+        byte[] ip2 = getIPAddress(host2.getHost());
+        
+        return ( ip[1] == ip2[1] );
+    }
+    
+    private byte[] getIPAddress(String host) throws UnknownHostException
+    {
+        InetAddress ia = InetAddress.getByName(host);         
+        return ia.getAddress();
+    }
+}

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IEndPointSnitch.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IEndPointSnitch.java?rev=799331&r1=799330&r2=799331&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IEndPointSnitch.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IEndPointSnitch.java Thu Jul 30 15:30:21 2009
@@ -1,52 +1,52 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.cassandra.locator;
-
-import java.net.UnknownHostException;
-
-import org.apache.cassandra.net.EndPoint;
-
-
-/**
- * This interface helps determine location of node in the data center relative to another node.
- * Give a node A and another node B it can tell if A and B are on the same rack or in the same
- * data center.
- * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
- */
-
-public interface IEndPointSnitch
-{
-    /**
-     * Helps determine if 2 nodes are in the same rack in the data center.
-     * @param host a specified endpoint
-     * @param host2 another specified endpoint
-     * @return true if on the same rack false otherwise
-     * @throws UnknownHostException
-     */
-    public boolean isOnSameRack(EndPoint host, EndPoint host2) throws UnknownHostException;
-    
-    /**
-     * Helps determine if 2 nodes are in the same data center.
-     * @param host a specified endpoint
-     * @param host2 another specified endpoint
-     * @return true if in the same data center false otherwise
-     * @throws UnknownHostException
-     */
-    public boolean isInSameDataCenter(EndPoint host, EndPoint host2) throws UnknownHostException;
-}
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.cassandra.locator;
+
+import java.net.UnknownHostException;
+
+import org.apache.cassandra.net.EndPoint;
+
+
+/**
+ * This interface helps determine location of node in the data center relative to another node.
+ * Give a node A and another node B it can tell if A and B are on the same rack or in the same
+ * data center.
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+
+public interface IEndPointSnitch
+{
+    /**
+     * Helps determine if 2 nodes are in the same rack in the data center.
+     * @param host a specified endpoint
+     * @param host2 another specified endpoint
+     * @return true if on the same rack false otherwise
+     * @throws UnknownHostException
+     */
+    public boolean isOnSameRack(EndPoint host, EndPoint host2) throws UnknownHostException;
+    
+    /**
+     * Helps determine if 2 nodes are in the same data center.
+     * @param host a specified endpoint
+     * @param host2 another specified endpoint
+     * @return true if in the same data center false otherwise
+     * @throws UnknownHostException
+     */
+    public boolean isInSameDataCenter(EndPoint host, EndPoint host2) throws UnknownHostException;
+}

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IReplicaPlacementStrategy.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IReplicaPlacementStrategy.java?rev=799331&r1=799330&r2=799331&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IReplicaPlacementStrategy.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/IReplicaPlacementStrategy.java Thu Jul 30 15:30:21 2009
@@ -1,40 +1,40 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.cassandra.locator;
-
-import java.util.Map;
-import java.math.BigInteger;
-
-import org.apache.cassandra.dht.Token;
-import org.apache.cassandra.net.EndPoint;
-
-
-/*
- * This interface has two implementations. One which
- * does not respect rack or datacenter awareness and
- * the other which does.
- * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
- */
-public interface IReplicaPlacementStrategy
-{
-	public EndPoint[] getStorageEndPoints(Token token);
-    public Map<String, EndPoint[]> getStorageEndPoints(String[] keys);
-    public EndPoint[] getStorageEndPoints(Token token, Map<Token, EndPoint> tokenToEndPointMap);
-    public Map<EndPoint, EndPoint> getHintedStorageEndPoints(Token token);
-}
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.cassandra.locator;
+
+import java.util.Map;
+import java.math.BigInteger;
+
+import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.net.EndPoint;
+
+
+/*
+ * This interface has two implementations. One which
+ * does not respect rack or datacenter awareness and
+ * the other which does.
+ * Author : Avinash Lakshman ( alakshman@facebook.com) & Prashant Malik ( pmalik@facebook.com )
+ */
+public interface IReplicaPlacementStrategy
+{
+	public EndPoint[] getStorageEndPoints(Token token);
+    public Map<String, EndPoint[]> getStorageEndPoints(String[] keys);
+    public EndPoint[] getStorageEndPoints(Token token, Map<Token, EndPoint> tokenToEndPointMap);
+    public Map<EndPoint, EndPoint> getHintedStorageEndPoints(Token token);
+}

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackAwareStrategy.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackAwareStrategy.java?rev=799331&r1=799330&r2=799331&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackAwareStrategy.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackAwareStrategy.java Thu Jul 30 15:30:21 2009
@@ -1,142 +1,142 @@
-/*
-* Licensed to the Apache Software Foundation (ASF) under one
-* or more contributor license agreements.  See the NOTICE file
-* distributed with this work for additional information
-* regarding copyright ownership.  The ASF licenses this file
-* to you under the Apache License, Version 2.0 (the
-* "License"); you may not use this file except in compliance
-* with the License.  You may obtain a copy of the License at
-*
-*    http://www.apache.org/licenses/LICENSE-2.0
-*
-* Unless required by applicable law or agreed to in writing,
-* software distributed under the License is distributed on an
-* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-* KIND, either express or implied.  See the License for the
-* specific language governing permissions and limitations
-* under the License.
-*/
-package org.apache.cassandra.locator;
-
-import java.net.UnknownHostException;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.apache.cassandra.dht.Token;
-import org.apache.cassandra.dht.IPartitioner;
-import org.apache.cassandra.net.EndPoint;
-import org.apache.cassandra.service.StorageService;
-import org.apache.cassandra.utils.LogUtil;
-
-/*
- * This class returns the nodes responsible for a given
- * key but does respects rack awareness. It makes a best
- * effort to get a node from a different data center and
- * a node in a different rack in the same datacenter as
- * the primary.
- */
-public class RackAwareStrategy extends AbstractStrategy
-{
-    public RackAwareStrategy(TokenMetadata tokenMetadata, IPartitioner partitioner, int replicas, int storagePort)
-    {
-        super(tokenMetadata, partitioner, replicas, storagePort);
-    }
-
-    public EndPoint[] getStorageEndPoints(Token token)
-    {
-        int startIndex;
-        List<EndPoint> list = new ArrayList<EndPoint>();
-        boolean bDataCenter = false;
-        boolean bOtherRack = false;
-        int foundCount = 0;
-        Map<Token, EndPoint> tokenToEndPointMap = tokenMetadata_.cloneTokenEndPointMap();
-        List tokens = new ArrayList(tokenToEndPointMap.keySet());
-        Collections.sort(tokens);
-        int index = Collections.binarySearch(tokens, token);
-        if(index < 0)
-        {
-            index = (index + 1) * (-1);
-            if (index >= tokens.size())
-                index = 0;
-        }
-        int totalNodes = tokens.size();
-        // Add the node at the index by default
-        list.add(tokenToEndPointMap.get(tokens.get(index)));
-        foundCount++;
-        if( replicas_ == 1 )
-        {
-            return list.toArray(new EndPoint[list.size()]);
-        }
-        startIndex = (index + 1)%totalNodes;
-        IEndPointSnitch endPointSnitch = StorageService.instance().getEndPointSnitch();
-        
-        for (int i = startIndex, count = 1; count < totalNodes && foundCount < replicas_; ++count, i = (i+1)%totalNodes)
-        {
-            try
-            {
-                // First try to find one in a different data center
-                if(!endPointSnitch.isInSameDataCenter(tokenToEndPointMap.get(tokens.get(index)), tokenToEndPointMap.get(tokens.get(i))))
-                {
-                    // If we have already found something in a diff datacenter no need to find another
-                    if( !bDataCenter )
-                    {
-                        list.add(tokenToEndPointMap.get(tokens.get(i)));
-                        bDataCenter = true;
-                        foundCount++;
-                    }
-                    continue;
-                }
-                // Now  try to find one on a different rack
-                if(!endPointSnitch.isOnSameRack(tokenToEndPointMap.get(tokens.get(index)), tokenToEndPointMap.get(tokens.get(i))) &&
-                        endPointSnitch.isInSameDataCenter(tokenToEndPointMap.get(tokens.get(index)), tokenToEndPointMap.get(tokens.get(i))))
-                {
-                    // If we have already found something in a diff rack no need to find another
-                    if( !bOtherRack )
-                    {
-                        list.add(tokenToEndPointMap.get(tokens.get(i)));
-                        bOtherRack = true;
-                        foundCount++;
-                    }
-                }
-            }
-            catch (UnknownHostException e)
-            {
-                if (logger_.isDebugEnabled())
-                  logger_.debug(LogUtil.throwableToString(e));
-            }
-
-        }
-        // If we found N number of nodes we are good. This loop wil just exit. Otherwise just
-        // loop through the list and add until we have N nodes.
-        for (int i = startIndex, count = 1; count < totalNodes && foundCount < replicas_; ++count, i = (i+1)%totalNodes)
-        {
-            if( ! list.contains(tokenToEndPointMap.get(tokens.get(i))))
-            {
-                list.add(tokenToEndPointMap.get(tokens.get(i)));
-                foundCount++;
-            }
-        }
-        retrofitPorts(list);
-        return list.toArray(new EndPoint[list.size()]);
-    }
-    
-    public Map<String, EndPoint[]> getStorageEndPoints(String[] keys)
-    {
-    	Map<String, EndPoint[]> results = new HashMap<String, EndPoint[]>();
-
-        for ( String key : keys )
-        {
-            results.put(key, getStorageEndPoints(partitioner_.getInitialToken(key)));
-        }
-
-        return results;
-    }
-
-    public EndPoint[] getStorageEndPoints(Token token, Map<Token, EndPoint> tokenToEndPointMap)
-    {
-        throw new UnsupportedOperationException("This operation is not currently supported");
-    }
+/*
+* Licensed to the Apache Software Foundation (ASF) under one
+* or more contributor license agreements.  See the NOTICE file
+* distributed with this work for additional information
+* regarding copyright ownership.  The ASF licenses this file
+* to you under the Apache License, Version 2.0 (the
+* "License"); you may not use this file except in compliance
+* with the License.  You may obtain a copy of the License at
+*
+*    http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing,
+* software distributed under the License is distributed on an
+* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+* KIND, either express or implied.  See the License for the
+* specific language governing permissions and limitations
+* under the License.
+*/
+package org.apache.cassandra.locator;
+
+import java.net.UnknownHostException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.dht.IPartitioner;
+import org.apache.cassandra.net.EndPoint;
+import org.apache.cassandra.service.StorageService;
+import org.apache.cassandra.utils.LogUtil;
+
+/*
+ * This class returns the nodes responsible for a given
+ * key but does respects rack awareness. It makes a best
+ * effort to get a node from a different data center and
+ * a node in a different rack in the same datacenter as
+ * the primary.
+ */
+public class RackAwareStrategy extends AbstractStrategy
+{
+    public RackAwareStrategy(TokenMetadata tokenMetadata, IPartitioner partitioner, int replicas, int storagePort)
+    {
+        super(tokenMetadata, partitioner, replicas, storagePort);
+    }
+
+    public EndPoint[] getStorageEndPoints(Token token)
+    {
+        int startIndex;
+        List<EndPoint> list = new ArrayList<EndPoint>();
+        boolean bDataCenter = false;
+        boolean bOtherRack = false;
+        int foundCount = 0;
+        Map<Token, EndPoint> tokenToEndPointMap = tokenMetadata_.cloneTokenEndPointMap();
+        List tokens = new ArrayList(tokenToEndPointMap.keySet());
+        Collections.sort(tokens);
+        int index = Collections.binarySearch(tokens, token);
+        if(index < 0)
+        {
+            index = (index + 1) * (-1);
+            if (index >= tokens.size())
+                index = 0;
+        }
+        int totalNodes = tokens.size();
+        // Add the node at the index by default
+        list.add(tokenToEndPointMap.get(tokens.get(index)));
+        foundCount++;
+        if( replicas_ == 1 )
+        {
+            return list.toArray(new EndPoint[list.size()]);
+        }
+        startIndex = (index + 1)%totalNodes;
+        IEndPointSnitch endPointSnitch = StorageService.instance().getEndPointSnitch();
+        
+        for (int i = startIndex, count = 1; count < totalNodes && foundCount < replicas_; ++count, i = (i+1)%totalNodes)
+        {
+            try
+            {
+                // First try to find one in a different data center
+                if(!endPointSnitch.isInSameDataCenter(tokenToEndPointMap.get(tokens.get(index)), tokenToEndPointMap.get(tokens.get(i))))
+                {
+                    // If we have already found something in a diff datacenter no need to find another
+                    if( !bDataCenter )
+                    {
+                        list.add(tokenToEndPointMap.get(tokens.get(i)));
+                        bDataCenter = true;
+                        foundCount++;
+                    }
+                    continue;
+                }
+                // Now  try to find one on a different rack
+                if(!endPointSnitch.isOnSameRack(tokenToEndPointMap.get(tokens.get(index)), tokenToEndPointMap.get(tokens.get(i))) &&
+                        endPointSnitch.isInSameDataCenter(tokenToEndPointMap.get(tokens.get(index)), tokenToEndPointMap.get(tokens.get(i))))
+                {
+                    // If we have already found something in a diff rack no need to find another
+                    if( !bOtherRack )
+                    {
+                        list.add(tokenToEndPointMap.get(tokens.get(i)));
+                        bOtherRack = true;
+                        foundCount++;
+                    }
+                }
+            }
+            catch (UnknownHostException e)
+            {
+                if (logger_.isDebugEnabled())
+                  logger_.debug(LogUtil.throwableToString(e));
+            }
+
+        }
+        // If we found N number of nodes we are good. This loop wil just exit. Otherwise just
+        // loop through the list and add until we have N nodes.
+        for (int i = startIndex, count = 1; count < totalNodes && foundCount < replicas_; ++count, i = (i+1)%totalNodes)
+        {
+            if( ! list.contains(tokenToEndPointMap.get(tokens.get(i))))
+            {
+                list.add(tokenToEndPointMap.get(tokens.get(i)));
+                foundCount++;
+            }
+        }
+        retrofitPorts(list);
+        return list.toArray(new EndPoint[list.size()]);
+    }
+    
+    public Map<String, EndPoint[]> getStorageEndPoints(String[] keys)
+    {
+    	Map<String, EndPoint[]> results = new HashMap<String, EndPoint[]>();
+
+        for ( String key : keys )
+        {
+            results.put(key, getStorageEndPoints(partitioner_.getInitialToken(key)));
+        }
+
+        return results;
+    }
+
+    public EndPoint[] getStorageEndPoints(Token token, Map<Token, EndPoint> tokenToEndPointMap)
+    {
+        throw new UnsupportedOperationException("This operation is not currently supported");
+    }
 }
\ No newline at end of file

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java?rev=799331&r1=799330&r2=799331&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java Thu Jul 30 15:30:21 2009
@@ -16,78 +16,78 @@
 * specific language governing permissions and limitations
 * under the License.
 */
-package org.apache.cassandra.locator;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.apache.cassandra.dht.Token;
-import org.apache.cassandra.dht.IPartitioner;
-import org.apache.cassandra.net.EndPoint;
-
-/**
- * This class returns the nodes responsible for a given
- * key but does not respect rack awareness. Basically
- * returns the 3 nodes that lie right next to each other
- * on the ring.
- */
-public class RackUnawareStrategy extends AbstractStrategy
-{
-    public RackUnawareStrategy(TokenMetadata tokenMetadata, IPartitioner partitioner, int replicas, int storagePort)
-    {
-        super(tokenMetadata, partitioner, replicas, storagePort);
-    }
-
-    public EndPoint[] getStorageEndPoints(Token token)
-    {
-        return getStorageEndPoints(token, tokenMetadata_.cloneTokenEndPointMap());            
-    }
-    
-    public EndPoint[] getStorageEndPoints(Token token, Map<Token, EndPoint> tokenToEndPointMap)
-    {
-        int startIndex;
-        List<EndPoint> list = new ArrayList<EndPoint>();
-        int foundCount = 0;
-        List tokens = new ArrayList<Token>(tokenToEndPointMap.keySet());
-        Collections.sort(tokens);
-        int index = Collections.binarySearch(tokens, token);
-        if(index < 0)
-        {
-            index = (index + 1) * (-1);
-            if (index >= tokens.size())
-                index = 0;
-        }
-        int totalNodes = tokens.size();
-        // Add the node at the index by default
-        list.add(tokenToEndPointMap.get(tokens.get(index)));
-        foundCount++;
-        startIndex = (index + 1)%totalNodes;
-        // If we found N number of nodes we are good. This loop will just exit. Otherwise just
-        // loop through the list and add until we have N nodes.
-        for (int i = startIndex, count = 1; count < totalNodes && foundCount < replicas_; ++count, i = (i+1)%totalNodes)
-        {
-            if( ! list.contains(tokenToEndPointMap.get(tokens.get(i))))
-            {
-                list.add(tokenToEndPointMap.get(tokens.get(i)));
-                foundCount++;
-            }
-        }
-        retrofitPorts(list);
-        return list.toArray(new EndPoint[list.size()]);
-    }
-            
-    public Map<String, EndPoint[]> getStorageEndPoints(String[] keys)
-    {
-    	Map<String, EndPoint[]> results = new HashMap<String, EndPoint[]>();
-
-        for ( String key : keys )
-        {
-            results.put(key, getStorageEndPoints(partitioner_.getInitialToken(key)));
-        }
-
-        return results;
-    }
-}
+package org.apache.cassandra.locator;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.dht.IPartitioner;
+import org.apache.cassandra.net.EndPoint;
+
+/**
+ * This class returns the nodes responsible for a given
+ * key but does not respect rack awareness. Basically
+ * returns the 3 nodes that lie right next to each other
+ * on the ring.
+ */
+public class RackUnawareStrategy extends AbstractStrategy
+{
+    public RackUnawareStrategy(TokenMetadata tokenMetadata, IPartitioner partitioner, int replicas, int storagePort)
+    {
+        super(tokenMetadata, partitioner, replicas, storagePort);
+    }
+
+    public EndPoint[] getStorageEndPoints(Token token)
+    {
+        return getStorageEndPoints(token, tokenMetadata_.cloneTokenEndPointMap());            
+    }
+    
+    public EndPoint[] getStorageEndPoints(Token token, Map<Token, EndPoint> tokenToEndPointMap)
+    {
+        int startIndex;
+        List<EndPoint> list = new ArrayList<EndPoint>();
+        int foundCount = 0;
+        List tokens = new ArrayList<Token>(tokenToEndPointMap.keySet());
+        Collections.sort(tokens);
+        int index = Collections.binarySearch(tokens, token);
+        if(index < 0)
+        {
+            index = (index + 1) * (-1);
+            if (index >= tokens.size())
+                index = 0;
+        }
+        int totalNodes = tokens.size();
+        // Add the node at the index by default
+        list.add(tokenToEndPointMap.get(tokens.get(index)));
+        foundCount++;
+        startIndex = (index + 1)%totalNodes;
+        // If we found N number of nodes we are good. This loop will just exit. Otherwise just
+        // loop through the list and add until we have N nodes.
+        for (int i = startIndex, count = 1; count < totalNodes && foundCount < replicas_; ++count, i = (i+1)%totalNodes)
+        {
+            if( ! list.contains(tokenToEndPointMap.get(tokens.get(i))))
+            {
+                list.add(tokenToEndPointMap.get(tokens.get(i)));
+                foundCount++;
+            }
+        }
+        retrofitPorts(list);
+        return list.toArray(new EndPoint[list.size()]);
+    }
+            
+    public Map<String, EndPoint[]> getStorageEndPoints(String[] keys)
+    {
+    	Map<String, EndPoint[]> results = new HashMap<String, EndPoint[]>();
+
+        for ( String key : keys )
+        {
+            results.put(key, getStorageEndPoints(partitioner_.getInitialToken(key)));
+        }
+
+        return results;
+    }
+}