Use hashicorp/go-memdb instead of truncindex
**- What I did**

Removed `truncindex` since we can get the same feature using memdb. This removes one of the 3 places we keep containers in memory.

**- How I did it**

I changed the ID index in memdb so that it can be searched by a prefix. I also converted the `truncindex` tests to make sure everything is still working as intended. I only converted some of the benchmarks from `truncindex,` I'm not sure we need the benchmarks for insertion/deletion since those aren't used any more, we are using the same list of containers that are already present in the memdb.

We no longer need `patricia` so I removed it from the vendors

**- How to verify it**

The CI should be enough.

Benchmarks:

```console
$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkDBGetByPrefix100$ github.com/docker/docker/container
goos: linux
goarch: amd64
pkg: github.com/docker/docker/container
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkDBGetByPrefix100-6        16018             73935 ns/op           33888 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        16502             73150 ns/op           33888 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        16218             74014 ns/op           33856 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        15733             73370 ns/op           33792 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        16432             72546 ns/op           33744 B/op       1100 allocs/op
PASS
ok      github.com/docker/docker/container      9.752s

$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkTruncIndexGet100$ github.com/docker/docker/pkg/truncindex
goos: linux
goarch: amd64
pkg: github.com/docker/docker/pkg/truncindex
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkTruncIndexGet100-6        16862             73732 ns/op           44776 B/op       1173 allocs/op
BenchmarkTruncIndexGet100-6        16832             73629 ns/op           45184 B/op       1179 allocs/op
BenchmarkTruncIndexGet100-6        17214             73571 ns/op           45160 B/op       1178 allocs/op
BenchmarkTruncIndexGet100-6        16113             71680 ns/op           45360 B/op       1182 allocs/op
BenchmarkTruncIndexGet100-6        16676             71246 ns/op           45056 B/op       1184 allocs/op
PASS
ok      github.com/docker/docker/pkg/truncindex 9.759s

$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkDBGetByPrefix500$ github.com/docker/docker/container
goos: linux
goarch: amd64
pkg: github.com/docker/docker/container
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkDBGetByPrefix500-6         1539            753541 ns/op          169381 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1624            749975 ns/op          169458 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1635            761222 ns/op          169298 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1693            727856 ns/op          169297 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1874            710813 ns/op          169570 B/op       5500 allocs/op
PASS
ok      github.com/docker/docker/container      6.711s

$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkTruncIndexGet500$ github.com/docker/docker/pkg/truncindex
goos: linux
goarch: amd64
pkg: github.com/docker/docker/pkg/truncindex
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkTruncIndexGet500-6         1934            780328 ns/op          224073 B/op       5929 allocs/op
BenchmarkTruncIndexGet500-6         1713            713935 ns/op          225011 B/op       5937 allocs/op
BenchmarkTruncIndexGet500-6         1780            702847 ns/op          224090 B/op       5943 allocs/op
BenchmarkTruncIndexGet500-6         1736            711086 ns/op          224027 B/op       5929 allocs/op
BenchmarkTruncIndexGet500-6         2448            508694 ns/op          222322 B/op       5914 allocs/op
PASS
ok      github.com/docker/docker/pkg/truncindex 6.877s
```


**- A picture of a cute animal (not mandatory but encouraged)**


container/view.go
package container // import "github.com/docker/docker/container"

import (
	"errors"
	"fmt"
	"strings"
	"time"

	"github.com/docker/docker/api/types"
	"github.com/docker/docker/api/types/network"
	"github.com/docker/go-connections/nat"
	memdb "github.com/hashicorp/go-memdb"
	"github.com/sirupsen/logrus"
)

const (
	memdbContainersTable  = "containers"
	memdbNamesTable       = "names"
	memdbIDIndex          = "id"
	memdbContainerIDIndex = "containerid"
)

var (
	// ErrNameReserved is an error which is returned when a name is requested to be reserved that already is reserved
	ErrNameReserved = errors.New("name is reserved")
	// ErrNameNotReserved is an error which is returned when trying to find a name that is not reserved
	ErrNameNotReserved = errors.New("name is not reserved")
)

