Python

Solve 'uwsgi_response_write_body_do() TIMEOUT !!!' error

Recently I write a django service to produce very large data in response, about 10GB data per request or even larger sometimes.

When I use python manage.py runserver to test service, there is no problem. But when use nginx + uwsgi to support service, I can't get the complete response at the client side. At the same time, there is an error log in uwsgi.log and a regular log notice that uswgi has finished request processing:

1
2
3
Fri Feb  88 88:88:88 2088 - uwsgi_response_write_body_do() TIMEOUT !!!
OSError: write error
GET REQUEST-URL => generated 8888888888 bytes in 8888 msecs (HTTP/1.1 200) 8 headers in 888 bytes

When uwsgi outputs these logs, the client still receives response data until the size of received equal to the generated size output in server log. And the generated size is smaller than the full size of response. So I think there is a large buffer in Nginx. Uwsgi writes response to Nginx actively and the speed is very fast because they are in same machine. But Nginx writes response to client is slow. If Nginx stores response data in buffer, uwsgi's write request will block when buffer is full. If buffer size is very large, uwsgi will wait a long time before Nginx clears its buffer and write request timeout.
Only in this way the Nginx can still write data to client when uwsgi finishs processing and close response stream.

According to ngx_http_uwsgi_module's document:

When buffering is enabled, nginx receives a response from the uwsgi server as soon as possible, saving it into the buffers set by the uwsgi_buffer_size and uwsgi_buffers directives. If the whole response does not fit into memory, a part of it can be saved to a temporary file on the disk. Writing to temporary files is controlled by the uwsgi_max_temp_file_size and uwsgi_temp_file_write_size directives.

There are memory buffers and temporary file buffers. The default size of memory buffers is only a few kilobytes. But the default max size of temporary file buffers is 1024MB, which is approximately equal to the generated size in uwsgi log.

In order to solve this problem, we can just disable temporary file buffers, use the directive uwsgi_max_temp_file_size 0;.

A memory buffer of a few kilobytes is ok because it will not block uwsgi' write request much time.
But as the previous analysis, if the transmission speed between Nginx and client side is far slower to the speed between Nginx and uswgi, the problem will come up no matter how smaller the buffer is.
As the implementation of Django and uwsgi, uwsgi read a block of data and write to response stream, if the block size is large enough and the transmission speed to the client side is slow enough, the problem will come up even all buffers in Nginx disabled. Because the block can be considered as a different form of buffer.

So slower transmission speed to client side means the smaller size of buffer we can use.
And we don't know user's network conditions, what we can do is only disable buffers.

database

Codis请求转发流程分析

本文是的一篇 Codis 代码阅读笔记，涉及的是 codis-proxy 从接收 client 请求，转发给 redis(codis-server)，然后返回给 client 的过程。Codis 代码开始阅读的是重构后的2.0版本，流程比较清晰高效，后来需要了解公司对 Codis 的使用修改情况，而线上系统是基于1.8的，这个版本的请求解析转发流程则有点晦涩，所以把分析结果记录下来，也作为 golang-server 开发的一个参考。

codis-config 在1.8/2.0版本之间接口、代码结构变化很少，zk角色功能变化较多，这部分不在本文范围之内。

这幅图是解析转发请求的顺序图（请不要在意细节）：

其中以Chan结尾的代表结构体里的channel或list，其他为结构体里实现的函数，通过goroutine运行，其中：

  • redisTunnel & WritingLoop 分别负责一个client连接的读写两端，redisTunnel函数实现在Server类里；
  • TaskRunner与一个redis实例一一对应，因此proxy内对同一个redis的请求是串行的；
  • Server代表当前运行的Proxy实例。

在这个架构里：

  1. session类对应client实体，每个client有一对 read-routine & write-routine 处理 client 的读请求和返回请求，客户端请求和命令结果分别对应的结构体是PipelineRequest & PipelineResponse；
  2. 请求 PipelineRequest 在 Server::reqCh 里串行化了，由一个唯一的 Server::handleTopoEvent-routine 分发(dispatch)给不同的后端 redis(TaskRunner)。
  3. 每个后端 redis 对应一个 TaskRunner，有两个routine： writeLoop & readLoop。
    writeLoop routine 从 chan-in 读取 PipelineRequest 然后通过 socket 写给后端，同时从 chan-out 读取 ParseResp 并封装成 PipelineResponse 发送给 Session::backQ。
    readLoop routine 从 socket 读取解析数据封装成 ParseResp 然后插入到 chan-out。
  4. 这里面 dispatch 分发过程是串行的。
  5. mget/mset/del 是串行执行的，不直接使用TaskRunner，而是新建一个独立的到本机服务的连接，转换成单key操作。并且是一个短链接，虽然代码里用到了pool object，但只是用来建立连接的。

