1// Copyright 2015 The etcd Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package store
16
17import (
18	"fmt"
19	"path"
20	"strings"
21	"sync"
22
23	etcdErr "github.com/coreos/etcd/error"
24)
25
26type EventHistory struct {
27	Queue      eventQueue
28	StartIndex uint64
29	LastIndex  uint64
30	rwl        sync.RWMutex
31}
32
33func newEventHistory(capacity int) *EventHistory {
34	return &EventHistory{
35		Queue: eventQueue{
36			Capacity: capacity,
37			Events:   make([]*Event, capacity),
38		},
39	}
40}
41
42// addEvent function adds event into the eventHistory
43func (eh *EventHistory) addEvent(e *Event) *Event {
44	eh.rwl.Lock()
45	defer eh.rwl.Unlock()
46
47	eh.Queue.insert(e)
48
49	eh.LastIndex = e.Index()
50
51	eh.StartIndex = eh.Queue.Events[eh.Queue.Front].Index()
52
53	return e
54}
55
56// scan enumerates events from the index history and stops at the first point
57// where the key matches.
58func (eh *EventHistory) scan(key string, recursive bool, index uint64) (*Event, *etcdErr.Error) {
59	eh.rwl.RLock()
60	defer eh.rwl.RUnlock()
61
62	// index should be after the event history's StartIndex
63	if index < eh.StartIndex {
64		return nil,
65			etcdErr.NewError(etcdErr.EcodeEventIndexCleared,
66				fmt.Sprintf("the requested history has been cleared [%v/%v]",
67					eh.StartIndex, index), 0)
68	}
69
70	// the index should come before the size of the queue minus the duplicate count
71	if index > eh.LastIndex { // future index
72		return nil, nil
73	}
74
75	offset := index - eh.StartIndex
76	i := (eh.Queue.Front + int(offset)) % eh.Queue.Capacity
77
78	for {
79		e := eh.Queue.Events[i]
80
81		if !e.Refresh {
82			ok := (e.Node.Key == key)
83
84			if recursive {
85				// add tailing slash
86				nkey := path.Clean(key)
87				if nkey[len(nkey)-1] != '/' {
88					nkey = nkey + "/"
89				}
90
91				ok = ok || strings.HasPrefix(e.Node.Key, nkey)
92			}
93
94			if (e.Action == Delete || e.Action == Expire) && e.PrevNode != nil && e.PrevNode.Dir {
95				ok = ok || strings.HasPrefix(key, e.PrevNode.Key)
96			}
97
98			if ok {
99				return e, nil
100			}
101		}
102
103		i = (i + 1) % eh.Queue.Capacity
104
105		if i == eh.Queue.Back {
106			return nil, nil
107		}
108	}
109}
110
111// clone will be protected by a stop-world lock
112// do not need to obtain internal lock
113func (eh *EventHistory) clone() *EventHistory {
114	clonedQueue := eventQueue{
115		Capacity: eh.Queue.Capacity,
116		Events:   make([]*Event, eh.Queue.Capacity),
117		Size:     eh.Queue.Size,
118		Front:    eh.Queue.Front,
119		Back:     eh.Queue.Back,
120	}
121
122	copy(clonedQueue.Events, eh.Queue.Events)
123	return &EventHistory{
124		StartIndex: eh.StartIndex,
125		Queue:      clonedQueue,
126		LastIndex:  eh.LastIndex,
127	}
128
129}
130