// Snapshot is a read only view for Containers. It holds all information necessary to serve container queries in a
// versioned ACID in-memory store.
type Snapshot struct {
	types.Container

	// additional info queries need to filter on
	// preserve nanosec resolution for queries
	CreatedAt    time.Time
	StartedAt    time.Time
	Name         string
	Pid          int
	ExitCode     int
	Running      bool
	Paused       bool
	Managed      bool
	ExposedPorts nat.PortSet
	PortBindings nat.PortSet
	Health       string
	HostConfig   struct {
		Isolation string
	}
}

// nameAssociation associates a container id with a name.
type nameAssociation struct {
	// name is the name to associate. Note that name is the primary key
	// ("id" in memdb).
	name        string
	containerID string
}

// ViewDB provides an in-memory transactional (ACID) container Store
type ViewDB interface {
	Snapshot() View
	Save(*Container) error
	Delete(*Container) error

	ReserveName(name, containerID string) error
	ReleaseName(name string) error
}

// View can be used by readers to avoid locking
type View interface {
	All() ([]Snapshot, error)
	Get(id string) (*Snapshot, error)

	GetID(name string) (string, error)
	GetAllNames() map[string][]string
}

var schema = &memdb.DBSchema{
	Tables: map[string]*memdb.TableSchema{
		memdbContainersTable: {
			Name: memdbContainersTable,
			Indexes: map[string]*memdb.IndexSchema{
				memdbIDIndex: {
					Name:    memdbIDIndex,
					Unique:  true,
					Indexer: &containerByIDIndexer{},
				},
			},
		},
		memdbNamesTable: {
			Name: memdbNamesTable,
			Indexes: map[string]*memdb.IndexSchema{
				// Used for names, because "id" is the primary key in memdb.
				memdbIDIndex: {
					Name:    memdbIDIndex,
					Unique:  true,
					Indexer: &namesByNameIndexer{},
				},
				memdbContainerIDIndex: {
					Name:    memdbContainerIDIndex,
					Indexer: &namesByContainerIDIndexer{},
				},
			},
		},
	},
}

type memDB struct {
	store *memdb.MemDB
}

// NoSuchContainerError indicates that the container wasn't found in the
// database.
type NoSuchContainerError struct {
	id string
}

// Error satisfies the error interface.
func (e NoSuchContainerError) Error() string {
	return "no such container " + e.id
}

// NewViewDB provides the default implementation, with the default schema
func NewViewDB() (ViewDB, error) {
	store, err := memdb.NewMemDB(schema)
	if err != nil {
		return nil, err
	}
	return &memDB{store: store}, nil
}

// Snapshot provides a consistent read-only View of the database
func (db *memDB) Snapshot() View {
	return &memdbView{
		txn: db.store.Txn(false),
	}
}

func (db *memDB) withTxn(cb func(*memdb.Txn) error) error {
	txn := db.store.Txn(true)
	err := cb(txn)
	if err != nil {
		txn.Abort()
		return err
	}
	txn.Commit()
	return nil
}

// Save atomically updates the in-memory store state for a Container.
// Only read only (deep) copies of containers may be passed in.
func (db *memDB) Save(c *Container) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		return txn.Insert(memdbContainersTable, c)
	})
}

// Delete removes an item by ID
func (db *memDB) Delete(c *Container) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		view := &memdbView{txn: txn}
		names := view.getNames(c.ID)

		for _, name := range names {
			txn.Delete(memdbNamesTable, nameAssociation{name: name})
		}

		// Ignore error - the container may not actually exist in the
		// db, but we still need to clean up associated names.
		txn.Delete(memdbContainersTable, NewBaseContainer(c.ID, c.Root))
		return nil
	})
}

// ReserveName registers a container ID to a name
// ReserveName is idempotent
// Attempting to reserve a container ID to a name that already exists results in an `ErrNameReserved`
// A name reservation is globally unique
func (db *memDB) ReserveName(name, containerID string) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		s, err := txn.First(memdbNamesTable, memdbIDIndex, name)
		if err != nil {
			return err
		}
		if s != nil {
			if s.(nameAssociation).containerID != containerID {
				return ErrNameReserved
			}
			return nil
		}
		return txn.Insert(memdbNamesTable, nameAssociation{name: name, containerID: containerID})
	})
}

// ReleaseName releases the reserved name
// Once released, a name can be reserved again
func (db *memDB) ReleaseName(name string) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		return txn.Delete(memdbNamesTable, nameAssociation{name: name})
	})
}

type memdbView struct {
	txn *memdb.Txn
}