3.0与1.8的差别在于 session::loopReader (相当于1.8的 read-routine )在自己的 goroutine 里分派 Request object 到对应 Backend (对应1.8的 TaskRunner )的队列中，同时使用了 Future 模式，session::loopWriter 阻塞在对应的 Reqest::WaitGroup 上，Backend 处理完调用 Request::WaitGroup.done() 通知 loopWriter-routine 处理结束。去掉了串行 dispatch 这个瓶颈。

我的注释版代码: github

algorithm

B-Tree实现

依照CLRS讲解实现了一个B-Tree，包括create & insert & search & delete操作，实现上使用迭代完成，没有使用递归。
CODE: link.

B-Tree节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define T           85
#define BNODE_KEY_SIZE  (2*T-1)
#define BNODE_CHILDREN_SIZE (2*T)

struct BTreeNode {
    size_t count;
    bool is_leaf;

    size_t keys[BNODE_KEY_SIZE];
    size_t values[BNODE_KEY_SIZE];
    size_t children[BNODE_CHILDREN_SIZE];

    BTreeNode() : count(0), is_leaf(true) {}
};

字段具体含义不解释。每个BTreeNode对一个磁盘页，实现了一组sim_XXX()函数模拟磁盘数据载入写出过程，通常用户持有一个size_t类型的node id，使用sim_get_node(size_t node_id)函数载入对应的磁盘数据，并返回对应的内存地址，修改或访问完以后使用sim_release_node()释放并“写回磁盘”。目前这组函数里做的只是size_t和BTreeNode*类型间的转换，可以额外增加写cache、reference_count代码，模拟实际开销。

b_tree_insert() 实现可以检测重复key，如果重复则只是更新对应的value值。
该函数实现有一点需要注意：当关键字k插入到x节点时，对应的插入子树为ci[x]，如果n[ci[x]]==2t-1，则需要拆分子树ci[x]，拆分后k & keyi[x]的相对关系会变化，需要重新对比k & keyi[x] & keyi+1[x]三者间的关系：确定k是否重复，需要递归处理拆分出来的ci[x] & ci+1[x]中的哪一个，对应在实现代码的 line: 153-178。
这部分还可以不检测，split-child以后下次递归或循环还在当前节点处理而不下降，代码会清爽一些。

b_tree_delete() 实现复杂一些。按照CLRS描述，对于递归处理的下一节点x有：n[x]>=t，因此x有可能会跟左兄弟或有兄弟合并，合并后n[parent[x]]会减一，如果parent[x]是根节点，则意味着合并后x再无兄弟节点，x成为新的根节点。这种情况在2c) & 3b)里会出现，需要注意处理。

剩下的可以直接看代码，有问题可以留言。

algorithm

AC-Search实现

写了一遍多字符串匹配的ac-search算法，输出所有的原串匹配区间。

build_trie()构造一个trie，build_longest_trans_target()函数构造自动机无法前向匹配时的转移路径，即TrieNode::prefix字段。当自动机到达一个最终状态后(terminal state，TrieNode::pattern_end)构造原串当前位置之前的所有匹配区间，通过把patterns串reverse之后构造出一个prefix树然后遍历实现。如果有更好的匹配串构造方法请留言。

原理请参考： <Flexible Pattern Matching in Strings>, 3.2.2 Basic Aho-Corasick Algorithm.

Trie & reverse(patterns)之后的trie树和状态机构造代码

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
struct TrieNode {
    struct TrieNode* sibling;
    struct TrieNode* children;
    struct TrieNode* prefix;
    int height; // 1, 2, 3 ...
    bool pattern_end;
    char this_char;
    TrieNode() : sibling(nullptr), children(nullptr), prefix(nullptr), 
            height(0), pattern_end(false), this_char(0) {}
};

TrieNode* get_node() {
    return new TrieNode();
}

void release_node(TrieNode* node) {
    delete node;
}

void free_trie(TrieNode* root) {
    vector<TrieNode*> stack;
    stack.push_back(root);
    while(!stack.empty()){
        root = stack.back();
        if(root==nullptr) {
            stack.pop_back();
            continue;
        }
        stack.back() = root->sibling;
        stack.push_back(root->children);
        release_node(root);
    }
}

