1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
// Copyright 2020 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef COMPONENTS_FEED_CORE_V2_STREAM_MODEL_FEATURE_TREE_H_
#define COMPONENTS_FEED_CORE_V2_STREAM_MODEL_FEATURE_TREE_H_
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "base/memory/raw_ptr.h"
#include "base/types/id_type.h"
#include "components/feed/core/proto/v2/store.pb.h"
#include "components/feed/core/v2/proto_util.h"
#include "components/feed/core/v2/types.h"
namespace feed {
namespace stream_model {
// Uniquely identifies a feedwire::ContentId. Provided by |ContentMap|.
using ContentTag = base::IdTypeU32<class ContentTagClass>;
using ContentRevision = feed::ContentRevision;
// Owns instances of feedstore::Content pointed to by the feature tree, and
// maps ContentId into ContentTag.
class ContentMap {
public:
explicit ContentMap(ContentRevision::Generator* revision_generator);
~ContentMap();
ContentMap(const ContentMap&) = delete;
ContentMap& operator=(const ContentMap&) = delete;
ContentTag GetContentTag(const feedwire::ContentId& id);
const feedstore::Content* FindContent(ContentRevision content_revision);
ContentRevision LookupContentRevision(const feedstore::Content& content);
ContentRevision AddContent(feedstore::Content content);
void Clear();
private:
ContentTag::Generator tag_generator_;
raw_ptr<ContentRevision::Generator> revision_generator_;
std::map<feedwire::ContentId, ContentTag, ContentIdCompareFunctor> mapping_;
// These two containers work together to store and index content.
// Each unique piece of content is stored once, and never removed.
std::map<feedstore::Content, ContentRevision, ContentCompareFunctor> content_;
std::vector<raw_ptr<const feedstore::Content, VectorExperimental>>
revision_to_content_;
};
// A node in FeatureTree.
struct StreamNode {
StreamNode();
~StreamNode();
StreamNode(const StreamNode&);
StreamNode& operator=(const StreamNode&);
// If true, this nodes has been removed and should be ignored.
bool tombstoned = false;
// Whether this node has a parent.
bool has_parent = false;
// If this node has content, this identifies it.
ContentRevision content_revision;
// Child relations are stored in linked-list fashion.
// The ID of the last child, or null.
ContentTag last_child;
// The ID of the sibling before this one.
ContentTag previous_sibling;
};
// The feature tree which underlies StreamModel.
// This tree is different than most, the rules are as follows:
// * A node may or may not have a parent, so this is more of a forest than a
// tree.
// * When nodes are removed, their set of children are remembered. If the node
// is added again, it retains its old children.
// * A node can be added multiple times, but subsequent adds will not change
// the node's parent.
// * There is only one 'stream root' acknowledged, even though there can be many
// roots. The stream root is the last root node added of type STREAM. The
// stream root identifies the tree whose nodes are used to compute
// |GetVisibleContent()|.
// * A tree can be constructed with a base tree. This copies features from base,
// but refers to content stored in base by reference.
class FeatureTree {
public:
// Constructor. |id_map| is retained by FeatureTree, and must have a greater
// scope than FeatureTree.
explicit FeatureTree(ContentMap* id_map);
// Create a |FeatureTree| which starts as a copy of |base|.
// Copies structure from |base|, and keeps a reference for content access.
explicit FeatureTree(const FeatureTree* base);
~FeatureTree();
FeatureTree(const FeatureTree& src) = delete;
FeatureTree& operator=(const FeatureTree& src) = delete;
// Mutations.
void ApplyStreamStructure(const feedstore::StreamStructure& structure);
// Adds |content| to the tree.
void AddContent(feedstore::Content content);
// Same as |AddContent()|, but can avoid a copy of |content| if it already
// exists.
void CopyAndAddContent(const feedstore::Content& content);
// Data access.
const StreamNode* FindNode(ContentTag id) const;
StreamNode* FindNode(ContentTag id);
const feedstore::Content* FindContent(ContentRevision id) const;
ContentTag GetContentTag(const feedwire::ContentId& id) {
return content_map_->GetContentTag(id);
}
// Returns the list of content that should be visible.
std::vector<ContentRevision> GetVisibleContent();
std::string DumpStateForTesting();
private:
StreamNode* GetOrMakeNode(ContentTag id);
void ResolveRoot();
void ResizeNodesIfNeeded(ContentTag id);
void RemoveFromParent(ContentTag node_id);
bool RemoveFromParent(StreamNode* parent, ContentTag node_id);
raw_ptr<const FeatureTree> base_ = nullptr; // Unowned.
raw_ptr<ContentMap> content_map_; // Unowned.
// Finding the root:
// We pick the root node as the last STREAM node which has no parent.
// In most cases, we can identify the root as the tree is built.
// But in some cases, we need to search all nodes to find the root.
// |computed_root_| is true if |root_tag_| is guaranteed to identify the root.
bool computed_root_ = true;
ContentTag root_tag_;
// All nodes in the forest, included removed nodes.
// This datastructure was selected to make copies efficient.
std::vector<StreamNode> nodes_;
};
} // namespace stream_model
} // namespace feed
#endif // COMPONENTS_FEED_CORE_V2_STREAM_MODEL_FEATURE_TREE_H_
|