// All returns a all items in this snapshot. Returned objects must never be modified.
func (v *memdbView) All() ([]Snapshot, error) {
	var all []Snapshot
	iter, err := v.txn.Get(memdbContainersTable, memdbIDIndex)
	if err != nil {
		return nil, err
	}
	for {
		item := iter.Next()
		if item == nil {
			break
		}
		snapshot := v.transform(item.(*Container))
		all = append(all, *snapshot)
	}
	return all, nil
}

// Get returns an item by id. Returned objects must never be modified.
func (v *memdbView) Get(id string) (*Snapshot, error) {
	s, err := v.txn.First(memdbContainersTable, memdbIDIndex, id)
	if err != nil {
		return nil, err
	}
	if s == nil {
		return nil, NoSuchContainerError{id: id}
	}
	return v.transform(s.(*Container)), nil
}

// getNames lists all the reserved names for the given container ID.
func (v *memdbView) getNames(containerID string) []string {
	iter, err := v.txn.Get(memdbNamesTable, memdbContainerIDIndex, containerID)
	if err != nil {
		return nil
	}

	var names []string
	for {
		item := iter.Next()
		if item == nil {
			break
		}
		names = append(names, item.(nameAssociation).name)
	}

	return names
}

// GetID returns the container ID that the passed in name is reserved to.
func (v *memdbView) GetID(name string) (string, error) {
	s, err := v.txn.First(memdbNamesTable, memdbIDIndex, name)
	if err != nil {
		return "", err
	}
	if s == nil {
		return "", ErrNameNotReserved
	}
	return s.(nameAssociation).containerID, nil
}

// GetAllNames returns all registered names.
func (v *memdbView) GetAllNames() map[string][]string {
	iter, err := v.txn.Get(memdbNamesTable, memdbContainerIDIndex)
	if err != nil {
		return nil
	}

	out := make(map[string][]string)
	for {
		item := iter.Next()
		if item == nil {
			break
		}
		assoc := item.(nameAssociation)
		out[assoc.containerID] = append(out[assoc.containerID], assoc.name)
	}

	return out
}

// transform maps a (deep) copied Container object to what queries need.
// A lock on the Container is not held because these are immutable deep copies.
func (v *memdbView) transform(container *Container) *Snapshot {
	health := types.NoHealthcheck
	if container.Health != nil {
		health = container.Health.Status()
	}
	snapshot := &Snapshot{
		Container: types.Container{
			ID:      container.ID,
			Names:   v.getNames(container.ID),
			ImageID: container.ImageID.String(),
			Ports:   []types.Port{},
			Mounts:  container.GetMountPoints(),
			State:   container.State.StateString(),
			Status:  container.State.String(),
			Created: container.Created.Unix(),
		},
		CreatedAt:    container.Created,
		StartedAt:    container.StartedAt,
		Name:         container.Name,
		Pid:          container.Pid,
		Managed:      container.Managed,
		ExposedPorts: make(nat.PortSet),
		PortBindings: make(nat.PortSet),
		Health:       health,
		Running:      container.Running,
		Paused:       container.Paused,
		ExitCode:     container.ExitCode(),
	}

	if snapshot.Names == nil {
		// Dead containers will often have no name, so make sure the response isn't null
		snapshot.Names = []string{}
	}

	if container.HostConfig != nil {
		snapshot.Container.HostConfig.NetworkMode = string(container.HostConfig.NetworkMode)
		snapshot.HostConfig.Isolation = string(container.HostConfig.Isolation)
		for binding := range container.HostConfig.PortBindings {
			snapshot.PortBindings[binding] = struct{}{}
		}
	}

	if container.Config != nil {
		snapshot.Image = container.Config.Image
		snapshot.Labels = container.Config.Labels
		for exposed := range container.Config.ExposedPorts {
			snapshot.ExposedPorts[exposed] = struct{}{}
		}
	}

	if len(container.Args) > 0 {
		var args []string
		for _, arg := range container.Args {
			if strings.Contains(arg, " ") {
				args = append(args, fmt.Sprintf("'%s'", arg))
			} else {
				args = append(args, arg)
			}
		}
		argsAsString := strings.Join(args, " ")
		snapshot.Command = fmt.Sprintf("%s %s", container.Path, argsAsString)
	} else {
		snapshot.Command = container.Path
	}

	snapshot.Ports = []types.Port{}
	networks := make(map[string]*network.EndpointSettings)
	if container.NetworkSettings != nil {
		for name, netw := range container.NetworkSettings.Networks {
			if netw == nil || netw.EndpointSettings == nil {
				continue
			}
			networks[name] = &network.EndpointSettings{
				EndpointID:          netw.EndpointID,
				Gateway:             netw.Gateway,
				IPAddress:           netw.IPAddress,
				IPPrefixLen:         netw.IPPrefixLen,
				IPv6Gateway:         netw.IPv6Gateway,
				GlobalIPv6Address:   netw.GlobalIPv6Address,
				GlobalIPv6PrefixLen: netw.GlobalIPv6PrefixLen,
				MacAddress:          netw.MacAddress,
				NetworkID:           netw.NetworkID,
			}
			if netw.IPAMConfig != nil {
				networks[name].IPAMConfig = &network.EndpointIPAMConfig{
					IPv4Address: netw.IPAMConfig.IPv4Address,
					IPv6Address: netw.IPAMConfig.IPv6Address,
				}
			}
		}
		for port, bindings := range container.NetworkSettings.Ports {
			p, err := nat.ParsePort(port.Port())
			if err != nil {
				logrus.Warnf("invalid port map %+v", err)
				continue
			}
			if len(bindings) == 0 {
				snapshot.Ports = append(snapshot.Ports, types.Port{
					PrivatePort: uint16(p),
					Type:        port.Proto(),
				})
				continue
			}
			for _, binding := range bindings {
				h, err := nat.ParsePort(binding.HostPort)
				if err != nil {
					logrus.Warnf("invalid host port map %+v", err)
					continue
				}
				snapshot.Ports = append(snapshot.Ports, types.Port{
					PrivatePort: uint16(p),
					PublicPort:  uint16(h),
					Type:        port.Proto(),
					IP:          binding.HostIP,
				})
			}
		}
	}
	snapshot.NetworkSettings = &types.SummaryNetworkSettings{Networks: networks}

	return snapshot
}

