KVS上に実装するStack

CASがあればCAS依存のデータ構造が実装出来る第二弾です。
今度はLockfreeの中でも簡単なデータ構造なスタックです。
前回の疑似コードは微妙だったのでもうちょっとpythonらしい文法に直しました。

import memcache // python-memcached使用
import string
from random import randrange

alphabets = string.digits + string.letters

// ランダム文字列を作る関数
def random_string(n):
    return ''.join(random.choice(alphabets) for i in xrange(n))

// KVS上に実装するスタック
class kvs_stack(object):
	def __init__(self,_server):
		self.client = memcache.Client(_server, debug=0) // memcachedサーバに接続
		head = random_string(8)  // この値をクライアント同士で共有する
		self.client.add(head,'')  // 初めのスタックは空

	def push(self, value_):
		newvalue = value_.join(random_string(8)) // ランダム文字列を末尾に付けて一意性を確保
		self.client.add(newvalue,'')
		while(1):
			old_head = self.client.gets(self.head)  // headが指す先がstackの先頭
			self.client.replace(newvalue,old_head)  // 新規アイテムがそれを指すように書き換え
			
			result = self.client.cas(self.head, newvalue)  // 新規アイテムを指すようにhead差し替え
			if(result == 0): // 失敗したらnewvalueの指す先を書き換える所からやり直し
				continue
			else:  // 成功
				break 

	def pop(self, value_):
		while(1):
			old_head = self.client.gets(self.head) 
			if(old_head == ''):  // スタックが空の場合なら空文字を返す
				return ''
			next_head = self.client.get(old_head)  // headが次に指すべき値を探す
			
			result = self.client.cas(self.head, next_head)  // headを差し替える
			if(result == 0):
				continue  // 失敗したならやり直し
			else:
				value_ = old_head[0:-8]  // 後ろに取り付けた乱数列を削って
				self.client.delete(old_head)  // KVS上から該当項目を消して
				break  // 成功

前回のFIFOでも言えることなんですが
･addは万一ダブって失敗した場合乱数の生成からやり直し
･保存する対象はmemcahedプロトコルに干渉する内容の物は不可
です。恐らくどちらも改善可能な部類ですが今回は説明のため簡単にしました。

次は…双方向dequeでしょうか…？