vendor/github.com/coreos/etcd/store/node.go - cloudstack-kubernetes-provider - Git at Google

 // Copyright 2015 The etcd Authors
 //
 // Licensed 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 store

 import (
 	"path"
 	"sort"
 	"time"

 	etcdErr "github.com/coreos/etcd/error"
 	"github.com/jonboulle/clockwork"
 )

 // explanations of Compare function result
 const (
 	CompareMatch = iota
 	CompareIndexNotMatch
 	CompareValueNotMatch
 	CompareNotMatch
 )

 var Permanent time.Time

 // node is the basic element in the store system.
 // A key-value pair will have a string value
 // A directory will have a children map
 type node struct {
 	Path string

 	CreatedIndex  uint64
 	ModifiedIndex uint64

 	Parent *node `json:"-"` // should not encode this field! avoid circular dependency.

 	ExpireTime time.Time
 	Value      string           // for key-value pair
 	Children   map[string]*node // for directory

 	// A reference to the store this node is attached to.
 	store *store
 }

 // newKV creates a Key-Value pair
 func newKV(store *store, nodePath string, value string, createdIndex uint64, parent *node, expireTime time.Time) *node {
 	return &node{
 		Path:          nodePath,
 		CreatedIndex:  createdIndex,
 		ModifiedIndex: createdIndex,
 		Parent:        parent,
 		store:         store,
 		ExpireTime:    expireTime,
 		Value:         value,
 	}
 }

 // newDir creates a directory
 func newDir(store *store, nodePath string, createdIndex uint64, parent *node, expireTime time.Time) *node {
 	return &node{
 		Path:          nodePath,
 		CreatedIndex:  createdIndex,
 		ModifiedIndex: createdIndex,
 		Parent:        parent,
 		ExpireTime:    expireTime,
 		Children:      make(map[string]*node),
 		store:         store,
 	}
 }

 // IsHidden function checks if the node is a hidden node. A hidden node
 // will begin with '_'
 // A hidden node will not be shown via get command under a directory
 // For example if we have /foo/_hidden and /foo/notHidden, get "/foo"
 // will only return /foo/notHidden
 func (n *node) IsHidden() bool {
 	_, name := path.Split(n.Path)

 	return name[0] == '_'
 }

 // IsPermanent function checks if the node is a permanent one.
 func (n *node) IsPermanent() bool {
 	// we use a uninitialized time.Time to indicate the node is a
 	// permanent one.
 	// the uninitialized time.Time should equal zero.
 	return n.ExpireTime.IsZero()
 }

 // IsDir function checks whether the node is a directory.
 // If the node is a directory, the function will return true.
 // Otherwise the function will return false.
 func (n *node) IsDir() bool {
 	return n.Children != nil
 }

 // Read function gets the value of the node.
 // If the receiver node is not a key-value pair, a "Not A File" error will be returned.
 func (n *node) Read() (string, *etcdErr.Error) {
 	if n.IsDir() {
 		return "", etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.CurrentIndex)
 	}

 	return n.Value, nil
 }

 // Write function set the value of the node to the given value.
 // If the receiver node is a directory, a "Not A File" error will be returned.
 func (n *node) Write(value string, index uint64) *etcdErr.Error {
 	if n.IsDir() {
 		return etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.CurrentIndex)
 	}

 	n.Value = value
 	n.ModifiedIndex = index

 	return nil
 }

 func (n *node) expirationAndTTL(clock clockwork.Clock) (*time.Time, int64) {
 	if !n.IsPermanent() {
 		/* compute ttl as:
 		   ceiling( (expireTime - timeNow) / nanosecondsPerSecond )
 		   which ranges from 1..n
 		   rather than as:
 		   ( (expireTime - timeNow) / nanosecondsPerSecond ) + 1
 		   which ranges 1..n+1
 		*/
 		ttlN := n.ExpireTime.Sub(clock.Now())
 		ttl := ttlN / time.Second
 		if (ttlN % time.Second) > 0 {
 			ttl++
 		}
 		t := n.ExpireTime.UTC()
 		return &t, int64(ttl)
 	}
 	return nil, 0
 }

 // List function return a slice of nodes under the receiver node.
 // If the receiver node is not a directory, a "Not A Directory" error will be returned.
 func (n *node) List() ([]*node, *etcdErr.Error) {
 	if !n.IsDir() {
 		return nil, etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.CurrentIndex)
 	}

 	nodes := make([]*node, len(n.Children))

 	i := 0
 	for _, node := range n.Children {
 		nodes[i] = node
 		i++
 	}

 	return nodes, nil
 }

 // GetChild function returns the child node under the directory node.
 // On success, it returns the file node
 func (n *node) GetChild(name string) (*node, *etcdErr.Error) {
 	if !n.IsDir() {
 		return nil, etcdErr.NewError(etcdErr.EcodeNotDir, n.Path, n.store.CurrentIndex)
 	}

 	child, ok := n.Children[name]

 	if ok {
 		return child, nil
 	}

 	return nil, nil
 }

 // Add function adds a node to the receiver node.
 // If the receiver is not a directory, a "Not A Directory" error will be returned.
 // If there is an existing node with the same name under the directory, a "Already Exist"
 // error will be returned
 func (n *node) Add(child *node) *etcdErr.Error {
 	if !n.IsDir() {
 		return etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.CurrentIndex)
 	}

 	_, name := path.Split(child.Path)

 	if _, ok := n.Children[name]; ok {
 		return etcdErr.NewError(etcdErr.EcodeNodeExist, "", n.store.CurrentIndex)
 	}

 	n.Children[name] = child

 	return nil
 }

 // Remove function remove the node.
 func (n *node) Remove(dir, recursive bool, callback func(path string)) *etcdErr.Error {
 	if !n.IsDir() { // key-value pair
 		_, name := path.Split(n.Path)

 		// find its parent and remove the node from the map
 		if n.Parent != nil && n.Parent.Children[name] == n {
 			delete(n.Parent.Children, name)
 		}

 		if callback != nil {
 			callback(n.Path)
 		}

 		if !n.IsPermanent() {
 			n.store.ttlKeyHeap.remove(n)
 		}

 		return nil
 	}

 	if !dir {
 		// cannot delete a directory without dir set to true
 		return etcdErr.NewError(etcdErr.EcodeNotFile, n.Path, n.store.CurrentIndex)
 	}

 	if len(n.Children) != 0 && !recursive {
 		// cannot delete a directory if it is not empty and the operation
 		// is not recursive
 		return etcdErr.NewError(etcdErr.EcodeDirNotEmpty, n.Path, n.store.CurrentIndex)
 	}

 	for _, child := range n.Children { // delete all children
 		child.Remove(true, true, callback)
 	}

 	// delete self
 	_, name := path.Split(n.Path)
 	if n.Parent != nil && n.Parent.Children[name] == n {
 		delete(n.Parent.Children, name)

 		if callback != nil {
 			callback(n.Path)
 		}

 		if !n.IsPermanent() {
 			n.store.ttlKeyHeap.remove(n)
 		}
 	}

 	return nil
 }

 func (n *node) Repr(recursive, sorted bool, clock clockwork.Clock) *NodeExtern {
 	if n.IsDir() {
 		node := &NodeExtern{
 			Key:           n.Path,
 			Dir:           true,
 			ModifiedIndex: n.ModifiedIndex,
 			CreatedIndex:  n.CreatedIndex,
 		}
 		node.Expiration, node.TTL = n.expirationAndTTL(clock)

 		if !recursive {
 			return node
 		}

 		children, _ := n.List()
 		node.Nodes = make(NodeExterns, len(children))

 		// we do not use the index in the children slice directly
 		// we need to skip the hidden one
 		i := 0

 		for _, child := range children {

 			if child.IsHidden() { // get will not list hidden node
 				continue
 			}

 			node.Nodes[i] = child.Repr(recursive, sorted, clock)

 			i++
 		}

 		// eliminate hidden nodes
 		node.Nodes = node.Nodes[:i]
 		if sorted {
 			sort.Sort(node.Nodes)
 		}

 		return node
 	}

 	// since n.Value could be changed later, so we need to copy the value out
 	value := n.Value
 	node := &NodeExtern{
 		Key:           n.Path,
 		Value:         &value,
 		ModifiedIndex: n.ModifiedIndex,
 		CreatedIndex:  n.CreatedIndex,
 	}
 	node.Expiration, node.TTL = n.expirationAndTTL(clock)
 	return node
 }

 func (n *node) UpdateTTL(expireTime time.Time) {
 	if !n.IsPermanent() {
 		if expireTime.IsZero() {
 			// from ttl to permanent
 			n.ExpireTime = expireTime
 			// remove from ttl heap
 			n.store.ttlKeyHeap.remove(n)
 			return
 		}

 		// update ttl
 		n.ExpireTime = expireTime
 		// update ttl heap
 		n.store.ttlKeyHeap.update(n)
 		return
 	}

 	if expireTime.IsZero() {
 		return
 	}

 	// from permanent to ttl
 	n.ExpireTime = expireTime
 	// push into ttl heap
 	n.store.ttlKeyHeap.push(n)
 }

 // Compare function compares node index and value with provided ones.
 // second result value explains result and equals to one of Compare.. constants
 func (n *node) Compare(prevValue string, prevIndex uint64) (ok bool, which int) {
 	indexMatch := (prevIndex == 0 || n.ModifiedIndex == prevIndex)
 	valueMatch := (prevValue == "" || n.Value == prevValue)
 	ok = valueMatch && indexMatch
 	switch {
 	case valueMatch && indexMatch:
 		which = CompareMatch
 	case indexMatch && !valueMatch:
 		which = CompareValueNotMatch
 	case valueMatch && !indexMatch:
 		which = CompareIndexNotMatch
 	default:
 		which = CompareNotMatch
 	}
 	return ok, which
 }

 // Clone function clone the node recursively and return the new node.
 // If the node is a directory, it will clone all the content under this directory.
 // If the node is a key-value pair, it will clone the pair.
 func (n *node) Clone() *node {
 	if !n.IsDir() {
 		newkv := newKV(n.store, n.Path, n.Value, n.CreatedIndex, n.Parent, n.ExpireTime)
 		newkv.ModifiedIndex = n.ModifiedIndex
 		return newkv
 	}

 	clone := newDir(n.store, n.Path, n.CreatedIndex, n.Parent, n.ExpireTime)
 	clone.ModifiedIndex = n.ModifiedIndex

 	for key, child := range n.Children {
 		clone.Children[key] = child.Clone()
 	}

 	return clone
 }

 // recoverAndclean function help to do recovery.
 // Two things need to be done: 1. recovery structure; 2. delete expired nodes
 //
 // If the node is a directory, it will help recover children's parent pointer and recursively
 // call this function on its children.
 // We check the expire last since we need to recover the whole structure first and add all the
 // notifications into the event history.
 func (n *node) recoverAndclean() {
 	if n.IsDir() {
 		for _, child := range n.Children {
 			child.Parent = n
 			child.store = n.store
 			child.recoverAndclean()
 		}
 	}

 	if !n.ExpireTime.IsZero() {
 		n.store.ttlKeyHeap.push(n)
 	}
 }
	// Copyright 2015 The etcd Authors
	//
	// Licensed 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 store

	import (
	"path"
	"sort"
	"time"

	etcdErr "github.com/coreos/etcd/error"
	"github.com/jonboulle/clockwork"
	)

	// explanations of Compare function result
	const (
	CompareMatch = iota
	CompareIndexNotMatch
	CompareValueNotMatch
	CompareNotMatch
	)

	var Permanent time.Time

	// node is the basic element in the store system.
	// A key-value pair will have a string value
	// A directory will have a children map
	type node struct {
	Path string

	CreatedIndex uint64
	ModifiedIndex uint64

	Parent *node `json:"-"` // should not encode this field! avoid circular dependency.

	ExpireTime time.Time
	Value string // for key-value pair
	Children map[string]*node // for directory

	// A reference to the store this node is attached to.
	store *store
	}

	// newKV creates a Key-Value pair
	func newKV(store store, nodePath string, value string, createdIndex uint64, parent node, expireTime time.Time) *node {
	return &node{
	Path: nodePath,
	CreatedIndex: createdIndex,
	ModifiedIndex: createdIndex,
	Parent: parent,
	store: store,
	ExpireTime: expireTime,
	Value: value,
	}
	}

	// newDir creates a directory
	func newDir(store store, nodePath string, createdIndex uint64, parent node, expireTime time.Time) *node {
	return &node{
	Path: nodePath,
	CreatedIndex: createdIndex,
	ModifiedIndex: createdIndex,
	Parent: parent,
	ExpireTime: expireTime,
	Children: make(map[string]*node),
	store: store,
	}
	}

	// IsHidden function checks if the node is a hidden node. A hidden node
	// will begin with '_'
	// A hidden node will not be shown via get command under a directory
	// For example if we have /foo/_hidden and /foo/notHidden, get "/foo"
	// will only return /foo/notHidden
	func (n *node) IsHidden() bool {
	_, name := path.Split(n.Path)

	return name[0] == '_'
	}

	// IsPermanent function checks if the node is a permanent one.
	func (n *node) IsPermanent() bool {
	// we use a uninitialized time.Time to indicate the node is a
	// permanent one.
	// the uninitialized time.Time should equal zero.
	return n.ExpireTime.IsZero()
	}

	// IsDir function checks whether the node is a directory.
	// If the node is a directory, the function will return true.
	// Otherwise the function will return false.
	func (n *node) IsDir() bool {
	return n.Children != nil
	}

	// Read function gets the value of the node.
	// If the receiver node is not a key-value pair, a "Not A File" error will be returned.
	func (n node) Read() (string, etcdErr.Error) {
	if n.IsDir() {
	return "", etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.CurrentIndex)
	}

	return n.Value, nil
	}

	// Write function set the value of the node to the given value.
	// If the receiver node is a directory, a "Not A File" error will be returned.
	func (n node) Write(value string, index uint64) etcdErr.Error {
	if n.IsDir() {
	return etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.CurrentIndex)
	}

	n.Value = value
	n.ModifiedIndex = index

	return nil
	}

	func (n node) expirationAndTTL(clock clockwork.Clock) (time.Time, int64) {
	if !n.IsPermanent() {
	/* compute ttl as:
	ceiling( (expireTime - timeNow) / nanosecondsPerSecond )
	which ranges from 1..n
	rather than as:
	( (expireTime - timeNow) / nanosecondsPerSecond ) + 1
	which ranges 1..n+1
	*/
	ttlN := n.ExpireTime.Sub(clock.Now())
	ttl := ttlN / time.Second
	if (ttlN % time.Second) > 0 {
	ttl++
	}
	t := n.ExpireTime.UTC()
	return &t, int64(ttl)
	}
	return nil, 0
	}

	// List function return a slice of nodes under the receiver node.
	// If the receiver node is not a directory, a "Not A Directory" error will be returned.
	func (n node) List() ([]node, *etcdErr.Error) {
	if !n.IsDir() {
	return nil, etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.CurrentIndex)
	}

	nodes := make([]*node, len(n.Children))

	i := 0
	for _, node := range n.Children {
	nodes[i] = node
	i++
	}

	return nodes, nil
	}

	// GetChild function returns the child node under the directory node.
	// On success, it returns the file node
	func (n node) GetChild(name string) (node, *etcdErr.Error) {
	if !n.IsDir() {
	return nil, etcdErr.NewError(etcdErr.EcodeNotDir, n.Path, n.store.CurrentIndex)
	}

	child, ok := n.Children[name]

	if ok {
	return child, nil
	}

	return nil, nil
	}

	// Add function adds a node to the receiver node.
	// If the receiver is not a directory, a "Not A Directory" error will be returned.
	// If there is an existing node with the same name under the directory, a "Already Exist"
	// error will be returned
	func (n node) Add(child node) *etcdErr.Error {
	if !n.IsDir() {
	return etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.CurrentIndex)
	}

	_, name := path.Split(child.Path)

	if _, ok := n.Children[name]; ok {
	return etcdErr.NewError(etcdErr.EcodeNodeExist, "", n.store.CurrentIndex)
	}

	n.Children[name] = child

	return nil
	}

	// Remove function remove the node.
	func (n node) Remove(dir, recursive bool, callback func(path string)) etcdErr.Error {
	if !n.IsDir() { // key-value pair
	_, name := path.Split(n.Path)

	// find its parent and remove the node from the map
	if n.Parent != nil && n.Parent.Children[name] == n {
	delete(n.Parent.Children, name)
	}

	if callback != nil {
	callback(n.Path)
	}

	if !n.IsPermanent() {
	n.store.ttlKeyHeap.remove(n)
	}

	return nil
	}

	if !dir {
	// cannot delete a directory without dir set to true
	return etcdErr.NewError(etcdErr.EcodeNotFile, n.Path, n.store.CurrentIndex)
	}

	if len(n.Children) != 0 && !recursive {
	// cannot delete a directory if it is not empty and the operation
	// is not recursive
	return etcdErr.NewError(etcdErr.EcodeDirNotEmpty, n.Path, n.store.CurrentIndex)
	}

	for _, child := range n.Children { // delete all children
	child.Remove(true, true, callback)
	}

	// delete self
	_, name := path.Split(n.Path)
	if n.Parent != nil && n.Parent.Children[name] == n {
	delete(n.Parent.Children, name)

	if callback != nil {
	callback(n.Path)
	}

	if !n.IsPermanent() {
	n.store.ttlKeyHeap.remove(n)
	}
	}

	return nil
	}

	func (n node) Repr(recursive, sorted bool, clock clockwork.Clock) NodeExtern {
	if n.IsDir() {
	node := &NodeExtern{
	Key: n.Path,
	Dir: true,
	ModifiedIndex: n.ModifiedIndex,
	CreatedIndex: n.CreatedIndex,
	}
	node.Expiration, node.TTL = n.expirationAndTTL(clock)

	if !recursive {
	return node
	}

	children, _ := n.List()
	node.Nodes = make(NodeExterns, len(children))

	// we do not use the index in the children slice directly
	// we need to skip the hidden one
	i := 0

	for _, child := range children {

	if child.IsHidden() { // get will not list hidden node
	continue
	}

	node.Nodes[i] = child.Repr(recursive, sorted, clock)

	i++
	}

	// eliminate hidden nodes
	node.Nodes = node.Nodes[:i]
	if sorted {
	sort.Sort(node.Nodes)
	}

	return node
	}

	// since n.Value could be changed later, so we need to copy the value out
	value := n.Value
	node := &NodeExtern{
	Key: n.Path,
	Value: &value,
	ModifiedIndex: n.ModifiedIndex,
	CreatedIndex: n.CreatedIndex,
	}
	node.Expiration, node.TTL = n.expirationAndTTL(clock)
	return node
	}

	func (n *node) UpdateTTL(expireTime time.Time) {
	if !n.IsPermanent() {
	if expireTime.IsZero() {
	// from ttl to permanent
	n.ExpireTime = expireTime
	// remove from ttl heap
	n.store.ttlKeyHeap.remove(n)
	return
	}

	// update ttl
	n.ExpireTime = expireTime
	// update ttl heap
	n.store.ttlKeyHeap.update(n)
	return
	}

	if expireTime.IsZero() {
	return
	}

	// from permanent to ttl
	n.ExpireTime = expireTime
	// push into ttl heap
	n.store.ttlKeyHeap.push(n)
	}

	// Compare function compares node index and value with provided ones.
	// second result value explains result and equals to one of Compare.. constants
	func (n *node) Compare(prevValue string, prevIndex uint64) (ok bool, which int) {
	indexMatch := (prevIndex == 0 \|\| n.ModifiedIndex == prevIndex)
	valueMatch := (prevValue == "" \|\| n.Value == prevValue)
	ok = valueMatch && indexMatch
	switch {
	case valueMatch && indexMatch:
	which = CompareMatch
	case indexMatch && !valueMatch:
	which = CompareValueNotMatch
	case valueMatch && !indexMatch:
	which = CompareIndexNotMatch
	default:
	which = CompareNotMatch
	}
	return ok, which
	}

	// Clone function clone the node recursively and return the new node.
	// If the node is a directory, it will clone all the content under this directory.
	// If the node is a key-value pair, it will clone the pair.
	func (n node) Clone() node {
	if !n.IsDir() {
	newkv := newKV(n.store, n.Path, n.Value, n.CreatedIndex, n.Parent, n.ExpireTime)
	newkv.ModifiedIndex = n.ModifiedIndex
	return newkv
	}

	clone := newDir(n.store, n.Path, n.CreatedIndex, n.Parent, n.ExpireTime)
	clone.ModifiedIndex = n.ModifiedIndex

	for key, child := range n.Children {
	clone.Children[key] = child.Clone()
	}

	return clone
	}

	// recoverAndclean function help to do recovery.
	// Two things need to be done: 1. recovery structure; 2. delete expired nodes
	//
	// If the node is a directory, it will help recover children's parent pointer and recursively
	// call this function on its children.
	// We check the expire last since we need to recover the whole structure first and add all the
	// notifications into the event history.
	func (n *node) recoverAndclean() {
	if n.IsDir() {
	for _, child := range n.Children {
	child.Parent = n
	child.store = n.store
	child.recoverAndclean()
	}
	}

	if !n.ExpireTime.IsZero() {
	n.store.ttlKeyHeap.push(n)
	}
	}