cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject svn commit: r1225001 [1/2] - in /cassandra/trunk: lib/ lib/licenses/ src/java/org/apache/cassandra/db/ test/unit/org/apache/cassandra/db/
Date Tue, 27 Dec 2011 20:17:18 GMT
Author: jbellis
Date: Tue Dec 27 20:17:17 2011
New Revision: 1225001

URL: http://svn.apache.org/viewvc?rev=1225001&view=rev
Log:
add row-level isolation via SnapTree
patch by slebresne; reviewed by jbellis for CASSANDRA-2893

Added:
    cassandra/trunk/lib/licenses/snaptree-0.1-SNAPSHOT.txt
    cassandra/trunk/lib/snaptree-0.1-SNAPSHOT.jar
    cassandra/trunk/src/java/org/apache/cassandra/db/AbstractThreadUnsafeSortedColumns.java
    cassandra/trunk/src/java/org/apache/cassandra/db/AtomicSortedColumns.java
Removed:
    cassandra/trunk/src/java/org/apache/cassandra/db/ThreadSafeSortedColumns.java
Modified:
    cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java
    cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
    cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java
    cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamily.java
    cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilySerializer.java
    cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java
    cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java
    cassandra/trunk/src/java/org/apache/cassandra/db/Row.java
    cassandra/trunk/src/java/org/apache/cassandra/db/RowMutation.java
    cassandra/trunk/src/java/org/apache/cassandra/db/SuperColumn.java
    cassandra/trunk/src/java/org/apache/cassandra/db/TreeMapBackedSortedColumns.java
    cassandra/trunk/test/unit/org/apache/cassandra/db/ArrayBackedSortedColumnsTest.java
    cassandra/trunk/test/unit/org/apache/cassandra/db/ColumnFamilyTest.java