// containerByIDIndexer is used to extract the ID field from Container types.
// memdb.StringFieldIndex can not be used since ID is a field from an embedded struct.
type containerByIDIndexer struct{}

// FromObject implements the memdb.SingleIndexer interface for Container objects
func (e *containerByIDIndexer) FromObject(obj interface{}) (bool, []byte, error) {
	c, ok := obj.(*Container)
	if !ok {
		return false, nil, fmt.Errorf("%T is not a Container", obj)
	}
	// Add the null character as a terminator
	v := c.ID + "\x00"
	return true, []byte(v), nil
}

// FromArgs implements the memdb.Indexer interface
func (e *containerByIDIndexer) FromArgs(args ...interface{}) ([]byte, error) {
	if len(args) != 1 {
		return nil, fmt.Errorf("must provide only a single argument")
	}
	arg, ok := args[0].(string)
	if !ok {
		return nil, fmt.Errorf("argument must be a string: %#v", args[0])
	}
	// Add the null character as a terminator
	arg += "\x00"
	return []byte(arg), nil
}

// namesByNameIndexer is used to index container name associations by name.
type namesByNameIndexer struct{}

func (e *namesByNameIndexer) FromObject(obj interface{}) (bool, []byte, error) {
	n, ok := obj.(nameAssociation)
	if !ok {
		return false, nil, fmt.Errorf(`%T does not have type "nameAssociation"`, obj)
	}

	// Add the null character as a terminator
	return true, []byte(n.name + "\x00"), nil
}

func (e *namesByNameIndexer) FromArgs(args ...interface{}) ([]byte, error) {
	if len(args) != 1 {
		return nil, fmt.Errorf("must provide only a single argument")
	}
	arg, ok := args[0].(string)
	if !ok {
		return nil, fmt.Errorf("argument must be a string: %#v", args[0])
	}
	// Add the null character as a terminator
	arg += "\x00"
	return []byte(arg), nil
}

// namesByContainerIDIndexer is used to index container names by container ID.
type namesByContainerIDIndexer struct{}

func (e *namesByContainerIDIndexer) FromObject(obj interface{}) (bool, []byte, error) {
	n, ok := obj.(nameAssociation)
	if !ok {
		return false, nil, fmt.Errorf(`%T does not have type "nameAssociation"`, obj)
	}

	// Add the null character as a terminator
	return true, []byte(n.containerID + "\x00"), nil
}

