func (d *dataStoreData) allocateIDs(incomplete *ds.Key, n int) (int64, error) {
	d.Lock()
	defer d.Unlock()

	ents := d.mutableEntsLocked(incomplete.Namespace())
	return d.allocateIDsLocked(ents, incomplete, n)
}

// writeMutation ensures that this transaction can support the given key/value
// mutation.
//
//   if getOnly is true, don't record the actual mutation data, just ensure that
//	   the key is in an included entity group (or add an empty entry for that
//	   group).
//
//   if !getOnly && data == nil, this counts as a deletion instead of a Put.
//
// Returns an error if this key causes the transaction to cross too many entity
// groups.
func (td *txnDataStoreData) writeMutation(getOnly bool, key *ds.Key, data ds.PropertyMap) error {
	rk := string(keyBytes(key.Root()))

	td.Lock()
	defer td.Unlock()

	if _, ok := td.muts[rk]; !ok {
		limit := 1
		if td.isXG {
			limit = xgEGLimit
		}
		if len(td.muts)+1 > limit {
			msg := "cross-group transaction need to be explicitly specified (xg=True)"
			if td.isXG {
				msg = "operating on too many entity groups in a single transaction"
			}
			return errors.New(msg)
		}
		td.muts[rk] = []txnMutation{}
	}
	if !getOnly {
		td.muts[rk] = append(td.muts[rk], txnMutation{key, data})
	}

	return nil
}

func testGetMeta(c context.Context, k *dsS.Key) int64 {
	ds := dsS.Get(c)
	mg := &MetaGroup{Parent: k.Root()}
	if err := ds.Get(mg); err != nil {
		panic(err)
	}
	return mg.Version
}

func (d rdsImpl) AllocateIDs(incomplete *ds.Key, n int) (start int64, err error) {
	par, err := dsF2R(d.aeCtx, incomplete.Parent())
	if err != nil {
		return
	}

	start, _, err = datastore.AllocateIDs(d.aeCtx, incomplete.Kind(), par, n)
	return
}

func (d *dataStoreData) fixKeyLocked(ents *memCollection, key *ds.Key) (*ds.Key, error) {
	if key.Incomplete() {
		id, err := d.allocateIDsLocked(ents, key, 1)
		if err != nil {
			return key, err
		}
		key = ds.NewKey(key.AppID(), key.Namespace(), key.Kind(), "", id, key.Parent())
	}
	return key, nil
}

func updateIndexes(store *memStore, key *ds.Key, oldEnt, newEnt ds.PropertyMap) {
	// load all current complex query index definitions.
	compIdx := []*ds.IndexDefinition{}
	walkCompIdxs(store, nil, func(i *ds.IndexDefinition) bool {
		compIdx = append(compIdx, i)
		return true
	})

	mergeIndexes(key.Namespace(), store,
		indexEntriesWithBuiltins(key, oldEnt, compIdx),
		indexEntriesWithBuiltins(key, newEnt, compIdx))
}

func (d *dataStoreData) allocateIDsLocked(ents *memCollection, incomplete *ds.Key, n int) (int64, error) {
	if d.disableSpecialEntities {
		return 0, errors.New("disableSpecialEntities is true so allocateIDs is disabled")
	}

	idKey := []byte(nil)
	if incomplete.Parent() == nil {
		idKey = rootIDsKey(incomplete.Kind())
	} else {
		idKey = groupIDsKey(incomplete)
	}
	return incrementLocked(ents, idKey, n), nil
}

// PropertyMapPartially turns a regular PropertyMap into a SerializedPmap.
// Essentially all the []Property's become SerializedPslice, using cmpbin and
// datastore/serialize's encodings.
func PropertyMapPartially(k *ds.Key, pm ds.PropertyMap) (ret SerializedPmap) {
	ret = make(SerializedPmap, len(pm)+2)
	if k != nil {
		ret["__key__"] = [][]byte{ToBytes(ds.MkProperty(k))}
		for k != nil {
			ret["__ancestor__"] = append(ret["__ancestor__"], ToBytes(ds.MkProperty(k)))
			k = k.Parent()
		}
	}
	for k, vals := range pm {
		newVals := PropertySlice(vals)
		if len(newVals) > 0 {
			ret[k] = newVals
		}
	}
	return
}

// WriteKey encodes a key to the buffer. If context is WithContext, then this
// encoded value will include the appid and namespace of the key.
func WriteKey(buf Buffer, context KeyContext, k *ds.Key) (err error) {
	// [appid ++ namespace]? ++ [1 ++ token]* ++ NULL
	defer recoverTo(&err)
	appid, namespace, toks := k.Split()
	if context == WithContext {
		panicIf(buf.WriteByte(1))
		_, e := cmpbin.WriteString(buf, appid)
		panicIf(e)
		_, e = cmpbin.WriteString(buf, namespace)
		panicIf(e)
	} else {
		panicIf(buf.WriteByte(0))
	}
	for _, tok := range toks {
		panicIf(buf.WriteByte(1))
		panicIf(WriteKeyTok(buf, tok))
	}
	return buf.WriteByte(0)
}

// dsF2R (DS fake-to-real) converts a DSKey back to an SDK *Key.
func dsF2R(aeCtx context.Context, k *ds.Key) (*datastore.Key, error) {
	if k == nil {
		return nil, nil
	}

	// drop aid.
	_, ns, toks := k.Split()
	err := error(nil)
	aeCtx, err = appengine.Namespace(aeCtx, ns)
	if err != nil {
		return nil, err
	}

	ret := datastore.NewKey(aeCtx, toks[0].Kind, toks[0].StringID, toks[0].IntID, nil)
	for _, t := range toks[1:] {
		ret = datastore.NewKey(aeCtx, t.Kind, t.StringID, t.IntID, ret)
	}

	return ret, nil
}

func groupIDsKey(key *ds.Key) []byte {
	return keyBytes(ds.NewKey("", "", "__entity_group_ids__", "", 1, key.Root()))
}

func indexEntriesWithBuiltins(k *ds.Key, pm ds.PropertyMap, complexIdxs []*ds.IndexDefinition) *memStore {
	sip := serialize.PropertyMapPartially(k, pm)
	return indexEntries(sip, k.Namespace(), append(defaultIndexes(k.Kind(), pm), complexIdxs...))
}