Added: cassandra/trunk/lib/licenses/snaptree-0.1-SNAPSHOT.txt
URL: http://svn.apache.org/viewvc/cassandra/trunk/lib/licenses/snaptree-0.1-SNAPSHOT.txt?rev=1225001&view=auto
==============================================================================
--- cassandra/trunk/lib/licenses/snaptree-0.1-SNAPSHOT.txt (added)
+++ cassandra/trunk/lib/licenses/snaptree-0.1-SNAPSHOT.txt Tue Dec 27 20:17:17 2011
@@ -0,0 +1,776 @@
+
+
+
+<!DOCTYPE html>
+<html>
+  <head>
+    <meta charset='utf-8'>
+    <meta http-equiv="X-UA-Compatible" content="chrome=1">
+        <title>doc/LICENSE at master from nbronson/snaptree - GitHub</title>
+    <link rel="search" type="application/opensearchdescription+xml" href="/opensearch.xml" title="GitHub" />
+    <link rel="fluid-icon" href="https://github.com/fluidicon.png" title="GitHub" />
+
+    
+    
+
+    <meta content="authenticity_token" name="csrf-param" />
+<meta content="kCKdrZvsCWGNIGaBTKBWlG4gYXwI636kkFF5Jfbr//c=" name="csrf-token" />
+
+    <link href="https://a248.e.akamai.net/assets.github.com/stylesheets/bundles/github-ce4abc8fb736cacb557664dcd8194a5486c74f6b.css" media="screen" rel="stylesheet" type="text/css" />
+    
+
+    <script src="https://a248.e.akamai.net/assets.github.com/javascripts/bundles/jquery-6c2aad85e5c2becfaac6d62ce0f290d10fa1725e.js" type="text/javascript"></script>
+    <script src="https://a248.e.akamai.net/assets.github.com/javascripts/bundles/github-724a1478428e953614c0459ba27f5d900fc109be.js" type="text/javascript"></script>
+    
+
+      <link rel='permalink' href='/nbronson/snaptree/blob/b198f84b0c927f6b5cdef080552fc26aa004d3ee/doc/LICENSE'>
+    
+
+    <meta name="description" content="snaptree - Concurrent TreeMap w/ efficient support for clone() and consistent iteration" />
+  <link href="https://github.com/nbronson/snaptree/commits/master.atom" rel="alternate" title="Recent Commits to snaptree:master" type="application/atom+xml" />
+
+  </head>
+
+
+  <body class="logged_out page-blob  vis-public env-production ">
+    
+
+
+    
+
+      <div id="header" class="true clearfix">
+        <div class="container" class="clearfix">
+          <a class="site-logo" href="https://github.com">
+            <!--[if IE]>
+            <img alt="GitHub" class="github-logo" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7.png?1323882717" />
+            <img alt="GitHub" class="github-logo-hover" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7-hover.png?1324325359" />
+            <![endif]-->
+            <img alt="GitHub" class="github-logo-4x" height="30" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7@4x.png?1323882717" />
+            <img alt="GitHub" class="github-logo-4x-hover" height="30" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7@4x-hover.png?1324325359" />
+          </a>
+
+                <!--
+      make sure to use fully qualified URLs here since this nav
+      is used on error pages on other domains
+    -->
+    <ul class="top-nav logged_out">
+        <li class="pricing"><a href="https://github.com/plans">Signup and Pricing</a></li>
+        <li class="explore"><a href="https://github.com/explore">Explore GitHub</a></li>
+      <li class="features"><a href="https://github.com/features">Features</a></li>
+        <li class="blog"><a href="https://github.com/blog">Blog</a></li>
+      <li class="login"><a href="https://github.com/login?return_to=%2Fnbronson%2Fsnaptree%2Fblob%2Fmaster%2Fdoc%2FLICENSE">Login</a></li>
+    </ul>
+
+
+        </div>
+      </div>
+
+      
+
+            <div class="site">
+      <div class="container">
+        <div class="pagehead repohead instapaper_ignore readability-menu">
+
+
+        <div class="title-actions-bar">
+          <h1>
+            <a href="/nbronson">nbronson</a> /
+            <strong><a href="/nbronson/snaptree" class="js-current-repository">snaptree</a></strong>
+          </h1>
+          
+
+
+
+              <ul class="pagehead-actions">
+
+
+          <li><a href="/login?return_to=%2Fnbronson%2Fsnaptree" class="minibutton btn-watch watch-button entice tooltipped leftwards" rel="nofollow" title="You must be logged in to use this feature"><span><span class="icon"></span>Watch</span></a></li>
+          <li><a href="/login?return_to=%2Fnbronson%2Fsnaptree" class="minibutton btn-fork fork-button entice tooltipped leftwards" rel="nofollow" title="You must be logged in to use this feature"><span><span class="icon"></span>Fork</span></a></li>
+
+
+      <li class="repostats">
+        <ul class="repo-stats">
+          <li class="watchers ">
+            <a href="/nbronson/snaptree/watchers" title="Watchers" class="tooltipped downwards">
+              25
+            </a>
+          </li>
+          <li class="forks">
+            <a href="/nbronson/snaptree/network" title="Forks" class="tooltipped downwards">
+              2
+            </a>
+          </li>
+        </ul>
+      </li>
+    </ul>
+
+        </div>
+
+          
+
+  <ul class="tabs">
+    <li><a href="/nbronson/snaptree" class="selected" highlight="repo_sourcerepo_downloadsrepo_commitsrepo_tagsrepo_branches">Code</a></li>
+    <li><a href="/nbronson/snaptree/network" highlight="repo_networkrepo_fork_queue">Network</a>
+    <li><a href="/nbronson/snaptree/pulls" highlight="repo_pulls">Pull Requests <span class='counter'>0</span></a></li>
+
+      <li><a href="/nbronson/snaptree/issues" highlight="repo_issues">Issues <span class='counter'>0</span></a></li>
+
+
+    <li><a href="/nbronson/snaptree/graphs" highlight="repo_graphsrepo_contributors">Stats &amp; Graphs</a></li>
+
+  </ul>
+
+  
+<div class="frame frame-center tree-finder" style="display:none"
+      data-tree-list-url="/nbronson/snaptree/tree-list/b198f84b0c927f6b5cdef080552fc26aa004d3ee"
+      data-blob-url-prefix="/nbronson/snaptree/blob/b198f84b0c927f6b5cdef080552fc26aa004d3ee"
+    >
+
+  <div class="breadcrumb">
+    <b><a href="/nbronson/snaptree">snaptree</a></b> /
+    <input class="tree-finder-input js-navigation-enable" type="text" name="query" autocomplete="off" spellcheck="false">
+  </div>
+
+    <div class="octotip">
+      <p>
+        <a href="/nbronson/snaptree/dismiss-tree-finder-help" class="dismiss js-dismiss-tree-list-help" title="Hide this notice forever" rel="nofollow">Dismiss</a>
+        <strong>Octotip:</strong> You've activated the <em>file finder</em>
+        by pressing <span class="kbd">t</span> Start typing to filter the
+        file list. Use <span class="kbd badmono">↑</span> and
+        <span class="kbd badmono">↓</span> to navigate,
+        <span class="kbd">enter</span> to view files.
+      </p>
+    </div>
+
+  <table class="tree-browser" cellpadding="0" cellspacing="0">
+    <tr class="js-header"><th>&nbsp;</th><th>name</th></tr>
+    <tr class="js-no-results no-results" style="display: none">
+      <th colspan="2">No matching files</th>
+    </tr>
+    <tbody class="js-results-list js-navigation-container" data-navigation-enable-mouse>
+    </tbody>
+  </table>
+</div>
+
+<div id="jump-to-line" style="display:none">
+  <h2>Jump to Line</h2>
+  <form>
+    <input class="textfield" type="text">
+    <div class="full-button">
+      <button type="submit" class="classy">
+        <span>Go</span>
+      </button>
+    </div>
+  </form>
+</div>
+
+
+<div class="subnav-bar">
+
+  <ul class="actions">
+    
+      <li class="switcher">
+
+        <div class="context-menu-container js-menu-container">
+          <span class="text">Current branch:</span>
+          <a href="#"
+             class="minibutton bigger switcher context-menu-button js-menu-target js-commitish-button btn-branch repo-tree"
+             data-master-branch="master"
+             data-ref="master">
+            <span><span class="icon"></span>master</span>
+          </a>
+
+          <div class="context-pane commitish-context js-menu-content">
+            <a href="javascript:;" class="close js-menu-close"></a>
+            <div class="title">Switch Branches/Tags</div>
+            <div class="body pane-selector commitish-selector js-filterable-commitishes">
+              <div class="filterbar">
+                <div class="placeholder-field js-placeholder-field">
+                  <label class="placeholder" for="context-commitish-filter-field" data-placeholder-mode="sticky">Filter branches/tags</label>
+                  <input type="text" id="context-commitish-filter-field" class="commitish-filter" />
+                </div>
+
+                <ul class="tabs">
+                  <li><a href="#" data-filter="branches" class="selected">Branches</a></li>
+                  <li><a href="#" data-filter="tags">Tags</a></li>
+                </ul>
+              </div>
+
+                <div class="commitish-item branch-commitish selector-item">
+                  <h4>
+                      <a href="/nbronson/snaptree/blob/master/doc/LICENSE" data-name="master">master</a>
+                  </h4>
+                </div>
+
+
+              <div class="no-results" style="display:none">Nothing to show</div>
+            </div>
+          </div><!-- /.commitish-context-context -->
+        </div>
+
+      </li>
+  </ul>
+
+  <ul class="subnav">
+    <li><a href="/nbronson/snaptree" class="selected" highlight="repo_source">Files</a></li>
+    <li><a href="/nbronson/snaptree/commits/master" highlight="repo_commits">Commits</a></li>
+    <li><a href="/nbronson/snaptree/branches" class="" highlight="repo_branches" rel="nofollow">Branches <span class="counter">1</span></a></li>
+    <li><a href="/nbronson/snaptree/tags" class="blank" highlight="repo_tags">Tags <span class="counter">0</span></a></li>
+    <li><a href="/nbronson/snaptree/downloads" class="blank" highlight="repo_downloads">Downloads <span class="counter">0</span></a></li>
+  </ul>
+
+</div>
+
+  
+  
+  
+
+
+          
+
+        </div><!-- /.repohead -->
+
+        
+
+
+
+
+  
+  <p class="last-commit">Latest commit to the <strong>master</strong> branch</p>
+
+<div class="commit commit-tease js-details-container">
+  <p class="commit-title ">
+      <a href="/nbronson/snaptree/commit/b198f84b0c927f6b5cdef080552fc26aa004d3ee" class="message">update to new IDEA install</a>
+      
+  </p>
+  <div class="commit-meta">
+    <a href="/nbronson/snaptree/commit/b198f84b0c927f6b5cdef080552fc26aa004d3ee" class="sha-block">commit <span class="sha">b198f84b0c</span></a>
+
+    <div class="authorship">
+      <img class="gravatar" height="20" src="https://secure.gravatar.com/avatar/9e4674291aec6ad9f6c0a7e219d522c0?s=140&amp;d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png" width="20" />
+      <span class="author-name"><a href="/nbronson">nbronson</a></span>
+      authored <time class="js-relative-date" datetime="2011-11-16T09:38:04-08:00" title="2011-11-16 09:38:04">November 16, 2011</time>
+
+    </div>
+  </div>
+</div>
+
+
+  <div id="slider">
+
+    <div class="breadcrumb" data-path="doc/LICENSE/">
+      <b><a href="/nbronson/snaptree/tree/b198f84b0c927f6b5cdef080552fc26aa004d3ee" class="js-rewrite-sha">snaptree</a></b> / <a href="/nbronson/snaptree/tree/b198f84b0c927f6b5cdef080552fc26aa004d3ee/doc" class="js-rewrite-sha">doc</a> / LICENSE       <span style="display:none" id="clippy_4738" class="clippy-text">doc/LICENSE</span>
+      
+      <object classid="clsid:d27cdb6e-ae6d-11cf-96b8-444553540000"
+              width="110"
+              height="14"
+              class="clippy"
+              id="clippy" >
+      <param name="movie" value="https://a248.e.akamai.net/assets.github.com/flash/clippy.swf?1261951368?v5"/>
+      <param name="allowScriptAccess" value="always" />
+      <param name="quality" value="high" />
+      <param name="scale" value="noscale" />
+      <param NAME="FlashVars" value="id=clippy_4738&amp;copied=copied!&amp;copyto=copy to clipboard">
+      <param name="bgcolor" value="#FFFFFF">
+      <param name="wmode" value="opaque">
+      <embed src="https://a248.e.akamai.net/assets.github.com/flash/clippy.swf?1261951368?v5"
+             width="110"
+             height="14"
+             name="clippy"
+             quality="high"
+             allowScriptAccess="always"
+             type="application/x-shockwave-flash"
+             pluginspage="http://www.macromedia.com/go/getflashplayer"
+             FlashVars="id=clippy_4738&amp;copied=copied!&amp;copyto=copy to clipboard"
+             bgcolor="#FFFFFF"
+             wmode="opaque"
+      />
+      </object>
+      
+
+    </div>
+
+    <div class="frames">
+      <div class="frame frame-center" data-path="doc/LICENSE/" data-permalink-url="/nbronson/snaptree/blob/b198f84b0c927f6b5cdef080552fc26aa004d3ee/doc/LICENSE" data-title="doc/LICENSE at master from nbronson/snaptree - GitHub" data-type="blob">
+          <ul class="big-actions">
+            <li><a class="file-edit-link minibutton js-rewrite-sha" href="/nbronson/snaptree/edit/b198f84b0c927f6b5cdef080552fc26aa004d3ee/doc/LICENSE" data-method="post" rel="nofollow"><span>Edit this file</span></a></li>
+          </ul>
+
+        <div id="files">
+          <div class="file">
+            <div class="meta">
+              <div class="info">
+                <span class="icon"><img alt="Txt" height="16" src="https://a248.e.akamai.net/assets.github.com/images/icons/txt.png?1252203928" width="16" /></span>
+                <span class="mode" title="File Mode">100644</span>
+                  <span>36 lines (27 sloc)</span>
+                <span>1.715 kb</span>
+              </div>
+              <ul class="actions">
+                <li><a href="/nbronson/snaptree/raw/master/doc/LICENSE" id="raw-url">raw</a></li>
+                  <li><a href="/nbronson/snaptree/blame/master/doc/LICENSE">blame</a></li>
+                <li><a href="/nbronson/snaptree/commits/master/doc/LICENSE" rel="nofollow">history</a></li>
+              </ul>
+            </div>
+              <div class="data type-text">
+      <table cellpadding="0" cellspacing="0" class="lines">
+        <tr>
+          <td>
+            <pre class="line_numbers"><span id="L1" rel="#L1">1</span>
+<span id="L2" rel="#L2">2</span>
+<span id="L3" rel="#L3">3</span>
+<span id="L4" rel="#L4">4</span>
+<span id="L5" rel="#L5">5</span>
+<span id="L6" rel="#L6">6</span>
+<span id="L7" rel="#L7">7</span>
+<span id="L8" rel="#L8">8</span>
+<span id="L9" rel="#L9">9</span>
+<span id="L10" rel="#L10">10</span>
+<span id="L11" rel="#L11">11</span>
+<span id="L12" rel="#L12">12</span>
+<span id="L13" rel="#L13">13</span>
+<span id="L14" rel="#L14">14</span>
+<span id="L15" rel="#L15">15</span>
+<span id="L16" rel="#L16">16</span>
+<span id="L17" rel="#L17">17</span>
+<span id="L18" rel="#L18">18</span>
+<span id="L19" rel="#L19">19</span>
+<span id="L20" rel="#L20">20</span>
+<span id="L21" rel="#L21">21</span>
+<span id="L22" rel="#L22">22</span>
+<span id="L23" rel="#L23">23</span>
+<span id="L24" rel="#L24">24</span>
+<span id="L25" rel="#L25">25</span>
+<span id="L26" rel="#L26">26</span>
+<span id="L27" rel="#L27">27</span>
+<span id="L28" rel="#L28">28</span>
+<span id="L29" rel="#L29">29</span>
+<span id="L30" rel="#L30">30</span>
+<span id="L31" rel="#L31">31</span>
+<span id="L32" rel="#L32">32</span>
+<span id="L33" rel="#L33">33</span>
+<span id="L34" rel="#L34">34</span>
+<span id="L35" rel="#L35">35</span>
+<span id="L36" rel="#L36">36</span>
+</pre>
+          </td>
+          <td width="100%">
+                <div class="highlight"><pre><div class='line' id='LC1'>SNAPTREE LICENSE</div><div class='line' id='LC2'><br/></div><div class='line' id='LC3'>Copyright (c) 2009 Stanford University, unless otherwise specified.</div><div class='line' id='LC4'>All rights reserved.</div><div class='line' id='LC5'><br/></div><div class='line' id='LC6'>This software was developed by the Pervasive Parallelism Laboratory of</div><div class='line' id='LC7'>Stanford University, California, USA.</div><div class='line' id='LC8'><br/></div><div class='line' id='LC9'>Permission to use, copy, modify, and distribute this software in source</div><div class='line' id='LC10'>or binary form for any purpose with or without fee is hereby granted,</div><div class='line' id='LC11'>provided that the following conditions are met:</div><div class='line' id='LC12'><br/></div><div class='line' id='LC13'>&nbsp;&nbsp;&nbsp;1. Redistributions of source code must retain the above copyright</div><div class='
 line' id='LC14'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;notice, this list of conditions and the following disclaimer.</div><div class='line' id='LC15'><br/></div><div class='line' id='LC16'>&nbsp;&nbsp;&nbsp;2. Redistributions in binary form must reproduce the above copyright</div><div class='line' id='LC17'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;notice, this list of conditions and the following disclaimer in the</div><div class='line' id='LC18'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;documentation and/or other materials provided with the distribution.</div><div class='line' id='LC19'><br/></div><div class='line' id='LC20'>&nbsp;&nbsp;&nbsp;3. Neither the name of Stanford University nor the names of its</div><div class='line' id='LC21'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;contributors may be used to endorse or promote products derived</div><div class='line' id='LC22'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;from this software without specific prior written permission.</div><div class='line' 
 id='LC23'><br/></div><div class='line' id='LC24'><br/></div><div class='line' id='LC25'>THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS&#39;&#39; AND</div><div class='line' id='LC26'>ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE</div><div class='line' id='LC27'>IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE</div><div class='line' id='LC28'>ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE</div><div class='line' id='LC29'>FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL</div><div class='line' id='LC30'>DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR</div><div class='line' id='LC31'>SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER</div><div class='line' id='LC32'>CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT</div><div class='line' id='LC33'>LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHE
 RWISE) ARISING IN ANY WAY</div><div class='line' id='LC34'>OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF</div><div class='line' id='LC35'>SUCH DAMAGE.</div><div class='line' id='LC36'><br/></div></pre></div>