func (e *namesByContainerIDIndexer) FromArgs(args ...interface{}) ([]byte, error) {
	if len(args) != 1 {
		return nil, fmt.Errorf("must provide only a single argument")
	}
	arg, ok := args[0].(string)
	if !ok {
		return nil, fmt.Errorf("argument must be a string: %#v", args[0])
	}
	// Add the null character as a terminator
	arg += "\x00"
	return []byte(arg), nil
}

package container // import "github.com/docker/docker/container"

import (
	"errors"
	"fmt"
	"strings"
	"time"

	"github.com/docker/docker/api/types"
	"github.com/docker/docker/api/types/network"
	"github.com/docker/go-connections/nat"
	memdb "github.com/hashicorp/go-memdb"
	"github.com/sirupsen/logrus"
)

const (
	memdbContainersTable  = "containers"
	memdbNamesTable       = "names"
	memdbIDIndex          = "id"
	memdbIDIndexPrefix    = "id_prefix"
	memdbContainerIDIndex = "containerid"
)

var (
	// ErrNameReserved is an error which is returned when a name is requested to be reserved that already is reserved
	ErrNameReserved = errors.New("name is reserved")
	// ErrNameNotReserved is an error which is returned when trying to find a name that is not reserved
	ErrNameNotReserved = errors.New("name is not reserved")
)

var (
	// ErrEmptyPrefix is an error returned if the prefix was empty.
	ErrEmptyPrefix = errors.New("Prefix can't be empty")

	// ErrNotExist is returned when ID or its prefix not found in index.
	ErrNotExist = errors.New("ID does not exist")
)

// ErrAmbiguousPrefix is returned if the prefix was ambiguous
// (multiple ids for the prefix).
type ErrAmbiguousPrefix struct {
	prefix string
}

func (e ErrAmbiguousPrefix) Error() string {
	return fmt.Sprintf("Multiple IDs found with provided prefix: %s", e.prefix)
}

// Snapshot is a read only view for Containers. It holds all information necessary to serve container queries in a
// versioned ACID in-memory store.
type Snapshot struct {
	types.Container

	// additional info queries need to filter on
	// preserve nanosec resolution for queries
	CreatedAt    time.Time
	StartedAt    time.Time
	Name         string
	Pid          int
	ExitCode     int
	Running      bool
	Paused       bool
	Managed      bool
	ExposedPorts nat.PortSet
	PortBindings nat.PortSet
	Health       string
	HostConfig   struct {
		Isolation string
	}
}

// nameAssociation associates a container id with a name.
type nameAssociation struct {
	// name is the name to associate. Note that name is the primary key
	// ("id" in memdb).
	name        string
	containerID string
}

// ViewDB provides an in-memory transactional (ACID) container Store
type ViewDB interface {
	Snapshot() View
	Save(*Container) error
	Delete(*Container) error

	GetByPrefix(string) (string, error)

	ReserveName(name, containerID string) error
	ReleaseName(name string) error
}

// View can be used by readers to avoid locking
type View interface {
	All() ([]Snapshot, error)
	Get(id string) (*Snapshot, error)

	GetID(name string) (string, error)
	GetAllNames() map[string][]string
}

var schema = &memdb.DBSchema{
	Tables: map[string]*memdb.TableSchema{
		memdbContainersTable: {
			Name: memdbContainersTable,
			Indexes: map[string]*memdb.IndexSchema{
				memdbIDIndex: {
					Name:    memdbIDIndex,
					Unique:  true,
					Indexer: &containerByIDIndexer{},
				},
			},
		},
		memdbNamesTable: {
			Name: memdbNamesTable,
			Indexes: map[string]*memdb.IndexSchema{
				// Used for names, because "id" is the primary key in memdb.
				memdbIDIndex: {
					Name:    memdbIDIndex,
					Unique:  true,
					Indexer: &namesByNameIndexer{},
				},
				memdbContainerIDIndex: {
					Name:    memdbContainerIDIndex,
					Indexer: &namesByContainerIDIndexer{},
				},
			},
		},
	},
}

type memDB struct {
	store *memdb.MemDB
}

