// findStores is the Store's implementation of a StoreFinder. It returns a list
// of stores with attributes that are a superset of the required attributes. It
// never returns an error.
//
// If it cannot retrieve a StoreDescriptor from the Store's gossip, it garbage
// collects the failed key.
//
// TODO(embark, spencer): consider using a reverse index map from Attr->stores,
// for efficiency.  Ensure that entries in this map still have an opportunity
// to be garbage collected.
func (sf *StoreFinder) findStores(required proto.Attributes) ([]*StoreDescriptor, error) {
	sf.finderMu.Lock()
	defer sf.finderMu.Unlock()
	var stores []*StoreDescriptor
	for key := range sf.capacityKeys {
		storeDesc, err := storeDescFromGossip(key, sf.gossip)
		if err != nil {
			// We can no longer retrieve this key from the gossip store,
			// perhaps it expired.
			delete(sf.capacityKeys, key)
		} else if required.IsSubset(storeDesc.Attrs) {
			stores = append(stores, storeDesc)
		}
	}
	return stores, nil
}

// getStoreList returns a store list matching the required attributes.
// Results are cached for performance.
//
// If it cannot retrieve a StoreDescriptor from the Store's gossip, it
// garbage collects the failed key.
//
// TODO(embark, spencer): consider using a reverse index map from
// Attr->stores, for efficiency. Ensure that entries in this map still
// have an opportunity to be garbage collected.
func (a *allocator) getStoreList(required proto.Attributes) *storeList {
	if a.storeLists == nil {
		a.storeLists = map[string]*storeList{}
	}
	key := required.SortedString()
	if sl, ok := a.storeLists[key]; ok {
		return sl
	}
	sl := &storeList{}
	a.storeLists[key] = sl

	updateStoreList := func(key string) {
		storeDesc, err := storeDescFromGossip(key, a.gossip)
		if err != nil {
			// We can no longer retrieve this key from the gossip store,
			// perhaps it expired.
			delete(a.capacityKeys, key)
		} else if required.IsSubset(*storeDesc.CombinedAttrs()) {
			sl.Add(storeDesc)
		}
	}

	if a.deterministic {
		var keys []string
		for key := range a.capacityKeys {
			keys = append(keys, key)
		}
		sort.Strings(keys)
		for _, key := range keys {
			updateStoreList(key)
		}
		return sl
	}

	for key := range a.capacityKeys {
		updateStoreList(key)
	}
	return sl
}

// GetStoreList returns a storeList that contains all active stores that
// contain the required attributes and their associated stats.
// TODO(embark, spencer): consider using a reverse index map from
// Attr->stores, for efficiency. Ensure that entries in this map still
// have an opportunity to be garbage collected.
func (sp *StorePool) getStoreList(required proto.Attributes, deterministic bool) *StoreList {
	sp.mu.RLock()
	defer sp.mu.RUnlock()

	var storeIDs proto.StoreIDSlice
	for storeID := range sp.stores {
		storeIDs = append(storeIDs, storeID)
	}
	// Sort the stores by key if deterministic is requested. This is only for
	// unit testing.
	if deterministic {
		sort.Sort(storeIDs)
	}
	sl := new(StoreList)
	for _, storeID := range storeIDs {
		detail := sp.stores[proto.StoreID(storeID)]
		if !detail.dead && required.IsSubset(*detail.desc.CombinedAttrs()) {
			desc := detail.desc
			sl.add(&desc)
		}
	}
	return sl
}

// GetStoreList returns a storeList that contains all active stores that
// contain the required attributes and their associated stats.
// TODO(embark, spencer): consider using a reverse index map from
// Attr->stores, for efficiency. Ensure that entries in this map still
// have an opportunity to be garbage collected.
func (sp *StorePool) getStoreList(required proto.Attributes, deterministic bool) *StoreList {
	sp.mu.RLock()
	defer sp.mu.RUnlock()

	// TODO(bram): Consider adding the sort interface to proto.StoreID.
	var storeIDs []int
	for storeID := range sp.stores {
		storeIDs = append(storeIDs, int(storeID))
	}
	// Sort the stores by key if deterministic is requested. This is only for
	// unit testing.
	if deterministic {
		sort.Ints(storeIDs)
	}
	sl := new(StoreList)
	for _, storeID := range storeIDs {
		detail := sp.stores[proto.StoreID(storeID)]
		if !detail.dead && required.IsSubset(*detail.desc.CombinedAttrs()) {
			desc := detail.desc
			sl.add(&desc)
		}
	}
	return sl
}