+          </td>
+        </tr>
+      </table>
+  </div>
+
+          </div>
+        </div>
+      </div>
+    </div>
+
+  </div>
+
+<div class="frame frame-loading" style="display:none;" data-tree-list-url="/nbronson/snaptree/tree-list/b198f84b0c927f6b5cdef080552fc26aa004d3ee" data-blob-url-prefix="/nbronson/snaptree/blob/b198f84b0c927f6b5cdef080552fc26aa004d3ee">
+  <img src="https://a248.e.akamai.net/assets.github.com/images/modules/ajax/big_spinner_336699.gif?1315937507" height="32" width="32">
+</div>
+
+      </div>
+    </div>
+
+    <!-- footer -->
+    <div id="footer" >
+      
+  <div class="upper_footer">
+     <div class="container" class="clearfix">
+
+       <!--[if IE]><h4 id="blacktocat_ie">GitHub Links</h4><![endif]-->
+       <![if !IE]><h4 id="blacktocat">GitHub Links</h4><![endif]>
+
+       <ul class="footer_nav">
+         <h4>GitHub</h4>
+         <li><a href="https://github.com/about">About</a></li>
+         <li><a href="https://github.com/blog">Blog</a></li>
+         <li><a href="https://github.com/features">Features</a></li>
+         <li><a href="https://github.com/contact">Contact &amp; Support</a></li>
+         <li><a href="https://github.com/training">Training</a></li>
+         <li><a href="http://enterprise.github.com/">GitHub Enterprise</a></li>
+         <li><a href="http://status.github.com/">Site Status</a></li>
+       </ul>
+
+       <ul class="footer_nav">
+         <h4>Tools</h4>
+         <li><a href="http://get.gaug.es/">Gauges: Analyze web traffic</a></li>
+         <li><a href="http://speakerdeck.com">Speakerdeck: Presentations</a></li>
+         <li><a href="https://gist.github.com">Gist: Code snippets</a></li>
+         <li><a href="http://mac.github.com/">GitHub for Mac</a></li>
+         <li><a href="http://mobile.github.com/">Issues for iPhone</a></li>
+         <li><a href="http://jobs.github.com/">Job Board</a></li>
+       </ul>
+
+       <ul class="footer_nav">
+         <h4>Extras</h4>
+         <li><a href="http://shop.github.com/">GitHub Shop</a></li>
+         <li><a href="http://octodex.github.com/">The Octodex</a></li>
+       </ul>
+
+       <ul class="footer_nav">
+         <h4>Documentation</h4>
+         <li><a href="http://help.github.com/">GitHub Help</a></li>
+         <li><a href="http://developer.github.com/">Developer API</a></li>
+         <li><a href="http://github.github.com/github-flavored-markdown/">GitHub Flavored Markdown</a></li>
+         <li><a href="http://pages.github.com/">GitHub Pages</a></li>
+       </ul>
+
+     </div><!-- /.site -->
+  </div><!-- /.upper_footer -->
+
+<div class="lower_footer">
+  <div class="container" class="clearfix">
+    <!--[if IE]><div id="legal_ie"><![endif]-->
+    <![if !IE]><div id="legal"><![endif]>
+      <ul>
+          <li><a href="https://github.com/site/terms">Terms of Service</a></li>
+          <li><a href="https://github.com/site/privacy">Privacy</a></li>
+          <li><a href="https://github.com/security">Security</a></li>
+      </ul>
+
+      <p>&copy; 2011 <span id="_rrt" title="0.07115s from fe10.rs.github.com">GitHub</span> Inc. All rights reserved.</p>
+    </div><!-- /#legal or /#legal_ie-->
+
+      <div class="sponsor">
+        <a href="http://www.rackspace.com" class="logo">
+          <img alt="Dedicated Server" height="36" src="https://a248.e.akamai.net/assets.github.com/images/modules/footer/rackspace_logo.png?v2" width="38" />
+        </a>
+        Powered by the <a href="http://www.rackspace.com ">Dedicated
+        Servers</a> and<br/> <a href="http://www.rackspacecloud.com">Cloud
+        Computing</a> of Rackspace Hosting<span>&reg;</span>
+      </div>
+  </div><!-- /.site -->
+</div><!-- /.lower_footer -->
+
+    </div><!-- /#footer -->
+
+    
+
+<div id="keyboard_shortcuts_pane" class="instapaper_ignore readability-extra" style="display:none">
+  <h2>Keyboard Shortcuts <small><a href="#" class="js-see-all-keyboard-shortcuts">(see all)</a></small></h2>
+
+  <div class="columns threecols">
+    <div class="column first">
+      <h3>Site wide shortcuts</h3>
+      <dl class="keyboard-mappings">
+        <dt>s</dt>
+        <dd>Focus site search</dd>
+      </dl>
+      <dl class="keyboard-mappings">
+        <dt>?</dt>
+        <dd>Bring up this help dialog</dd>
+      </dl>
+    </div><!-- /.column.first -->
+
+    <div class="column middle" style='display:none'>
+      <h3>Commit list</h3>
+      <dl class="keyboard-mappings">
+        <dt>j</dt>
+        <dd>Move selection down</dd>
+      </dl>
+      <dl class="keyboard-mappings">
+        <dt>k</dt>
+        <dd>Move selection up</dd>
+      </dl>
+      <dl class="keyboard-mappings">
+        <dt>c <em>or</em> o <em>or</em> enter</dt>
+        <dd>Open commit</dd>
+      </dl>
+      <dl class="keyboard-mappings">
+        <dt>y</dt>
+        <dd>Expand URL to its canonical form</dd>
+      </dl>
+    </div><!-- /.column.first -->
+
+    <div class="column last" style='display:none'>
+      <h3>Pull request list</h3>
+      <dl class="keyboard-mappings">
+        <dt>j</dt>
+        <dd>Move selection down</dd>
+      </dl>
+      <dl class="keyboard-mappings">
+        <dt>k</dt>
+        <dd>Move selection up</dd>
+      </dl>
+      <dl class="keyboard-mappings">
+        <dt>o <em>or</em> enter</dt>
+        <dd>Open issue</dd>
+      </dl>
+    </div><!-- /.columns.last -->
+
+  </div><!-- /.columns.equacols -->
+
+  <div style='display:none'>
+    <div class="rule"></div>
+
+    <h3>Issues</h3>
+
+    <div class="columns threecols">
+      <div class="column first">
+        <dl class="keyboard-mappings">
+          <dt>j</dt>
+          <dd>Move selection down</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>k</dt>
+          <dd>Move selection up</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>x</dt>
+          <dd>Toggle selection</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>o <em>or</em> enter</dt>
+          <dd>Open issue</dd>
+        </dl>
+      </div><!-- /.column.first -->
+      <div class="column middle">
+        <dl class="keyboard-mappings">
+          <dt>I</dt>
+          <dd>Mark selection as read</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>U</dt>
+          <dd>Mark selection as unread</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>e</dt>
+          <dd>Close selection</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>y</dt>
+          <dd>Remove selection from view</dd>
+        </dl>
+      </div><!-- /.column.middle -->
+      <div class="column last">
+        <dl class="keyboard-mappings">
+          <dt>c</dt>
+          <dd>Create issue</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>l</dt>
+          <dd>Create label</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>i</dt>
+          <dd>Back to inbox</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>u</dt>
+          <dd>Back to issues</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>/</dt>
+          <dd>Focus issues search</dd>
+        </dl>
+      </div>
+    </div>
+  </div>
+
+  <div style='display:none'>
+    <div class="rule"></div>
+
+    <h3>Issues Dashboard</h3>
+
+    <div class="columns threecols">
+      <div class="column first">
+        <dl class="keyboard-mappings">
+          <dt>j</dt>
+          <dd>Move selection down</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>k</dt>
+          <dd>Move selection up</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>o <em>or</em> enter</dt>
+          <dd>Open issue</dd>
+        </dl>
+      </div><!-- /.column.first -->
+    </div>
+  </div>
+
+  <div style='display:none'>
+    <div class="rule"></div>
+
+    <h3>Network Graph</h3>
+    <div class="columns equacols">
+      <div class="column first">
+        <dl class="keyboard-mappings">
+          <dt><span class="badmono">←</span> <em>or</em> h</dt>
+          <dd>Scroll left</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt><span class="badmono">→</span> <em>or</em> l</dt>
+          <dd>Scroll right</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt><span class="badmono">↑</span> <em>or</em> k</dt>
+          <dd>Scroll up</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt><span class="badmono">↓</span> <em>or</em> j</dt>
+          <dd>Scroll down</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>t</dt>
+          <dd>Toggle visibility of head labels</dd>
+        </dl>
+      </div><!-- /.column.first -->
+      <div class="column last">
+        <dl class="keyboard-mappings">
+          <dt>shift <span class="badmono">←</span> <em>or</em> shift h</dt>
+          <dd>Scroll all the way left</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>shift <span class="badmono">→</span> <em>or</em> shift l</dt>
+          <dd>Scroll all the way right</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>shift <span class="badmono">↑</span> <em>or</em> shift k</dt>
+          <dd>Scroll all the way up</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>shift <span class="badmono">↓</span> <em>or</em> shift j</dt>
+          <dd>Scroll all the way down</dd>
+        </dl>
+      </div><!-- /.column.last -->
+    </div>
+  </div>
+
+  <div >
+    <div class="rule"></div>
+    <div class="columns threecols">
+      <div class="column first" >
+        <h3>Source Code Browsing</h3>
+        <dl class="keyboard-mappings">
+          <dt>t</dt>
+          <dd>Activates the file finder</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>l</dt>
+          <dd>Jump to line</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>w</dt>
+          <dd>Switch branch/tag</dd>
+        </dl>
+        <dl class="keyboard-mappings">
+          <dt>y</dt>
+          <dd>Expand URL to its canonical form</dd>
+        </dl>
+      </div>
+    </div>
+  </div>
+</div>
+
+    <div id="markdown-help" class="instapaper_ignore readability-extra">
+  <h2>Markdown Cheat Sheet</h2>
+
+  <div class="cheatsheet-content">
+
+  <div class="mod">
+    <div class="col">
+      <h3>Format Text</h3>
+      <p>Headers</p>
+      <pre>
+# This is an &lt;h1&gt; tag
+## This is an &lt;h2&gt; tag
+###### This is an &lt;h6&gt; tag</pre>
+     <p>Text styles</p>
+     <pre>
+*This text will be italic*
+_This will also be italic_
+**This text will be bold**
+__This will also be bold__
+
+*You **can** combine them*
+</pre>
+    </div>
+    <div class="col">
+      <h3>Lists</h3>
+      <p>Unordered</p>
+      <pre>
+* Item 1
+* Item 2
+  * Item 2a
+  * Item 2b</pre>
+     <p>Ordered</p>
+     <pre>
+1. Item 1
+2. Item 2
+3. Item 3
+   * Item 3a
+   * Item 3b</pre>
+    </div>
+    <div class="col">
+      <h3>Miscellaneous</h3>
+      <p>Images</p>
+      <pre>
+![GitHub Logo](/images/logo.png)
+Format: ![Alt Text](url)
+</pre>
+     <p>Links</p>
+     <pre>
+http://github.com - automatic!
+[GitHub](http://github.com)</pre>
+<p>Blockquotes</p>
+     <pre>
+As Kanye West said:
+
+> We're living the future so
+> the present is our past.
+</pre>
+    </div>
+  </div>
+  <div class="rule"></div>
+
+  <h3>Code Examples in Markdown</h3>
+  <div class="col">
+      <p>Syntax highlighting with <a href="http://github.github.com/github-flavored-markdown/" title="GitHub Flavored Markdown" target="_blank">GFM</a></p>
+      <pre>
+```javascript
+function fancyAlert(arg) {
+  if(arg) {
+    $.facebox({div:'#foo'})
+  }
+}
+```</pre>
+    </div>
+    <div class="col">
+      <p>Or, indent your code 4 spaces</p>
+      <pre>
+Here is a Python code example
+without syntax highlighting:
+
+    def foo:
+      if not bar:
+        return true</pre>
+    </div>
+    <div class="col">
+      <p>Inline code for comments</p>
+      <pre>
+I think you should use an
+`&lt;addr&gt;` element here instead.</pre>
+    </div>
+  </div>
+
+  </div>
+</div>
+
+
+    <div class="context-overlay"></div>
+
+    <div class="ajax-error-message">
+      <p><span class="icon"></span> Something went wrong with that request. Please try again. <a href="javascript:;" class="ajax-error-dismiss">Dismiss</a></p>
+    </div>
+
+    
+    
+    
+  </body>
+</html>
+

Added: cassandra/trunk/lib/snaptree-0.1-SNAPSHOT.jar
URL: http://svn.apache.org/viewvc/cassandra/trunk/lib/snaptree-0.1-SNAPSHOT.jar?rev=1225001&view=auto
==============================================================================
Files cassandra/trunk/lib/snaptree-0.1-SNAPSHOT.jar (added) and cassandra/trunk/lib/snaptree-0.1-SNAPSHOT.jar Tue Dec 27 20:17:17 2011 differ

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java Tue Dec 27 20:17:17 2011
@@ -18,31 +18,24 @@
 package org.apache.cassandra.db;
 
 import java.nio.ByteBuffer;
-import java.security.MessageDigest;
 import java.util.Collection;
 import java.util.Iterator;
-import java.util.Map;
 import java.util.SortedSet;
-import java.util.concurrent.ConcurrentSkipListMap;
-import java.util.concurrent.atomic.AtomicReference;
 
+import com.google.common.base.Function;
+import com.google.common.base.Functions;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
-import org.apache.cassandra.config.CFMetaData;
-import org.apache.cassandra.config.DatabaseDescriptor;
-import org.apache.cassandra.db.filter.QueryPath;
 import org.apache.cassandra.db.marshal.AbstractType;
 import org.apache.cassandra.io.util.IIterableColumns;
 import org.apache.cassandra.utils.Allocator;
-import org.apache.cassandra.utils.FBUtilities;
 import org.apache.cassandra.utils.HeapAllocator;
 
 public abstract class AbstractColumnContainer implements IColumnContainer, IIterableColumns
 {
     private static Logger logger = LoggerFactory.getLogger(AbstractColumnContainer.class);
 
-    protected final AtomicReference<DeletionInfo> deletionInfo = new AtomicReference<DeletionInfo>(new DeletionInfo());
     protected final ISortedColumns columns;
 
     protected AbstractColumnContainer(ISortedColumns columns)
@@ -53,20 +46,12 @@ public abstract class AbstractColumnCont
     @Deprecated // TODO this is a hack to set initial value outside constructor
     public void delete(int localtime, long timestamp)
     {
-        deletionInfo.set(new DeletionInfo(timestamp, localtime));
+        columns.delete(new ISortedColumns.DeletionInfo(timestamp, localtime));
     }
 
     public void delete(AbstractColumnContainer cc2)
     {
-        // Keeping deletion info for max markedForDeleteAt value
-        DeletionInfo current;
-        DeletionInfo cc2Info = cc2.deletionInfo.get();
-        while (true)
-        {
-             current = deletionInfo.get();
-             if (current.markedForDeleteAt >= cc2Info.markedForDeleteAt || deletionInfo.compareAndSet(current, cc2Info))
-                 break;
-        }
+        columns.delete(cc2.columns.getDeletionInfo());
     }
 
     public boolean isMarkedForDelete()
@@ -76,12 +61,12 @@ public abstract class AbstractColumnCont
 
     public long getMarkedForDeleteAt()
     {
-        return deletionInfo.get().markedForDeleteAt;
+        return columns.getDeletionInfo().markedForDeleteAt;
     }
 
     public int getLocalDeletionTime()
     {
-        return deletionInfo.get().localDeletionTime;
+        return columns.getDeletionInfo().localDeletionTime;
     }
 
     public AbstractType getComparator()
@@ -96,27 +81,20 @@ public abstract class AbstractColumnCont
      */
     public void maybeResetDeletionTimes(int gcBefore)
     {
-        while (true)
-        {
-            DeletionInfo current = deletionInfo.get();
-            // Stop if either we don't need to change the deletion info (it's
-            // still MIN_VALUE or not expired yet) or we've succesfully changed it
-            if (current.localDeletionTime == Integer.MIN_VALUE
-                || current.localDeletionTime > gcBefore
-                || deletionInfo.compareAndSet(current, new DeletionInfo()))
-            {
-                break;
-            }
-        }
+        columns.maybeResetDeletionTimes(gcBefore);
     }
 
     /**
      * We need to go through each column in the column container and resolve it before adding
      */
+    public void addAll(AbstractColumnContainer cc, Allocator allocator, Function<IColumn, IColumn> transformation)
+    {
+        columns.addAll(cc.columns, allocator, transformation);
+    }
+
     public void addAll(AbstractColumnContainer cc, Allocator allocator)
     {
-        columns.addAll(cc.columns, allocator);
-        delete(cc);
+        addAll(cc, allocator, Functions.<IColumn>identity());
     }
 
     public void addColumn(IColumn column)
@@ -166,39 +144,7 @@ public abstract class AbstractColumnCont
 
     public void retainAll(AbstractColumnContainer container)
     {
-        Iterator<IColumn> iter = iterator();
-        Iterator<IColumn> toRetain = container.iterator();
-        IColumn current = iter.hasNext() ? iter.next() : null;
-        IColumn retain = toRetain.hasNext() ? toRetain.next() : null;
-        AbstractType comparator = getComparator();
-        while (current != null && retain != null)
-        {
-            int c = comparator.compare(current.name(), retain.name());
-            if (c == 0)
-            {
-                if (current instanceof SuperColumn)
-                {
-                    assert retain instanceof SuperColumn;
-                    ((SuperColumn)current).retainAll((SuperColumn)retain);
-                }
-                current = iter.hasNext() ? iter.next() : null;
-                retain = toRetain.hasNext() ? toRetain.next() : null;
-            }
-            else if (c < 0)
-            {
-                iter.remove();
-                current = iter.hasNext() ? iter.next() : null;
-            }
-            else // c > 0
-            {
-                retain = toRetain.hasNext() ? toRetain.next() : null;
-            }
-        }
-        while (current != null)
-        {
-            iter.remove();
-            current = iter.hasNext() ? iter.next() : null;
-        }
+        columns.retainAll(container.columns);
     }
 
     public int getColumnCount()
@@ -249,23 +195,6 @@ public abstract class AbstractColumnCont
         return columns.reverseIterator(start);
     }
 
-    protected static class DeletionInfo
-    {
-        public final long markedForDeleteAt;
-        public final int localDeletionTime;
-
-        public DeletionInfo()
-        {
-            this(Long.MIN_VALUE, Integer.MIN_VALUE);
-        }
-
-        public DeletionInfo(long markedForDeleteAt, int localDeletionTime)
-        {
-            this.markedForDeleteAt = markedForDeleteAt;
-            this.localDeletionTime = localDeletionTime;
-        }
-    }
-
     public boolean hasExpiredTombstones(int gcBefore)
     {
         if (isMarkedForDelete() && getLocalDeletionTime() < gcBefore)

Added: cassandra/trunk/src/java/org/apache/cassandra/db/AbstractThreadUnsafeSortedColumns.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/AbstractThreadUnsafeSortedColumns.java?rev=1225001&view=auto
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/AbstractThreadUnsafeSortedColumns.java (added)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/AbstractThreadUnsafeSortedColumns.java Tue Dec 27 20:17:17 2011
@@ -0,0 +1,111 @@
+/**
+ * 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.db;
+
+import java.util.Iterator;
+
+import com.google.common.base.Function;
+
+import org.apache.cassandra.db.marshal.AbstractType;
+import org.apache.cassandra.utils.Allocator;
+
+public abstract class AbstractThreadUnsafeSortedColumns implements ISortedColumns
+{
+    private DeletionInfo deletionInfo;
+
+    public AbstractThreadUnsafeSortedColumns()
+    {
+        deletionInfo = new DeletionInfo();
+    }
+
+    public DeletionInfo getDeletionInfo()
+    {
+        return deletionInfo;
+    }
+
+    public void delete(DeletionInfo newInfo)
+    {
+        if (deletionInfo.markedForDeleteAt < newInfo.markedForDeleteAt)
+            // since deletion info is immutable, aliasing it is fine
+            deletionInfo = newInfo;
+    }
+
+    public void maybeResetDeletionTimes(int gcBefore)
+    {
+        // Update if it's not MIN_VALUE anymore and it has expired
+        if (deletionInfo.localDeletionTime != Integer.MIN_VALUE && deletionInfo.localDeletionTime <= gcBefore)
+            deletionInfo = new DeletionInfo();
+    }
+
+    public void retainAll(ISortedColumns columns)
+    {
+        Iterator<IColumn> iter = iterator();
+        Iterator<IColumn> toRetain = columns.iterator();
+        IColumn current = iter.hasNext() ? iter.next() : null;
+        IColumn retain = toRetain.hasNext() ? toRetain.next() : null;
+        AbstractType comparator = getComparator();
+        while (current != null && retain != null)
+        {
+            int c = comparator.compare(current.name(), retain.name());
+            if (c == 0)
+            {
+                if (current instanceof SuperColumn)
+                {
+                    assert retain instanceof SuperColumn;
+                    ((SuperColumn)current).retainAll((SuperColumn)retain);
+                }
+                current = iter.hasNext() ? iter.next() : null;
+                retain = toRetain.hasNext() ? toRetain.next() : null;
+            }
+            else if (c < 0)
+            {
+                iter.remove();
+                current = iter.hasNext() ? iter.next() : null;
+            }
+            else // c > 0
+            {
+                retain = toRetain.hasNext() ? toRetain.next() : null;
+            }
+        }
+        while (current != null)
+        {
+            iter.remove();
+            current = iter.hasNext() ? iter.next() : null;
+        }
+    }
+
+    // Implementations should implement this rather than addAll to avoid
+    // having to care about the deletion infos
+    protected abstract void addAllColumns(ISortedColumns columns, Allocator allocator, Function<IColumn, IColumn> transformation);
+
+    public void addAll(ISortedColumns columns, Allocator allocator, Function<IColumn, IColumn> transformation)
+    {
+        addAllColumns(columns, allocator, transformation);
+        delete(columns.getDeletionInfo());
+    }
+
+    public boolean isEmpty()
+    {
+        return size() == 0;
+    }
+
+    public int getEstimatedColumnCount()
+    {
+        return size();
+    }
+}

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java Tue Dec 27 20:17:17 2011
@@ -20,6 +20,8 @@ package org.apache.cassandra.db;
 import java.nio.ByteBuffer;
 import java.util.*;
 
+import com.google.common.base.Function;
+
 import org.apache.cassandra.db.marshal.AbstractType;
 import org.apache.cassandra.utils.Allocator;
 
@@ -30,10 +32,11 @@ import org.apache.cassandra.utils.Alloca
  * main operations performed are iterating over the map and adding columns
  * (especially if insertion is in sorted order).
  */
-public class ArrayBackedSortedColumns extends ArrayList<IColumn> implements ISortedColumns
+public class ArrayBackedSortedColumns extends AbstractThreadUnsafeSortedColumns implements ISortedColumns
 {
     private final AbstractType<?> comparator;
     private final boolean reversed;
+    private final ArrayList<IColumn> columns;
 
     public static final ISortedColumns.Factory factory = new Factory()
     {
@@ -58,13 +61,14 @@ public class ArrayBackedSortedColumns ex
         super();
         this.comparator = comparator;
         this.reversed = reversed;
+        this.columns = new ArrayList<IColumn>();
     }
 
     private ArrayBackedSortedColumns(Collection<IColumn> columns, AbstractType<?> comparator, boolean reversed)
     {
-        super(columns);
         this.comparator = comparator;
         this.reversed = reversed;
+        this.columns = new ArrayList<IColumn>(columns);
     }
 
     public ISortedColumns.Factory getFactory()
@@ -79,7 +83,7 @@ public class ArrayBackedSortedColumns ex
 
     public ISortedColumns cloneMe()
     {
-        return new ArrayBackedSortedColumns(this, comparator, reversed);
+        return new ArrayBackedSortedColumns(columns, comparator, reversed);
     }
 
     public boolean isInsertReversed()
@@ -98,7 +102,7 @@ public class ArrayBackedSortedColumns ex
     public IColumn getColumn(ByteBuffer name)
     {
         int pos = binarySearch(name);
-        return pos >= 0 ? get(pos) : null;
+        return pos >= 0 ? columns.get(pos) : null;
     }
 
     /**
@@ -113,14 +117,14 @@ public class ArrayBackedSortedColumns ex
      */
     public void addColumn(IColumn column, Allocator allocator)
     {
-        if (isEmpty())
+        if (columns.isEmpty())
         {
-            add(column);
+            columns.add(column);
             return;
         }
 
         // Fast path if inserting at the tail
-        int c = compare(get(size() - 1).name(), column.name());
+        int c = compare(columns.get(size() - 1).name(), column.name());
         // note that we want an assertion here (see addColumn javadoc), but we also want that if
         // assertion are disabled, addColumn works correctly with unsorted input
         assert c <= 0 : "Added column does not sort as the " + (reversed ? "first" : "last") + " column";
@@ -128,7 +132,7 @@ public class ArrayBackedSortedColumns ex
         if (c < 0)
         {
             // Insert as last
-            add(column);
+            columns.add(column);
         }
         else if (c == 0)
         {
@@ -141,7 +145,7 @@ public class ArrayBackedSortedColumns ex
             if (pos >= 0)
                 resolveAgainst(pos, column, allocator);
             else
-                add(-pos-1, column);
+                columns.add(-pos-1, column);
         }
     }
 
@@ -151,7 +155,7 @@ public class ArrayBackedSortedColumns ex
      */
     private void resolveAgainst(int i, IColumn column, Allocator allocator)
     {
-        IColumn oldColumn = get(i);
+        IColumn oldColumn = columns.get(i);
         if (oldColumn instanceof SuperColumn)
         {
             // Delegated to SuperColumn
@@ -162,7 +166,7 @@ public class ArrayBackedSortedColumns ex
         {
             // calculate reconciled col from old (existing) col and new col
             IColumn reconciledColumn = column.reconcile(oldColumn, allocator);
-            set(i, reconciledColumn);
+            columns.set(i, reconciledColumn);
         }
     }
 
@@ -181,7 +185,7 @@ public class ArrayBackedSortedColumns ex
         while (low <= high)
         {
             mid = (low + high) >> 1;
-            if ((result = compare(name, get(mid).name())) > 0)
+            if ((result = compare(name, columns.get(mid).name())) > 0)
             {
                 low = mid + 1;
             }
@@ -197,46 +201,46 @@ public class ArrayBackedSortedColumns ex
         return -mid - (result < 0 ? 1 : 2);
     }
 
-    public void addAll(ISortedColumns cm, Allocator allocator)
+    protected void addAllColumns(ISortedColumns cm, Allocator allocator, Function<IColumn, IColumn> transformation)
     {
         if (cm.isEmpty())
             return;
 
-        IColumn[] copy = toArray(new IColumn[size()]);
+        IColumn[] copy = columns.toArray(new IColumn[size()]);
         int idx = 0;
         Iterator<IColumn> other = reversed ? cm.reverseIterator() : cm.iterator();
         IColumn otherColumn = other.next();
 
-        clear();
+        columns.clear();
 
         while (idx < copy.length && otherColumn != null)
         {
             int c = compare(copy[idx].name(), otherColumn.name());
             if (c < 0)
             {
-                add(copy[idx]);
+                columns.add(copy[idx]);
                 idx++;
             }
             else if (c > 0)
             {
-                add(otherColumn);
+                columns.add(transformation.apply(otherColumn));
                 otherColumn = other.hasNext() ? other.next() : null;
             }
             else // c == 0
             {
-                add(copy[idx]);
-                resolveAgainst(size() - 1, otherColumn, allocator);
+                columns.add(copy[idx]);
+                resolveAgainst(size() - 1, transformation.apply(otherColumn), allocator);
                 idx++;
                 otherColumn = other.hasNext() ? other.next() : null;
             }
         }
         while (idx < copy.length)
         {
-            add(copy[idx++]);
+            columns.add(copy[idx++]);
         }
         while (otherColumn != null)
         {
-            add(otherColumn);
+            columns.add(transformation.apply(otherColumn));
             otherColumn = other.hasNext() ? other.next() : null;
         }
     }
@@ -249,7 +253,7 @@ public class ArrayBackedSortedColumns ex
         int pos = binarySearch(oldColumn.name());
         if (pos >= 0)
         {
-            set(pos, newColumn);
+            columns.set(pos, newColumn);
         }
 
         return pos >= 0;
@@ -257,7 +261,7 @@ public class ArrayBackedSortedColumns ex
 
     public Collection<IColumn> getSortedColumns()
     {
-        return reversed ? new ReverseSortedCollection() : this;
+        return reversed ? new ReverseSortedCollection() : columns;
     }
 
     public Collection<IColumn> getReverseSortedColumns()
@@ -272,29 +276,34 @@ public class ArrayBackedSortedColumns ex
     {
         int pos = binarySearch(name);
         if (pos >= 0)
-            remove(pos);
+            columns.remove(pos);
     }
 
-    public SortedSet<ByteBuffer> getColumnNames()
+    public int size()
     {
-        // we could memoize the created set but it's unlikely we'll call this method a lot on the same object anyway
-        return new ColumnNamesSet();
+        return columns.size();
+    }
+
+    public void clear()
+    {
+        columns.clear();
     }
 
-    public int getEstimatedColumnCount()
+    public SortedSet<ByteBuffer> getColumnNames()
     {
-        return size();
+        // we could memoize the created set but it's unlikely we'll call this method a lot on the same object anyway
+        return new ColumnNamesSet();
     }
 
     @Override
     public Iterator<IColumn> iterator()
     {
-        return reversed ? reverseInternalIterator(size()) : super.iterator();
+        return reversed ? reverseInternalIterator(size()) : columns.iterator();
     }
 
     public Iterator<IColumn> reverseIterator()
     {
-        return reversed ? super.iterator() : reverseInternalIterator(size());
+        return reversed ? columns.iterator() : reverseInternalIterator(size());
     }
 
     public Iterator<IColumn> iterator(ByteBuffer start)
@@ -305,7 +314,7 @@ public class ArrayBackedSortedColumns ex
         else if (reversed)
             // listIterator.previous() doesn't return the current element at first but the previous one
             idx++;
-        return reversed ? reverseInternalIterator(idx) : listIterator(idx);
+        return reversed ? reverseInternalIterator(idx) : columns.listIterator(idx);
     }
 
     public Iterator<IColumn> reverseIterator(ByteBuffer start)
@@ -316,12 +325,12 @@ public class ArrayBackedSortedColumns ex
         else if (!reversed)
             // listIterator.previous() doesn't return the current element at first but the previous one
             idx++;
-        return reversed ? listIterator(idx) : reverseInternalIterator(idx);
+        return reversed ? columns.listIterator(idx) : reverseInternalIterator(idx);
     }
 
     private Iterator<IColumn> reverseInternalIterator(int idx)
     {
-        final ListIterator<IColumn> iter = listIterator(idx);
+        final ListIterator<IColumn> iter = columns.listIterator(idx);
         return new Iterator<IColumn>()
         {
             public boolean hasNext()
@@ -345,7 +354,7 @@ public class ArrayBackedSortedColumns ex
     {
         public int size()
         {
-            return ArrayBackedSortedColumns.this.size();
+            return columns.size();
         }
 
         public Iterator<IColumn> iterator()
@@ -361,12 +370,12 @@ public class ArrayBackedSortedColumns ex
 
                 public IColumn next()
                 {
-                    return ArrayBackedSortedColumns.this.get(idx--);
+                    return columns.get(idx--);
                 }
 
                 public void remove()
                 {
-                    ArrayBackedSortedColumns.this.remove(idx--);
+                    columns.remove(idx--);
                 }
             };
         }
@@ -376,12 +385,12 @@ public class ArrayBackedSortedColumns ex
     {
         public int size()
         {
-            return ArrayBackedSortedColumns.this.size();
+            return columns.size();
         }
 
         public Iterator<IColumn> iterator()
         {
-            return ArrayBackedSortedColumns.super.iterator();
+            return columns.iterator();
         }
     }
 
@@ -389,7 +398,7 @@ public class ArrayBackedSortedColumns ex
     {
         public int size()
         {
-            return ArrayBackedSortedColumns.this.size();
+            return columns.size();
         }
 
         public Iterator<ByteBuffer> iterator()
@@ -416,7 +425,7 @@ public class ArrayBackedSortedColumns ex
 
         public Comparator<ByteBuffer> comparator()
         {
-            return ArrayBackedSortedColumns.this.getComparator();
+            return getComparator();
         }
 
         public ByteBuffer first()
@@ -424,7 +433,7 @@ public class ArrayBackedSortedColumns ex
             final ArrayBackedSortedColumns outerList = ArrayBackedSortedColumns.this;
             if (outerList.isEmpty())
                 throw new NoSuchElementException();
-            return outerList.get(outerList.reversed ? size() - 1 : 0).name();
+            return outerList.columns.get(outerList.reversed ? size() - 1 : 0).name();
         }
 
         public ByteBuffer last()
@@ -432,7 +441,7 @@ public class ArrayBackedSortedColumns ex
             final ArrayBackedSortedColumns outerList = ArrayBackedSortedColumns.this;
             if (outerList.isEmpty())
                 throw new NoSuchElementException();
-            return outerList.get(outerList.reversed ? 0 : size() - 1).name();
+            return outerList.columns.get(outerList.reversed ? 0 : size() - 1).name();
         }
 
         /*

Added: cassandra/trunk/src/java/org/apache/cassandra/db/AtomicSortedColumns.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/AtomicSortedColumns.java?rev=1225001&view=auto
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/AtomicSortedColumns.java (added)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/AtomicSortedColumns.java Tue Dec 27 20:17:17 2011
@@ -0,0 +1,394 @@
+/**
+ * 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.db;
+
+import java.nio.ByteBuffer;
+import java.util.*;
+import java.util.concurrent.atomic.AtomicReference;
+
+import com.google.common.base.Function;
+import edu.stanford.ppl.concurrent.SnapTreeMap;
+
+import org.apache.cassandra.db.marshal.AbstractType;
+import org.apache.cassandra.utils.Allocator;
+
+
+/**
+ * A thread-safe and atomic ISortedColumns implementation.
+ * Operations (in particular addAll) on this implemenation are atomic and
+ * isolated (in the sense of ACID). Typically a addAll is guaranteed that no
+ * other thread can see the state where only parts but not all columns have
+ * been added.
+ *
+ * The implementation uses snaptree (https://github.com/nbronson/snaptree),
+ * and in particular it's copy-on-write clone operation to achieve its
+ * atomicity guarantee.
+ *
+ * WARNING: removing element through getSortedColumns().iterator() is *not*
+ * isolated of other operations and could actually be fully ignored in the
+ * face of a concurrent. Don't use it unless in a non-concurrent context.
+ *
+ * TODO: check the snaptree license make it ok to use
+ */
+public class AtomicSortedColumns implements ISortedColumns
+{
+    private final AtomicReference<Holder> ref;
+
+    public static final ISortedColumns.Factory factory = new Factory()
+    {
+        public ISortedColumns create(AbstractType<?> comparator, boolean insertReversed)
+        {
+            return new AtomicSortedColumns(comparator);
+        }
+
+        public ISortedColumns fromSorted(SortedMap<ByteBuffer, IColumn> sortedMap, boolean insertReversed)
+        {
+            return new AtomicSortedColumns(sortedMap);
+        }
+    };
+
+    public static ISortedColumns.Factory factory()
+    {
+        return factory;
+    }
+
+    private AtomicSortedColumns(AbstractType<?> comparator)
+    {
+        this(new Holder(comparator));
+    }
+
+    private AtomicSortedColumns(SortedMap<ByteBuffer, IColumn> columns)
+    {
+        this(new Holder(columns));
+    }
+
+    private AtomicSortedColumns(Holder holder)
+    {
+        this.ref = new AtomicReference<Holder>(holder);
+    }
+
+    public AbstractType<?> getComparator()
+    {
+        return (AbstractType)ref.get().map.comparator();
+    }
+
+    public ISortedColumns.Factory getFactory()
+    {
+        return factory;
+    }
+
+    public ISortedColumns cloneMe()
+    {
+        return new AtomicSortedColumns(ref.get().cloneMe());
+    }
+
+    public DeletionInfo getDeletionInfo()
+    {
+        return ref.get().deletionInfo;
+    }
+
+    public void delete(DeletionInfo info)
+    {
+        // Keeping deletion info for max markedForDeleteAt value
+        Holder current;
+        do
+        {
+            current = ref.get();
+            if (current.deletionInfo.markedForDeleteAt >= info.markedForDeleteAt)
+                break;
+        }
+        while (!ref.compareAndSet(current, current.with(info)));
+    }
+
+    public void maybeResetDeletionTimes(int gcBefore)
+    {
+        Holder current;
+        do
+        {
+            current = ref.get();
+            // Stop if we don't need to change the deletion info (it's still MIN_VALUE or not expired yet)
+            if (current.deletionInfo.localDeletionTime == Integer.MIN_VALUE || current.deletionInfo.localDeletionTime > gcBefore)
+                break;
+        }
+        while (!ref.compareAndSet(current, current.with(new DeletionInfo())));
+    }
+
+    public void retainAll(ISortedColumns columns)
+    {
+        Holder current, modified;
+        do
+        {
+            current = ref.get();
+            modified = current.cloneMe();
+            modified.retainAll(columns);
+        }
+        while (!ref.compareAndSet(current, modified));
+    }
+
+    public void addColumn(IColumn column, Allocator allocator)
+    {
+        Holder current, modified;
+        do
+        {
+            current = ref.get();
+            modified = current.cloneMe();
+            modified.addColumn(column, allocator);
+        }
+        while (!ref.compareAndSet(current, modified));
+    }
+
+    public void addAll(ISortedColumns cm, Allocator allocator, Function<IColumn, IColumn> transformation)
+    {
+        /*
+         * This operation needs to atomicity and isolation. To that end, we
+         * add the new column to a copy of the map (a cheap O(1) snapTree
+         * clone) and atomically compare and swap when everything has been
+         * added. Of course, we must not forget to update the deletion times
+         * too.
+         * In case we are adding a lot of columns, failing the final compare
+         * and swap could be expensive. To mitigate, we check we haven't been
+         * beaten by another thread after every column addition. If we have,
+         * we bail early, avoiding unnecessary work if possible.
+         */
+        Holder current, modified;
+        main_loop:
+        do
+        {
+            current = ref.get();
+            DeletionInfo newDelInfo = current.deletionInfo;
+            if (newDelInfo.markedForDeleteAt < cm.getDeletionInfo().markedForDeleteAt)
+                newDelInfo = cm.getDeletionInfo();
+            modified = new Holder(current.map.clone(), newDelInfo);
+
+            for (IColumn column : cm.getSortedColumns())
+            {
+                modified.addColumn(transformation.apply(column), allocator);
+                // bail early if we know we've been beaten
+                if (ref.get() != current)
+                    continue main_loop;
+            }
+        }
+        while (!ref.compareAndSet(current, modified));
+    }
+
+    public boolean replace(IColumn oldColumn, IColumn newColumn)
+    {
+        if (!oldColumn.name().equals(newColumn.name()))
+            throw new IllegalArgumentException();
+
+        Holder current, modified;
+        boolean replaced;
+        do
+        {
+            current = ref.get();
+            modified = current.cloneMe();
+            replaced = modified.map.replace(oldColumn.name(), oldColumn, newColumn);
+        }
+        while (!ref.compareAndSet(current, modified));
+        return replaced;
+    }
+
+    public void removeColumn(ByteBuffer name)
+    {
+        Holder current, modified;
+        do
+        {
+            current = ref.get();
+            modified = current.cloneMe();
+            modified.map.remove(name);
+        }
+        while (!ref.compareAndSet(current, modified));
+    }
+
+    public void clear()
+    {
+        Holder current, modified;
+        do
+        {
+            current = ref.get();
+            modified = current.clear();
+        }
+        while (!ref.compareAndSet(current, modified));
+    }
+
+    public IColumn getColumn(ByteBuffer name)
+    {
+        return ref.get().map.get(name);
+    }
+
+    public SortedSet<ByteBuffer> getColumnNames()
+    {
+        return ref.get().map.keySet();
+    }
+
+    public Collection<IColumn> getSortedColumns()
+    {
+        return ref.get().map.values();
+    }
+
+    public Collection<IColumn> getReverseSortedColumns()
+    {
+        return ref.get().map.descendingMap().values();
+    }
+
+    public int size()
+    {
+        return ref.get().map.size();
+    }
+
+    public int getEstimatedColumnCount()
+    {
+        return size();
+    }
+
+    public boolean isEmpty()
+    {
+        return ref.get().map.isEmpty();
+    }
+
+    public Iterator<IColumn> iterator()
+    {
+        return getSortedColumns().iterator();
+    }
+
+    public Iterator<IColumn> reverseIterator()
+    {
+        return getReverseSortedColumns().iterator();
+    }
+
+    public Iterator<IColumn> iterator(ByteBuffer start)
+    {
+        return ref.get().map.tailMap(start).values().iterator();
+    }
+
+    public Iterator<IColumn> reverseIterator(ByteBuffer start)
+    {
+        return ref.get().map.descendingMap().tailMap(start).values().iterator();
+    }
+
+    public boolean isInsertReversed()
+    {
+        return false;
+    }
+
+    private static class Holder
+    {
+        final SnapTreeMap<ByteBuffer, IColumn> map;
+        final DeletionInfo deletionInfo;
+
+        Holder(AbstractType<?> comparator)
+        {
+            this(new SnapTreeMap<ByteBuffer, IColumn>(comparator), new DeletionInfo());
+        }
+
+        Holder(SortedMap<ByteBuffer, IColumn> columns)
+        {
+            this(new SnapTreeMap<ByteBuffer, IColumn>(columns), new DeletionInfo());
+        }
+
+        Holder(SnapTreeMap<ByteBuffer, IColumn> map, DeletionInfo deletionInfo)
+        {
+            this.map = map;
+            this.deletionInfo = deletionInfo;
+        }
+
+        Holder cloneMe()
+        {
+            return with(map.clone());
+        }
+
+        Holder with(DeletionInfo info)
+        {
+            return new Holder(map, info);
+        }
+
+        Holder with(SnapTreeMap<ByteBuffer, IColumn> newMap)
+        {
+            return new Holder(newMap, deletionInfo);
+        }
+
+        // There is no point in cloning the underlying map to clear it
+        // afterwards.
+        Holder clear()
+        {
+            return new Holder(new SnapTreeMap<ByteBuffer, IColumn>(map.comparator()), deletionInfo);
+        }
+
+        void addColumn(IColumn column, Allocator allocator)
+        {
+            ByteBuffer name = column.name();
+            IColumn oldColumn;
+            while ((oldColumn = map.putIfAbsent(name, column)) != null)
+            {
+                if (oldColumn instanceof SuperColumn)
+                {
+                    assert column instanceof SuperColumn;
+                    ((SuperColumn) oldColumn).putColumn((SuperColumn)column, allocator);
+                    break;  // Delegated to SuperColumn
+                }
+                else
+                {
+                    // calculate reconciled col from old (existing) col and new col
+                    IColumn reconciledColumn = column.reconcile(oldColumn, allocator);
+                    if (map.replace(name, oldColumn, reconciledColumn))
+                        break;
+
+                    // We failed to replace column due to a concurrent update or a concurrent removal. Keep trying.
+                    // (Currently, concurrent removal should not happen (only updates), but let us support that anyway.)
+                }
+            }
+        }
+
+        void retainAll(ISortedColumns columns)
+        {
+            Iterator<IColumn> iter = map.values().iterator();
+            Iterator<IColumn> toRetain = columns.iterator();
+            IColumn current = iter.hasNext() ? iter.next() : null;
+            IColumn retain = toRetain.hasNext() ? toRetain.next() : null;
+            Comparator<? super ByteBuffer> comparator = map.comparator();
+            while (current != null && retain != null)
+            {
+                int c = comparator.compare(current.name(), retain.name());
+                if (c == 0)
+                {
+                    if (current instanceof SuperColumn)
+                    {
+                        assert retain instanceof SuperColumn;
+                        ((SuperColumn)current).retainAll((SuperColumn)retain);
+                    }
+                    current = iter.hasNext() ? iter.next() : null;
+                    retain = toRetain.hasNext() ? toRetain.next() : null;
+                }
+                else if (c < 0)
+                {
+                    iter.remove();
+                    current = iter.hasNext() ? iter.next() : null;
+                }
+                else // c > 0
+                {
+                    retain = toRetain.hasNext() ? toRetain.next() : null;
+                }
+            }
+            while (current != null)
+            {
+                iter.remove();
+                current = iter.hasNext() ? iter.next() : null;
+            }
+        }
+    }
+}

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java Tue Dec 27 20:17:17 2011
@@ -76,7 +76,7 @@ public class CollationController
         logger.debug("collectTimeOrderedData");
 
         ISortedColumns.Factory factory = mutableColumns
-                                       ? ThreadSafeSortedColumns.factory()
+                                       ? AtomicSortedColumns.factory()
                                        : TreeMapBackedSortedColumns.factory();
         ColumnFamily container = ColumnFamily.create(cfs.metadata, factory, filter.filter.isReversed());
         List<IColumnIterator> iterators = new ArrayList<IColumnIterator>();
@@ -209,7 +209,7 @@ public class CollationController
     {
         logger.debug("collectAllData");
         ISortedColumns.Factory factory = mutableColumns
-                                       ? ThreadSafeSortedColumns.factory()
+                                       ? AtomicSortedColumns.factory()
                                        : ArrayBackedSortedColumns.factory();
         List<IColumnIterator> iterators = new ArrayList<IColumnIterator>();
         ColumnFamily returnCF = ColumnFamily.create(cfs.metadata, factory, filter.filter.isReversed());

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamily.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamily.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamily.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamily.java Tue Dec 27 20:17:17 2011
@@ -61,7 +61,7 @@ public class ColumnFamily extends Abstra
 
     public static ColumnFamily create(CFMetaData cfm)
     {
-        return create(cfm, ThreadSafeSortedColumns.factory());
+        return create(cfm, TreeMapBackedSortedColumns.factory());
     }
 
     public static ColumnFamily create(CFMetaData cfm, ISortedColumns.Factory factory)
@@ -84,8 +84,7 @@ public class ColumnFamily extends Abstra
     public ColumnFamily cloneMeShallow(ISortedColumns.Factory factory, boolean reversedInsertOrder)
     {
         ColumnFamily cf = ColumnFamily.create(cfm, factory, reversedInsertOrder);
-        // since deletion info is immutable, aliasing it is fine
-        cf.deletionInfo.set(deletionInfo.get());
+        cf.delete(this);
         return cf;
     }
 
@@ -108,8 +107,7 @@ public class ColumnFamily extends Abstra
     public ColumnFamily cloneMe()
     {
         ColumnFamily cf = new ColumnFamily(cfm, columns.cloneMe());
-        // since deletion info is immutable, aliasing it is fine
-        cf.deletionInfo.set(deletionInfo.get());
+        cf.delete(this);
         return cf;
     }
 

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilySerializer.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilySerializer.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilySerializer.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilySerializer.java Tue Dec 27 20:17:17 2011
@@ -115,7 +115,7 @@ public class ColumnFamilySerializer impl
 
     public ColumnFamily deserialize(DataInput dis) throws IOException
     {
-        return deserialize(dis, IColumnSerializer.Flag.LOCAL, ThreadSafeSortedColumns.factory());
+        return deserialize(dis, IColumnSerializer.Flag.LOCAL, TreeMapBackedSortedColumns.factory());
     }
 
     public ColumnFamily deserialize(DataInput dis, IColumnSerializer.Flag flag, ISortedColumns.Factory factory) throws IOException

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java Tue Dec 27 20:17:17 2011
@@ -23,6 +23,8 @@ import java.util.Iterator;
 import java.util.SortedMap;
 import java.util.SortedSet;
 
+import com.google.common.base.Function;
+
 import org.apache.cassandra.db.marshal.AbstractType;
 import org.apache.cassandra.io.util.IIterableColumns;
 import org.apache.cassandra.utils.Allocator;
@@ -46,6 +48,11 @@ public interface ISortedColumns extends 
      */
     public Factory getFactory();
 
+    public DeletionInfo getDeletionInfo();
+    public void delete(DeletionInfo info);
+    public void maybeResetDeletionTimes(int gcBefore);
+    public void retainAll(ISortedColumns columns);
+
     /**
      * Adds a column to this column map.
      * If a column with the same name is already present in the map, it will
@@ -62,7 +69,7 @@ public interface ISortedColumns extends 
      *   </code>
      *  but is potentially faster.
      */
-    public void addAll(ISortedColumns cm, Allocator allocator);
+    public void addAll(ISortedColumns cm, Allocator allocator, Function<IColumn, IColumn> transformation);
 
     /**
      * Replace oldColumn if present by newColumn.
@@ -161,4 +168,22 @@ public interface ISortedColumns extends 
          */
         public ISortedColumns fromSorted(SortedMap<ByteBuffer, IColumn> sm, boolean insertReversed);
     }
+
+    public static class DeletionInfo
+    {
+        public final long markedForDeleteAt;
+        public final int localDeletionTime;
+
+        public DeletionInfo()
+        {
+            this(Long.MIN_VALUE, Integer.MIN_VALUE);
+        }
+
+        public DeletionInfo(long markedForDeleteAt, int localDeletionTime)
+        {
+            this.markedForDeleteAt = markedForDeleteAt;
+            this.localDeletionTime = localDeletionTime;
+        }
+    }
+
 }

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java Tue Dec 27 20:17:17 2011
@@ -25,6 +25,7 @@ import java.util.*;
 import java.util.concurrent.*;
 import java.util.concurrent.atomic.AtomicLong;
 
+import com.google.common.base.Function;
 import com.google.common.collect.Iterators;
 import com.google.common.collect.PeekingIterator;
 import org.slf4j.Logger;
@@ -82,7 +83,15 @@ public class Memtable
     public final ColumnFamilyStore cfs;
     private final long creationTime;
 
-    private SlabAllocator allocator = new SlabAllocator();
+    private final SlabAllocator allocator = new SlabAllocator();
+    // We really only need one column by allocator but one by memtable is not a big waste and avoids needing allocators to know about CFS
+    private final Function<IColumn, IColumn> localCopyFunction = new Function<IColumn, IColumn>()
+    {
+        public IColumn apply(IColumn c)
+        {
+            return c.localCopy(cfs, allocator);
+        };
+    };
 
     public Memtable(ColumnFamilyStore cfs)
     {
@@ -203,25 +212,19 @@ public class Memtable
                                     ? cf.isMarkedForDelete() ? 1 : 0
                                     : cf.getColumnCount());
 
-        ColumnFamily clonedCf = columnFamilies.get(key);
-        // if the row doesn't exist yet in the memtable, clone cf to our allocator.
-        if (clonedCf == null)
-        {
-            clonedCf = cf.cloneMeShallow();
-            for (IColumn column : cf.getSortedColumns())
-                clonedCf.addColumn(column.localCopy(cfs, allocator));
-            clonedCf = columnFamilies.putIfAbsent(new DecoratedKey(key.token, allocator.clone(key.key)), clonedCf);
-            if (clonedCf == null)
-                return;
-            // else there was a race and the other thread won.  fall through to updating his CF object
+
+        ColumnFamily previous = columnFamilies.get(key);
+
+        if (previous == null)
+        {
+            ColumnFamily empty = cf.cloneMeShallow(AtomicSortedColumns.factory(), false);
+            // We'll add the columns later. This avoids wasting works if we get beaten in the putIfAbsent
+            previous = columnFamilies.putIfAbsent(new DecoratedKey(key.token, allocator.clone(key.key)), empty);
+            if (previous == null)
+                previous = empty;
         }
 
-        // we duplicate the funcationality of CF.resolve here to avoid having to either pass the Memtable in for
-        // the cloning operation, or cloning the CF container as well as the Columns.  fortunately, resolve
-        // is really quite simple:
-        clonedCf.delete(cf);
-        for (IColumn column : cf.getSortedColumns())
-            clonedCf.addColumn(column.localCopy(cfs, allocator), allocator);
+        previous.addAll(cf, allocator, localCopyFunction);
     }
 
     // for debugging

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/Row.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/Row.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/Row.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/Row.java Tue Dec 27 20:17:17 2011
@@ -70,7 +70,7 @@ public class Row
 
         public Row deserialize(DataInput dis, int version) throws IOException
         {
-            return deserialize(dis, version, IColumnSerializer.Flag.LOCAL, ThreadSafeSortedColumns.factory());
+            return deserialize(dis, version, IColumnSerializer.Flag.LOCAL, TreeMapBackedSortedColumns.factory());
         }
 
         public long serializedSize(Row row, int version)

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/RowMutation.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/RowMutation.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/RowMutation.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/RowMutation.java Tue Dec 27 20:17:17 2011
@@ -398,7 +398,7 @@ public class RowMutation implements IMut
             for (int i = 0; i < size; ++i)
             {
                 Integer cfid = Integer.valueOf(dis.readInt());
-                ColumnFamily cf = ColumnFamily.serializer().deserialize(dis, flag, ThreadSafeSortedColumns.factory());
+                ColumnFamily cf = ColumnFamily.serializer().deserialize(dis, flag, TreeMapBackedSortedColumns.factory());
                 modifications.put(cfid, cf);
             }
             return new RowMutation(table, key, modifications);

Modified: cassandra/trunk/src/java/org/apache/cassandra/db/SuperColumn.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/SuperColumn.java?rev=1225001&r1=1225000&r2=1225001&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/SuperColumn.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/SuperColumn.java Tue Dec 27 20:17:17 2011
@@ -55,7 +55,7 @@ public class SuperColumn extends Abstrac
 
     public SuperColumn(ByteBuffer name, AbstractType comparator)
     {
-        this(name, ThreadSafeSortedColumns.factory().create(comparator, false));
+        this(name, AtomicSortedColumns.factory().create(comparator, false));
     }
 
     SuperColumn(ByteBuffer name, ISortedColumns columns)
@@ -69,16 +69,14 @@ public class SuperColumn extends Abstrac
     public SuperColumn cloneMeShallow()
     {
         SuperColumn sc = new SuperColumn(name, getComparator());
-        // since deletion info is immutable, aliasing it is fine
-        sc.deletionInfo.set(deletionInfo.get());
+        sc.delete(this);
         return sc;
     }
 
     public IColumn cloneMe()
     {
         SuperColumn sc = new SuperColumn(name, columns.cloneMe());
-        // since deletion info is immutable, aliasing it is fine
-        sc.deletionInfo.set(deletionInfo.get());
+        sc.delete(this);
         return sc;
     }
 
@@ -262,8 +260,7 @@ public class SuperColumn extends Abstrac
         // we don't try to intern supercolumn names, because if we're using Cassandra correctly it's almost
         // certainly just going to pollute our interning map with unique, dynamic values
         SuperColumn sc = new SuperColumn(allocator.clone(name), this.getComparator());
-        // since deletion info is immutable, aliasing it is fine
-        sc.deletionInfo.set(deletionInfo.get());
+        sc.delete(this);
 
         for(IColumn c : columns)
         {
@@ -358,7 +355,7 @@ class SuperColumnSerializer implements I
         int size = dis.readInt();
         ColumnSerializer serializer = Column.serializer();
         ColumnSortedMap preSortedMap = new ColumnSortedMap(comparator, serializer, dis, size, flag, expireBefore);
-        SuperColumn superColumn = new SuperColumn(name, ThreadSafeSortedColumns.factory().fromSorted(preSortedMap, false));
+        SuperColumn superColumn = new SuperColumn(name, AtomicSortedColumns.factory().fromSorted(preSortedMap, false));
         superColumn.delete(localDeleteTime, markedForDeleteAt);
         return superColumn;
     }



Mime
View raw message