Skip to content

Commit 93d1dd8

Browse files
calaveracalavera
committed
Make filtering a linear operation.
Improves the current filtering implementation complixity. Currently, the best case is O(N) and worst case O(N^2) for key-value filtering. In the new implementation, the best case is O(1) and worst case O(N), again for key-value filtering. Signed-off-by: David Calavera <[email protected]>
1 parent 8a350c5 commit 93d1dd8

13 files changed

Lines changed: 443 additions & 237 deletions

File tree

‎api/client/events.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@ func (cli *DockerCli) CmdEvents(args ...string) error {
2626

2727
var (
2828
v = url.Values{}
29-
eventFilterArgs = filters.Args{}
29+
eventFilterArgs = filters.NewArgs()
3030
)
3131

3232
// Consolidate all filter flags, and sanity check them early.
@@ -53,7 +53,7 @@ func (cli *DockerCli) CmdEvents(args ...string) error {
5353
}
5454
v.Set("until", ts)
5555
}
56-
if len(eventFilterArgs) > 0 {
56+
if eventFilterArgs.Len() > 0 {
5757
filterJSON, err := filters.ToParam(eventFilterArgs)
5858
if err != nil {
5959
return err

‎api/client/images.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,7 @@ func (cli *DockerCli) CmdImages(args ...string) error {
3636

3737
// Consolidate all filter flags, and sanity check them early.
3838
// They'll get process in the daemon/server.
39-
imageFilterArgs := filters.Args{}
39+
imageFilterArgs := filters.NewArgs()
4040
for _, f := range flFilter.GetAll() {
4141
var err error
4242
imageFilterArgs, err = filters.ParseFlag(f, imageFilterArgs)
@@ -47,7 +47,7 @@ func (cli *DockerCli) CmdImages(args ...string) error {
4747

4848
matchName := cmd.Arg(0)
4949
v := url.Values{}
50-
if len(imageFilterArgs) > 0 {
50+
if imageFilterArgs.Len() > 0 {
5151
filterJSON, err := filters.ToParam(imageFilterArgs)
5252
if err != nil {
5353
return err

‎api/client/ps.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@ func (cli *DockerCli) CmdPs(args ...string) error {
2020
var (
2121
err error
2222

23-
psFilterArgs = filters.Args{}
23+
psFilterArgs = filters.NewArgs()
2424
v = url.Values{}
2525

2626
cmd = Cli.Subcmd("ps", nil, Cli.DockerCommands["ps"].Description, true)
@@ -72,7 +72,7 @@ func (cli *DockerCli) CmdPs(args ...string) error {
7272
}
7373
}
7474

75-
if len(psFilterArgs) > 0 {
75+
if psFilterArgs.Len() > 0 {
7676
filterJSON, err := filters.ToParam(psFilterArgs)
7777
if err != nil {
7878
return err

‎api/client/volume.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -54,7 +54,7 @@ func (cli *DockerCli) CmdVolumeLs(args ...string) error {
5454
cmd.Require(flag.Exact, 0)
5555
cmd.ParseFlags(args, true)
5656

57-
volFilterArgs := filters.Args{}
57+
volFilterArgs := filters.NewArgs()
5858
for _, f := range flFilter.GetAll() {
5959
var err error
6060
volFilterArgs, err = filters.ParseFlag(f, volFilterArgs)
@@ -64,7 +64,7 @@ func (cli *DockerCli) CmdVolumeLs(args ...string) error {
6464
}
6565

6666
v := url.Values{}
67-
if len(volFilterArgs) > 0 {
67+
if volFilterArgs.Len() > 0 {
6868
filterJSON, err := filters.ToParam(volFilterArgs)
6969
if err != nil {
7070
return err

‎api/server/router/network/network_routes.go‎

Lines changed: 13 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -29,27 +29,23 @@ func (n *networkRouter) getNetworksList(ctx context.Context, w http.ResponseWrit
2929
}
3030

3131
list := []*types.NetworkResource{}
32-
var nameFilter, idFilter bool
33-
var names, ids []string
34-
if names, nameFilter = netFilters["name"]; nameFilter {
35-
for _, name := range names {
36-
if nw, err := n.backend.GetNetwork(name, daemon.NetworkByName); err == nil {
37-
list = append(list, buildNetworkResource(nw))
38-
} else {
39-
logrus.Errorf("failed to get network for filter=%s : %v", name, err)
40-
}
32+
netFilters.WalkValues("name", func(name string) error {
33+
if nw, err := n.backend.GetNetwork(name, daemon.NetworkByName); err == nil {
34+
list = append(list, buildNetworkResource(nw))
35+
} else {
36+
logrus.Errorf("failed to get network for filter=%s : %v", name, err)
4137
}
42-
}
38+
return nil
39+
})
4340

44-
if ids, idFilter = netFilters["id"]; idFilter {
45-
for _, id := range ids {
46-
for _, nw := range n.backend.GetNetworksByID(id) {
47-
list = append(list, buildNetworkResource(nw))
48-
}
41+
netFilters.WalkValues("id", func(id string) error {
42+
for _, nw := range n.backend.GetNetworksByID(id) {
43+
list = append(list, buildNetworkResource(nw))
4944
}
50-
}
45+
return nil
46+
})
5147

52-
if !nameFilter && !idFilter {
48+
if !netFilters.Include("name") && !netFilters.Include("id") {
5349
nwList := n.backend.GetNetworksByID("")
5450
for _, nw := range nwList {
5551
list = append(list, buildNetworkResource(nw))

‎daemon/daemon.go‎

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -536,12 +536,11 @@ func (daemon *Daemon) GetByName(name string) (*Container, error) {
536536
func (daemon *Daemon) GetEventFilter(filter filters.Args) *events.Filter {
537537
// incoming container filter can be name, id or partial id, convert to
538538
// a full container id
539-
for i, cn := range filter["container"] {
539+
for _, cn := range filter.Get("container") {
540540
c, err := daemon.Get(cn)
541-
if err != nil {
542-
filter["container"][i] = ""
543-
} else {
544-
filter["container"][i] = c.ID
541+
filter.Del("container", cn)
542+
if err == nil {
543+
filter.Add("container", c.ID)
545544
}
546545
}
547546
return events.NewFilter(filter, daemon.GetLabels)

‎daemon/events/filter.go‎

Lines changed: 12 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -19,14 +19,14 @@ func NewFilter(filter filters.Args, getLabels func(id string) map[string]string)
1919

2020
// Include returns true when the event ev is included by the filters
2121
func (ef *Filter) Include(ev *jsonmessage.JSONMessage) bool {
22-
return isFieldIncluded(ev.Status, ef.filter["event"]) &&
23-
isFieldIncluded(ev.ID, ef.filter["container"]) &&
22+
return ef.filter.ExactMatch("event", ev.Status) &&
23+
ef.filter.ExactMatch("container", ev.ID) &&
2424
ef.isImageIncluded(ev.ID, ev.From) &&
2525
ef.isLabelFieldIncluded(ev.ID)
2626
}
2727

2828
func (ef *Filter) isLabelFieldIncluded(id string) bool {
29-
if _, ok := ef.filter["label"]; !ok {
29+
if !ef.filter.Include("label") {
3030
return true
3131
}
3232
return ef.filter.MatchKVList("label", ef.getLabels(id))
@@ -37,31 +37,16 @@ func (ef *Filter) isLabelFieldIncluded(id string) bool {
3737
// from an image will be included in the image events. Also compare both
3838
// against the stripped repo name without any tags.
3939
func (ef *Filter) isImageIncluded(eventID string, eventFrom string) bool {
40-
stripTag := func(image string) string {
41-
ref, err := reference.ParseNamed(image)
42-
if err != nil {
43-
return image
44-
}
45-
return ref.Name()
46-
}
47-
48-
return isFieldIncluded(eventID, ef.filter["image"]) ||
49-
isFieldIncluded(eventFrom, ef.filter["image"]) ||
50-
isFieldIncluded(stripTag(eventID), ef.filter["image"]) ||
51-
isFieldIncluded(stripTag(eventFrom), ef.filter["image"])
40+
return ef.filter.ExactMatch("image", eventID) ||
41+
ef.filter.ExactMatch("image", eventFrom) ||
42+
ef.filter.ExactMatch("image", stripTag(eventID)) ||
43+
ef.filter.ExactMatch("image", stripTag(eventFrom))
5244
}
5345

54-
func isFieldIncluded(field string, filter []string) bool {
55-
if len(field) == 0 {
56-
return true
57-
}
58-
if len(filter) == 0 {
59-
return true
60-
}
61-
for _, v := range filter {
62-
if v == field {
63-
return true
64-
}
46+
func stripTag(image string) string {
47+
ref, err := reference.ParseNamed(image)
48+
if err != nil {
49+
return image
6550
}
66-
return false
51+
return ref.Name()
6752
}

‎daemon/images.go‎

Lines changed: 12 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,6 @@ import (
44
"fmt"
55
"path"
66
"sort"
7-
"strings"
87

98
"github.com/docker/distribution/reference"
109
"github.com/docker/docker/api/types"
@@ -13,9 +12,9 @@ import (
1312
"github.com/docker/docker/pkg/parsers/filters"
1413
)
1514

16-
var acceptedImageFilterTags = map[string]struct{}{
17-
"dangling": {},
18-
"label": {},
15+
var acceptedImageFilterTags = map[string]bool{
16+
"dangling": true,
17+
"label": true,
1918
}
2019

2120
// byCreated is a temporary type used to sort a list of images by creation
@@ -47,19 +46,15 @@ func (daemon *Daemon) Images(filterArgs, filter string, all bool) ([]*types.Imag
4746
if err != nil {
4847
return nil, err
4948
}
50-
for name := range imageFilters {
51-
if _, ok := acceptedImageFilterTags[name]; !ok {
52-
return nil, fmt.Errorf("Invalid filter '%s'", name)
53-
}
49+
if err := imageFilters.Validate(acceptedImageFilterTags); err != nil {
50+
return nil, err
5451
}
5552

56-
if i, ok := imageFilters["dangling"]; ok {
57-
for _, value := range i {
58-
if v := strings.ToLower(value); v == "true" {
59-
danglingOnly = true
60-
} else if v != "false" {
61-
return nil, fmt.Errorf("Invalid filter 'dangling=%s'", v)
62-
}
53+
if imageFilters.Include("dangling") {
54+
if imageFilters.ExactMatch("dangling", "true") {
55+
danglingOnly = true
56+
} else if !imageFilters.ExactMatch("dangling", "false") {
57+
return nil, fmt.Errorf("Invalid filter 'dangling=%s'", imageFilters.Get("dangling"))
6358
}
6459
}
6560

@@ -82,9 +77,9 @@ func (daemon *Daemon) Images(filterArgs, filter string, all bool) ([]*types.Imag
8277
}
8378

8479
for id, img := range allImages {
85-
if _, ok := imageFilters["label"]; ok {
80+
if imageFilters.Include("label") {
81+
// Very old image that do not have image.Config (or even labels)
8682
if img.Config == nil {
87-
// Very old image that do not have image.Config (or even labels)
8883
continue
8984
}
9085
// We are now sure image.Config is not nil

‎daemon/list.go‎

Lines changed: 40 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,6 @@ import (
88

99
"github.com/Sirupsen/logrus"
1010
"github.com/docker/docker/api/types"
11-
derr "github.com/docker/docker/errors"
1211
"github.com/docker/docker/image"
1312
"github.com/docker/docker/pkg/graphdb"
1413
"github.com/docker/docker/pkg/nat"
@@ -136,64 +135,65 @@ func (daemon *Daemon) foldFilter(config *ContainersConfig) (*listContext, error)
136135
}
137136

138137
var filtExited []int
139-
if i, ok := psFilters["exited"]; ok {
140-
for _, value := range i {
141-
code, err := strconv.Atoi(value)
142-
if err != nil {
143-
return nil, err
144-
}
145-
filtExited = append(filtExited, code)
138+
err = psFilters.WalkValues("exited", func(value string) error {
139+
code, err := strconv.Atoi(value)
140+
if err != nil {
141+
return err
146142
}
143+
filtExited = append(filtExited, code)
144+
return nil
145+
})
146+
if err != nil {
147+
return nil, err
147148
}
148149

149-
if i, ok := psFilters["status"]; ok {
150-
for _, value := range i {
151-
if !isValidStateString(value) {
152-
return nil, errors.New("Unrecognised filter value for status")
153-
}
154-
155-
config.All = true
150+
err = psFilters.WalkValues("status", func(value string) error {
151+
if !isValidStateString(value) {
152+
return fmt.Errorf("Unrecognised filter value for status: %s", value)
156153
}
154+
155+
config.All = true
156+
return nil
157+
})
158+
if err != nil {
159+
return nil, err
157160
}
158161

159162
var beforeContFilter, sinceContFilter *Container
160-
if i, ok := psFilters["before"]; ok {
161-
for _, value := range i {
162-
beforeContFilter, err = daemon.Get(value)
163-
if err != nil {
164-
return nil, err
165-
}
166-
}
163+
err = psFilters.WalkValues("before", func(value string) error {
164+
beforeContFilter, err = daemon.Get(value)
165+
return err
166+
})
167+
if err != nil {
168+
return nil, err
167169
}
168170

169-
if i, ok := psFilters["since"]; ok {
170-
for _, value := range i {
171-
sinceContFilter, err = daemon.Get(value)
172-
if err != nil {
173-
return nil, err
174-
}
175-
}
171+
err = psFilters.WalkValues("since", func(value string) error {
172+
sinceContFilter, err = daemon.Get(value)
173+
return err
174+
})
175+
if err != nil {
176+
return nil, err
176177
}
177178

178179
imagesFilter := map[image.ID]bool{}
179180
var ancestorFilter bool
180-
if ancestors, ok := psFilters["ancestor"]; ok {
181+
if psFilters.Include("ancestor") {
181182
ancestorFilter = true
182-
// The idea is to walk the graph down the most "efficient" way.
183-
for _, ancestor := range ancestors {
184-
// First, get the imageId of the ancestor filter (yay)
183+
psFilters.WalkValues("ancestor", func(ancestor string) error {
185184
id, err := daemon.GetImageID(ancestor)
186185
if err != nil {
187186
logrus.Warnf("Error while looking up for image %v", ancestor)
188-
continue
187+
return nil
189188
}
190189
if imagesFilter[id] {
191190
// Already seen this ancestor, skip it
192-
continue
191+
return nil
193192
}
194193
// Then walk down the graph and put the imageIds in imagesFilter
195194
populateImageFilterByParents(imagesFilter, id, daemon.imageStore.Children)
196-
}
195+
return nil
196+
})
197197
}
198198

199199
names := make(map[string][]string)
@@ -202,14 +202,14 @@ func (daemon *Daemon) foldFilter(config *ContainersConfig) (*listContext, error)
202202
return nil
203203
}, 1)
204204

205-
if config.Before != "" {
205+
if config.Before != "" && beforeContFilter == nil {
206206
beforeContFilter, err = daemon.Get(config.Before)
207207
if err != nil {
208208
return nil, err
209209
}
210210
}
211211

212-
if config.Since != "" {
212+
if config.Since != "" && sinceContFilter == nil {
213213
sinceContFilter, err = daemon.Get(config.Since)
214214
if err != nil {
215215
return nil, err
@@ -397,17 +397,8 @@ func (daemon *Daemon) Volumes(filter string) ([]*types.Volume, error) {
397397
return nil, err
398398
}
399399

400-
filterUsed := false
401-
if i, ok := volFilters["dangling"]; ok {
402-
if len(i) > 1 {
403-
return nil, derr.ErrorCodeDanglingOne
404-
}
405-
406-
filterValue := i[0]
407-
if strings.ToLower(filterValue) == "true" || filterValue == "1" {
408-
filterUsed = true
409-
}
410-
}
400+
filterUsed := volFilters.Include("dangling") &&
401+
(volFilters.ExactMatch("dangling", "true") || volFilters.ExactMatch("dangling", "1"))
411402

412403
volumes := daemon.volumes.List()
413404
for _, v := range volumes {

0 commit comments

Comments
 (0)