// assumption: there are no duplicate item and no empty string in strs.
TrieNode* build_trie(const vector<string>& strs) {
    // build root;
    TrieNode* root = nullptr;
    for(auto &str : strs) {
        int len = 0;
        TrieNode** insert_pos = &root;
        TrieNode* parent_node = nullptr;
        for(auto curr_char : str) {
            // find insert pos
            len += 1;
            while(*insert_pos!=nullptr && (*insert_pos)->this_char<curr_char)
                insert_pos = &(*insert_pos)->sibling;

            parent_node = *insert_pos;
            // new char, insert
            if(*insert_pos==nullptr || (*insert_pos)->this_char>curr_char) {
                parent_node = get_node();
                parent_node->sibling = *insert_pos;
                parent_node->this_char = curr_char;
                parent_node->height = len;
                *insert_pos = parent_node;
            }
            insert_pos = &parent_node->children;
        }
        // no duplicate
        assert(parent_node && parent_node->pattern_end==false);
        parent_node->pattern_end = true;
    }
    return root;
}

// 忽略这个名字吧。。
TrieNode* build_suffix(const vector<string>& strs) {
    TrieNode* root = nullptr;
    for(auto &str : strs) {
        TrieNode** insert_pos = &root;
        TrieNode* parent_node = nullptr;
        for(int i=0; i<str.size(); ++i) {
            char curr_char = str[str.size()-1-i];
            while(*insert_pos!=nullptr && (*insert_pos)->this_char<curr_char)
                insert_pos = &(*insert_pos)->sibling;

            parent_node = *insert_pos;
            if(*insert_pos==nullptr || (*insert_pos)->this_char>curr_char) {
                parent_node = get_node();
                parent_node->sibling = *insert_pos;
                parent_node->this_char = curr_char;
                parent_node->height = i+1;
                *insert_pos = parent_node;
            }
            insert_pos = &parent_node->children;
        }
        assert(parent_node && parent_node->pattern_end==false);
        parent_node->pattern_end = true;
    }
    return root;
}

TrieNode* list_search(TrieNode* list_head, char target) {
    while(list_head && list_head->this_char!=target)
        list_head = list_head->sibling;
    return list_head;
}

void build_longest_trans_target(TrieNode* root) {
    assert(root!=nullptr);
    vector<TrieNode*> stack;
    TrieNode* current = root;
    while(current) {
        stack.push_back(current);
        current = current->sibling;
    }
    // bfs可以正确传递pattern_end标志, 但是需要使用queue实现。
    // 此处dfs。
    while(!stack.empty()){
        current = stack.back();
        stack.pop_back();
        TrieNode* children = current->children;
        while(children) {
            TrieNode* candidate = current->prefix;
            while(candidate && children->prefix==nullptr) {
                children->prefix = list_search(candidate->children, children->this_char);
                candidate = candidate->prefix;
            }
            if(children->prefix==nullptr)
                children->prefix = list_search(root, children->this_char);
            assert(children->prefix!=children);
            stack.push_back(children);
            TrieNode* prefix = children->prefix;
            bool pattern_end = children->pattern_end;
            while(prefix && !pattern_end) {
                pattern_end = pattern_end || prefix->pattern_end;
                prefix = prefix->prefix;
            }
            children->pattern_end = pattern_end;
            children = children->sibling;
        }
    }
}

void print_tree(TrieNode* root, bool newline=true) {
    while(root) {
        cout << "(" << root->this_char << "," << root->height << "," 
            << root->pattern_end << ") ";
        print_tree(root->children, false);
        root = root->sibling;
    }
    if(newline) cout << endl;
}

ac-search & test

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
void fill_pattern_occurrence(TrieNode* suffix, const string& haystack, int pos, 
            vector<pair<int, int>>& result) {

    for(int i=pos; i>=0 && suffix; --i) {
        char curr_char = haystack[i];
        suffix = list_search(suffix, curr_char);
        if(suffix->pattern_end) {
            // [i, pos+1) ~ [i, pos]
            result.push_back(make_pair(i, pos+1));
        }
        suffix = suffix->children;
    }
}

// [begin_pos, end_pos)
vector<pair<int, int>> ac_search(TrieNode* root, TrieNode* suffix, const string& haystack) {
    assert(root!=nullptr);
    assert(suffix!=nullptr);

    vector<pair<int, int>> result;
    TrieNode* prev_matched = nullptr;
    TrieNode* curr_matched = nullptr;
    for(int i=0; i<haystack.size(); ++i) {
        char curr_char = haystack[i];
        while(prev_matched && !curr_matched) {
            curr_matched = list_search(prev_matched->children, curr_char);
            prev_matched = prev_matched->prefix;
        }
        if(curr_matched==nullptr)
            curr_matched = list_search(root, curr_char);
        if(curr_matched && curr_matched->pattern_end) {
            fill_pattern_occurrence(suffix, haystack, i, result);
        }
        prev_matched = curr_matched;
        curr_matched = nullptr;
    }
    return result;
}