// NoSuchContainerError indicates that the container wasn't found in the
// database.
type NoSuchContainerError struct {
	id string
}

// Error satisfies the error interface.
func (e NoSuchContainerError) Error() string {
	return "no such container " + e.id
}

// NewViewDB provides the default implementation, with the default schema
func NewViewDB() (ViewDB, error) {
	store, err := memdb.NewMemDB(schema)
	if err != nil {
		return nil, err
	}
	return &memDB{store: store}, nil
}

func (db *memDB) GetByPrefix(s string) (string, error) {
	if s == "" {
		return "", ErrEmptyPrefix
	}
	txn := db.store.Txn(false)
	iter, err := txn.Get(memdbContainersTable, memdbIDIndexPrefix, s)
	if err != nil {
		return "", err
	}

	var (
		id string
	)

	for {
		item := iter.Next()
		if item == nil {
			break
		}
		if id != "" {
			return "", ErrAmbiguousPrefix{prefix: s}
		}
		id = item.(*Container).ID
	}

	if id != "" {
		return id, nil
	}

	return "", ErrNotExist
}

// Snapshot provides a consistent read-only View of the database
func (db *memDB) Snapshot() View {
	return &memdbView{
		txn: db.store.Txn(false),
	}
}

func (db *memDB) withTxn(cb func(*memdb.Txn) error) error {
	txn := db.store.Txn(true)
	err := cb(txn)
	if err != nil {
		txn.Abort()
		return err
	}
	txn.Commit()
	return nil
}

// Save atomically updates the in-memory store state for a Container.
// Only read only (deep) copies of containers may be passed in.
func (db *memDB) Save(c *Container) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		return txn.Insert(memdbContainersTable, c)
	})
}

// Delete removes an item by ID
func (db *memDB) Delete(c *Container) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		view := &memdbView{txn: txn}
		names := view.getNames(c.ID)

		for _, name := range names {
			txn.Delete(memdbNamesTable, nameAssociation{name: name})
		}

		// Ignore error - the container may not actually exist in the
		// db, but we still need to clean up associated names.
		txn.Delete(memdbContainersTable, NewBaseContainer(c.ID, c.Root))
		return nil
	})
}

// ReserveName registers a container ID to a name
// ReserveName is idempotent
// Attempting to reserve a container ID to a name that already exists results in an `ErrNameReserved`
// A name reservation is globally unique
func (db *memDB) ReserveName(name, containerID string) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		s, err := txn.First(memdbNamesTable, memdbIDIndex, name)
		if err != nil {
			return err
		}
		if s != nil {
			if s.(nameAssociation).containerID != containerID {
				return ErrNameReserved
			}
			return nil
		}
		return txn.Insert(memdbNamesTable, nameAssociation{name: name, containerID: containerID})
	})
}

// ReleaseName releases the reserved name
// Once released, a name can be reserved again
func (db *memDB) ReleaseName(name string) error {
	return db.withTxn(func(txn *memdb.Txn) error {
		return txn.Delete(memdbNamesTable, nameAssociation{name: name})
	})
}

type memdbView struct {
	txn *memdb.Txn
}

// All returns a all items in this snapshot. Returned objects must never be modified.
func (v *memdbView) All() ([]Snapshot, error) {
	var all []Snapshot
	iter, err := v.txn.Get(memdbContainersTable, memdbIDIndex)
	if err != nil {
		return nil, err
	}
	for {
		item := iter.Next()
		if item == nil {
			break
		}
		snapshot := v.transform(item.(*Container))
		all = append(all, *snapshot)
	}
	return all, nil
}

// Get returns an item by id. Returned objects must never be modified.
func (v *memdbView) Get(id string) (*Snapshot, error) {
	s, err := v.txn.First(memdbContainersTable, memdbIDIndex, id)
	if err != nil {
		return nil, err
	}
	if s == nil {
		return nil, NoSuchContainerError{id: id}
	}
	return v.transform(s.(*Container)), nil
}

// getNames lists all the reserved names for the given container ID.
func (v *memdbView) getNames(containerID string) []string {
	iter, err := v.txn.Get(memdbNamesTable, memdbContainerIDIndex, containerID)
	if err != nil {
		return nil
	}

	var names []string
	for {
		item := iter.Next()
		if item == nil {
			break
		}
		names = append(names, item.(nameAssociation).name)
	}

	return names
}