int main(int argc, char** argv) {
    vector<string> patterns = {
        "announce",
        "annual",
        "annually",
    };
    string haystack = "annual_announce";

    TrieNode* prefix = build_trie(patterns);
    build_longest_trans_target(prefix);
    TrieNode* suffix = build_suffix(patterns);

    print_tree(prefix);
    print_tree(suffix);

    auto result = ac_search(prefix, suffix, haystack);
    for(auto& item : result) {
        cout << item.first << ", " << item.second << endl;
    }

    free_trie(prefix);
    free_trie(suffix);
    return 0;
}

完整代码：github

algorithm

LeetCode - Combination Sum II

Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.

先对C里的数字计数，然后递归处理，每个数字出现[0, count[num]]次。
自己写了个AVL树作为map计数。然后没有维护unique-number的列表，把AVL树先转成线索二叉树，然后遍历，结束后再转回普通树结构。不要问我为啥这么写，闲的。

AVL Tree实现

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
const size_t AVLTREE_MAX_HEIGHT = 62;

struct AVLTreeNode {
    AVLTreeNode* left;
    AVLTreeNode* right;
    int height;
    size_t key;
    int value;
    AVLTreeNode(size_t k=0, int v=0) : left(nullptr), right(nullptr), height(1), key(k), value(v) {}
};

int avl_height(AVLTreeNode* root) {
    return root?root->height:0;
}

int avl_height_update(AVLTreeNode* root) {
    // assert(root!=NULL);
    return (root->height = std::max(avl_height(root->left), avl_height(root->right)) + 1);
}

int avl_balance_factor(AVLTreeNode* root) {
    // assert(root!=NULL);
    return avl_height(root->left) - avl_height(root->right);
}

AVLTreeNode* avl_rotate_left(AVLTreeNode* root) {
    // assert(root!=nullptr);
    AVLTreeNode* right = root->right;
    // assert(right!=nullptr);
    root->right= right->left;
    right->left = root;
    avl_height_update(root);
    avl_height_update(right);
    return right;
}

AVLTreeNode* avl_rotate_right(AVLTreeNode* root) {
    // assert(root!=nullptr);
    AVLTreeNode* left = root->left;
    // assert(right!=nullptr);
    root->left = left->right;
    left->right = root;
    avl_height_update(root);
    avl_height_update(left);
    return left;
}

// true:    insert;
// false:   update;
bool avl_insert(AVLTreeNode*& root, size_t key, int value) {
    AVLTreeNode* path[AVLTREE_MAX_HEIGHT] = {nullptr};
    int top_pos = 1;
    AVLTreeNode* curr = root;
    while(curr!=NULL) {
        path[top_pos++] = curr;
        if(curr->key>key) {
            curr = curr->left;
        } else if(curr->key<key) {
            curr = curr->right;
        } else {
            curr->value = value;
            return false;
        }
    }

    curr = new AVLTreeNode(key, value);
    AVLTreeNode* parent = path[--top_pos];
    if(parent==nullptr) root = curr;
    else if(parent->key<key) parent->right = curr;
    else parent->left = curr;

    while(parent!=nullptr) {
        int parent_balance_factor = avl_balance_factor(parent);
        int curr_balance_factor = avl_balance_factor(curr);
        if(parent_balance_factor==2) {
            if(curr_balance_factor==-1) {
                curr = avl_rotate_left(curr);
                parent->left = curr;
            }

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_right(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor==-2) {
            if(curr_balance_factor==1) {
                curr = avl_rotate_right(curr);
                parent->right = curr;
            }

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_left(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor==0) {
            break;
        }
        avl_height_update(parent);
        curr = parent;
        parent = path[--top_pos];
    }
    return true;
}

bool avl_search(AVLTreeNode* const root, size_t key, int* value) {
    AVLTreeNode* temp = root;
    while(temp) {
        if(temp->key==key) {
            if(value) *value = temp->value;
            return true;
        }
        if(temp->key < key) {
            temp = temp->right;
        } else {
            temp = temp->left;
        }
    }
    return false;
}

bool avl_delete(AVLTreeNode*& root, size_t key, int* value) {
    AVLTreeNode* path[AVLTREE_MAX_HEIGHT] = {nullptr};
    int top_pos = 1;
    AVLTreeNode* curr = root;
    AVLTreeNode* remove = nullptr;
    while(curr!=NULL) {
        if(curr->key==key)
            break;
        path[top_pos++] = curr;
        if(curr->key>key)
            curr = curr->left;
        else
            curr =curr->right;
    }
    if(curr==nullptr)
        return false;

    remove = curr;
    if(curr->left!=nullptr && curr->right!=nullptr)
    {
        remove = curr->left;
        path[top_pos++] = curr;
        while(remove->right) {
            path[top_pos++] = remove;
            remove = remove->right;
        }
    }

    AVLTreeNode* parent = path[--top_pos];
    if(parent==nullptr) {
        // assert(remove==curr);
        root = remove->left ? remove->left : remove->right;
        delete(remove);
        return true;
    }

    if(remove!=curr) {
        curr->key = remove->key;
        curr->value = remove->value;
    }
    curr = remove->left ? remove->left : remove->right;
    if(remove==parent->left)
        parent->left = curr;
    else
        parent->right = curr;

    delete(remove);

    while(parent!=nullptr) {
        parent->height = avl_height_update(parent);
        int parent_balance_factor = avl_balance_factor(parent);
        if(parent_balance_factor==2) {
            int curr_balance_factor = avl_balance_factor(parent->left);
            if(curr_balance_factor==-1)
                parent->left = avl_rotate_left(parent->left);

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_right(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor==-2) {
            int curr_balance_factor = avl_balance_factor(parent->right);
            if(curr_balance_factor==1)
                parent->right = avl_rotate_right(parent->right);

            AVLTreeNode** p_parent_parent = nullptr;
            if(path[top_pos-1]==nullptr)
                p_parent_parent = &root;
            else if(path[top_pos-1]->left == parent)
                p_parent_parent = &path[top_pos-1]->left;
            else
                p_parent_parent = &path[top_pos-1]->right;

            parent = avl_rotate_left(parent);
            *p_parent_parent = parent;
            break;
        } else if(parent_balance_factor == 1 || parent_balance_factor == -1) {
            break;
        }
        avl_height_update(parent);
        parent = path[--top_pos];
    }
    return true;
}

题目实现

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
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        AVLTreeNode* head = nullptr;
        int sum = 0;
        for(auto item: num) {
            int value = 0;
            bool ret = avl_search(head, item, &value);
            avl_insert(head, item, value+1);
        }
        vector<vector<int>> result;
        vector<int> buffer;
        buffer.reserve(num.size()/2);

        // 先将二叉树转成线索二叉树，然后再转换回来。
        // trans to threaded thee;
        AVLTreeNode* curr = head;
        AVLTreeNode* thread_head = nullptr;
        while(curr) {
            if(curr->left==nullptr) {
                if(thread_head==nullptr) thread_head = curr;
                curr = curr->right;
                continue;
            }
            AVLTreeNode* left = curr->left;
            while(left->right && left->right!=curr) left = left->right;
            if(left->right == nullptr) {
                left->right = curr;
                curr = curr->left;
            } else {
                curr = curr->right;
            }
        }

        dfs(thread_head, target, buffer, result);

        // unthread
        curr = thread_head;
        while(curr) {
            if(curr->left == nullptr) {
                curr = curr->right;
                continue;
            }
            AVLTreeNode* left = curr->left;
            while(left->right && left->right!=curr) left = left->right;
            if(left->right == curr) {
                left->right = nullptr;
                curr = curr->right;
            } else {
                assert(false && "should not here");
                curr = curr->left;
            }
        }
        return result;
    }
private:
    void dfs(AVLTreeNode* head, int target, vector<int>& tpl, vector<vector<int>>& result) {
        if(head==nullptr) return;
        int num = head->key;
        int i = 0;

        AVLTreeNode* next = head->right;
        AVLTreeNode* left = next ? next->left : nullptr;
        if(left) {
            while(left->right && left->right!=next) left = left->right;
            if(left != head) {
                while(next->left) next = next->left;
            }
        }

        do{
            if(target==0) result.push_back(tpl);
            else if(target>num) dfs(next, target, tpl, result);

            ++i;
            tpl.push_back(num);
            target -= num;
        }while(i<=head->value && target >=0);
        tpl.resize(tpl.size()-i);
    }
};

int main(int argc, char** argv) {
    vector<int> nums = {4,4,2,1,4,2,2,1,3};
    int target = 6;
    Solution s;

    auto result = s.combinationSum2(nums, target);
    cout << result.size() << endl;

    for(auto& item : result) {
        cout << "size(" << item.size() << ") ";
        for(auto val : item) {
            cout << val << ", ";
        }
        cout << endl;
    }
    return 0;
}

最开始是用它解Word Break的，但是hash冲突了，我也懒得再给TreeNode补个开链实现。