// GetID returns the container ID that the passed in name is reserved to.
func (v *memdbView) GetID(name string) (string, error) {
	s, err := v.txn.First(memdbNamesTable, memdbIDIndex, name)
	if err != nil {
		return "", err
	}
	if s == nil {
		return "", ErrNameNotReserved
	}
	return s.(nameAssociation).containerID, nil
}

// GetAllNames returns all registered names.
func (v *memdbView) GetAllNames() map[string][]string {
	iter, err := v.txn.Get(memdbNamesTable, memdbContainerIDIndex)
	if err != nil {
		return nil
	}

	out := make(map[string][]string)
	for {
		item := iter.Next()
		if item == nil {
			break
		}
		assoc := item.(nameAssociation)
		out[assoc.containerID] = append(out[assoc.containerID], assoc.name)
	}

	return out
}

// transform maps a (deep) copied Container object to what queries need.
// A lock on the Container is not held because these are immutable deep copies.
func (v *memdbView) transform(container *Container) *Snapshot {
	health := types.NoHealthcheck
	if container.Health != nil {
		health = container.Health.Status()
	}
	snapshot := &Snapshot{
		Container: types.Container{
			ID:      container.ID,
			Names:   v.getNames(container.ID),
			ImageID: container.ImageID.String(),
			Ports:   []types.Port{},
			Mounts:  container.GetMountPoints(),
			State:   container.State.StateString(),
			Status:  container.State.String(),
			Created: container.Created.Unix(),
		},
		CreatedAt:    container.Created,
		StartedAt:    container.StartedAt,
		Name:         container.Name,
		Pid:          container.Pid,
		Managed:      container.Managed,
		ExposedPorts: make(nat.PortSet),
		PortBindings: make(nat.PortSet),
		Health:       health,
		Running:      container.Running,
		Paused:       container.Paused,
		ExitCode:     container.ExitCode(),
	}

	if snapshot.Names == nil {
		// Dead containers will often have no name, so make sure the response isn't null
		snapshot.Names = []string{}
	}

	if container.HostConfig != nil {
		snapshot.Container.HostConfig.NetworkMode = string(container.HostConfig.NetworkMode)
		snapshot.HostConfig.Isolation = string(container.HostConfig.Isolation)
		for binding := range container.HostConfig.PortBindings {
			snapshot.PortBindings[binding] = struct{}{}
		}
	}

	if container.Config != nil {
		snapshot.Image = container.Config.Image
		snapshot.Labels = container.Config.Labels
		for exposed := range container.Config.ExposedPorts {
			snapshot.ExposedPorts[exposed] = struct{}{}
		}
	}

	if len(container.Args) > 0 {
		var args []string
		for _, arg := range container.Args {
			if strings.Contains(arg, " ") {
				args = append(args, fmt.Sprintf("'%s'", arg))
			} else {
				args = append(args, arg)
			}
		}
		argsAsString := strings.Join(args, " ")
		snapshot.Command = fmt.Sprintf("%s %s", container.Path, argsAsString)
	} else {
		snapshot.Command = container.Path
	}

	snapshot.Ports = []types.Port{}
	networks := make(map[string]*network.EndpointSettings)
	if container.NetworkSettings != nil {
		for name, netw := range container.NetworkSettings.Networks {
			if netw == nil || netw.EndpointSettings == nil {
				continue
			}
			networks[name] = &network.EndpointSettings{
				EndpointID:          netw.EndpointID,
				Gateway:             netw.Gateway,
				IPAddress:           netw.IPAddress,
				IPPrefixLen:         netw.IPPrefixLen,
				IPv6Gateway:         netw.IPv6Gateway,
				GlobalIPv6Address:   netw.GlobalIPv6Address,
				GlobalIPv6PrefixLen: netw.GlobalIPv6PrefixLen,
				MacAddress:          netw.MacAddress,
				NetworkID:           netw.NetworkID,
			}
			if netw.IPAMConfig != nil {
				networks[name].IPAMConfig = &network.EndpointIPAMConfig{
					IPv4Address: netw.IPAMConfig.IPv4Address,
					IPv6Address: netw.IPAMConfig.IPv6Address,
				}
			}
		}
		for port, bindings := range container.NetworkSettings.Ports {
			p, err := nat.ParsePort(port.Port())
			if err != nil {
				logrus.Warnf("invalid port map %+v", err)
				continue
			}
			if len(bindings) == 0 {
				snapshot.Ports = append(snapshot.Ports, types.Port{
					PrivatePort: uint16(p),
					Type:        port.Proto(),
				})
				continue
			}
			for _, binding := range bindings {
				h, err := nat.ParsePort(binding.HostPort)
				if err != nil {
					logrus.Warnf("invalid host port map %+v", err)
					continue
				}
				snapshot.Ports = append(snapshot.Ports, types.Port{
					PrivatePort: uint16(p),
					PublicPort:  uint16(h),
					Type:        port.Proto(),
					IP:          binding.HostIP,
				})
			}
		}
	}
	snapshot.NetworkSettings = &types.SummaryNetworkSettings{Networks: networks}

	return snapshot
}

// containerByIDIndexer is used to extract the ID field from Container types.
// memdb.StringFieldIndex can not be used since ID is a field from an embedded struct.
type containerByIDIndexer struct{}

// FromObject implements the memdb.SingleIndexer interface for Container objects
func (e *containerByIDIndexer) FromObject(obj interface{}) (bool, []byte, error) {
	c, ok := obj.(*Container)
	if !ok {
		return false, nil, fmt.Errorf("%T is not a Container", obj)
	}
	// Add the null character as a terminator
	v := c.ID + "\x00"
	return true, []byte(v), nil
}

// FromArgs implements the memdb.Indexer interface
func (e *containerByIDIndexer) FromArgs(args ...interface{}) ([]byte, error) {
	if len(args) != 1 {
		return nil, fmt.Errorf("must provide only a single argument")
	}
	arg, ok := args[0].(string)
	if !ok {
		return nil, fmt.Errorf("argument must be a string: %#v", args[0])
	}
	// Add the null character as a terminator
	arg += "\x00"
	return []byte(arg), nil
}

func (e *containerByIDIndexer) PrefixFromArgs(args ...interface{}) ([]byte, error) {
	val, err := e.FromArgs(args...)
	if err != nil {
		return nil, err
	}

	// Strip the null terminator, the rest is a prefix
	n := len(val)
	if n > 0 {
		return val[:n-1], nil
	}
	return val, nil
}

// namesByNameIndexer is used to index container name associations by name.
type namesByNameIndexer struct{}

func (e *namesByNameIndexer) FromObject(obj interface{}) (bool, []byte, error) {
	n, ok := obj.(nameAssociation)
	if !ok {
		return false, nil, fmt.Errorf(`%T does not have type "nameAssociation"`, obj)
	}

	// Add the null character as a terminator
	return true, []byte(n.name + "\x00"), nil
}

func (e *namesByNameIndexer) FromArgs(args ...interface{}) ([]byte, error) {
	if len(args) != 1 {
		return nil, fmt.Errorf("must provide only a single argument")
	}
	arg, ok := args[0].(string)
	if !ok {
		return nil, fmt.Errorf("argument must be a string: %#v", args[0])
	}
	// Add the null character as a terminator
	arg += "\x00"
	return []byte(arg), nil
}

// namesByContainerIDIndexer is used to index container names by container ID.
type namesByContainerIDIndexer struct{}

func (e *namesByContainerIDIndexer) FromObject(obj interface{}) (bool, []byte, error) {
	n, ok := obj.(nameAssociation)
	if !ok {
		return false, nil, fmt.Errorf(`%T does not have type "nameAssociation"`, obj)
	}

	// Add the null character as a terminator
	return true, []byte(n.containerID + "\x00"), nil
}

func (e *namesByContainerIDIndexer) FromArgs(args ...interface{}) ([]byte, error) {
	if len(args) != 1 {
		return nil, fmt.Errorf("must provide only a single argument")
	}
	arg, ok := args[0].(string)
	if !ok {
		return nil, fmt.Errorf("argument must be a string: %#v", args[0])
	}
	// Add the null character as a terminator
	arg += "\x00"
	return []byte(arg), nil
}

Not new, so ok to do in a follow-up, but this should be lowercase `prefix`, and ideally, it would return an error that implements `errdefs.ErrInvalidParameter`; https://github.com/moby/moby/blob/7d4b7883815d45a0b4e1f4c50ec566e24040cb2a/errdefs/defs.go#L8-L11
