1/*
2 * Copyright (c) 2013-2019, Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020, Huawei Device Co., Ltd. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this list of
9 *    conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 *    of conditions and the following disclaimer in the documentation and/or other materials
13 *    provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
16 *    to endorse or promote products derived from this software without specific prior written
17 *    permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32/* Architecture Analysis
33 *********************************************************************************************
34 *      The USB Devices Topology    ---    Translate   -->  Binary Tree Map
35 *               BUS                                             BUS
36 *                |                                              /
37 *       ---------------------                                  /
38 *       |                   |                                 H01
39 *      H01                 H02...                             / \
40 *       |                   |                                /   \
41 * ------------      ---------------                        H11    \---------H02
42 * |          |      |             |         ------\        / \              / \
43 *H11        H12... H21           H22...     -------\      /   \            /   \
44 * |          |      |             |         -------/     D1   H12         H21  ...
45 *D1         D2      |            D3         ------/           / \         / \
46 *              ------------                                  /   \       /   \
47 *              |          |                                 D2   ...    H31   \----H22
48 *             H31        H32...                                          / \        / \
49 *              |          |                                             /   \      /   \
50 *             D4         D5                                            D4   H32   D3   ...
51 *                                                                      / \
52 *                                                                     /   \
53 *                                                                    D5   ...
54 *********************************************************************************************
55 */
56
57#include <stdlib.h>
58#include <string.h>
59#include <los_printf_pri.h>
60
61#include "implementation/usb_btree.h"
62
63
64#ifdef USB_BINARY_TREE_DEBUG
65#define	BT_DEBUG(x...) dprintf(x)
66#else
67#define	BT_DEBUG(x...) do{}while(0)
68#endif
69
70extern usbd_bt_tree hub_tree;
71
72struct usbd_bt_node *
73usbd_create_bt_node(struct node_info *info)
74{
75	struct usbd_bt_node *node = (usbd_bt_node *)malloc(sizeof(usbd_bt_node));
76	if (node == NULL) {
77		PRINT_ERR("Binary tree node alloc failed!\n");
78		return (NULL);
79	}
80
81	(void)memset_s(&node->info, sizeof(node->info), 0, sizeof(node->info));
82	node->info.port_no = info->port_no;
83	node->info.nameunit = info->nameunit;
84	node->lbt_node = NULL;
85	node->rbt_node = NULL;
86
87	BT_DEBUG("[create node] %p %s %d\n", node, node->info.nameunit, node->info.port_no);
88	return (node);
89}
90
91void
92usbd_free_bt_node(usbd_bt_node *node)
93{
94	BT_DEBUG("[free node] %p %s %d\n", node, node->info.nameunit, node->info.port_no);
95
96	node->info.nameunit = NULL;
97	node->info.port_no = 0;
98	node->lbt_node = NULL;
99	node->rbt_node = NULL;
100
101	free(node);
102}
103
104static void
105usbd_release_bt_node(usbd_bt_node *node)
106{
107	if (node == NULL)
108		return;
109
110	usbd_release_bt_node(node->lbt_node);
111	usbd_release_bt_node(node->rbt_node);
112
113	if (node->info.nameunit != NULL)
114		usbd_free_bt_node(node);
115}
116
117static struct usbd_bt_node *
118usbd_pre_order_bt_node(usbd_bt_node *node, struct node_info *info)
119{
120	usbd_bt_node *l_node, *r_node;
121
122	if (node == NULL) {
123		return (NULL);
124	}
125
126	if (node->info.nameunit == info->nameunit) {
127		if (node->info.port_no == info->port_no) {
128			return (node);
129		}
130	}
131
132	l_node = usbd_pre_order_bt_node(node->lbt_node, info);
133	if (l_node != NULL) {
134		return (l_node);
135	}
136	r_node = usbd_pre_order_bt_node(node->rbt_node, info);
137	if (r_node != NULL) {
138		return (r_node);
139	}
140
141	return (NULL);
142}
143
144static bool f_find_device = false;
145static struct usbd_bt_node *
146usbd_pre_order_hub_node(usbd_bt_node *node, char *devname, uint8_t *port_num)
147{
148	usbd_bt_node *l_node, *r_node;
149
150	if (node == NULL) {
151		return (NULL);
152	}
153
154	if (!strncmp(node->info.nameunit, "uhub", strlen("uhub"))) {
155		BT_DEBUG("[Hub Node] %p %s %d %d\n", node, node->info.nameunit, node->info.port_no, *port_num);
156		if (node->lbt_node == NULL) {
157			(*port_num)--;
158		} else {
159			if (!strncmp(node->lbt_node->info.nameunit, devname, strlen(devname))) {
160				(*port_num)--;
161				if (*port_num == 0)
162					f_find_device = 1;
163			}
164		}
165		if (*port_num == 0) {
166			return (node->lbt_node);
167		}
168	}
169
170	l_node = usbd_pre_order_hub_node(node->lbt_node, devname, port_num);
171	if (l_node != NULL) {
172		return (l_node);
173	}
174	r_node = usbd_pre_order_hub_node(node->rbt_node, devname, port_num);
175	if (r_node != NULL) {
176		return (r_node);
177	}
178	return (NULL);
179}
180
181static void
182usbd_per_order_hub_quantity(usbd_bt_node *node, uint8_t *port_qty)
183{
184	if (node == NULL) {
185		return;
186	}
187
188	if (!strncmp(node->info.nameunit, "uhub", strlen("uhub"))) {
189		if (node->lbt_node == NULL) {
190			(*port_qty)++;
191		} else {
192			if (strncmp(node->lbt_node->info.nameunit, "uhub", strlen("uhub"))) {
193				(*port_qty)++;
194			}
195		}
196	}
197
198	usbd_per_order_hub_quantity(node->lbt_node, port_qty);
199	usbd_per_order_hub_quantity(node->rbt_node, port_qty);
200}
201
202int
203usbd_get_hub_quantity(void)
204{
205	uint8_t quantity = 0;
206
207	usbd_per_order_hub_quantity(hub_tree, &quantity);
208
209	return (quantity);
210}
211
212struct usbd_bt_node *
213usbd_per_order_probe(usbd_bt_tree tree, char *devname, uint8_t *port_num)
214{
215	usbd_bt_node *node = usbd_pre_order_hub_node(tree, devname, port_num);
216
217	if ((node != NULL) && f_find_device) {
218		f_find_device = 0;
219		return (node);
220	}
221
222	return (NULL);
223}
224
225int
226usbd_insert_bt_node(usbd_bt_node *node, usbd_bt_tree tree, struct node_info *parent_info)
227{
228	usbd_bt_node *parent_node;
229
230	if ((node == NULL) || (tree == NULL) || (parent_info == NULL))
231		return (-1);
232
233	parent_node = usbd_pre_order_bt_node(tree, parent_info);
234	if (parent_node == NULL) {
235		PRINT_ERR("Find err, insert fail!\n");
236		return (-1);
237	}
238
239	if (parent_node->info.nameunit == node->info.nameunit) {  /* The same hub node. */
240		parent_node->rbt_node = node;
241	} else {  /* Other driver(hub or other) */
242		parent_node->lbt_node = node;
243	}
244
245	BT_DEBUG("[insert node] parent:%p %s %d\n \
246		    %s child :%p %s %d\n", \
247		    parent_node, parent_node->info.nameunit, parent_node->info.port_no,
248		    (parent_node->info.nameunit == node->info.nameunit ? "right" : "left"),
249		    node, node->info.nameunit, node->info.port_no);
250	return (0);
251}
252
253int
254usbd_remove_bt_node(usbd_bt_tree tree, struct node_info *p_info, struct node_info *rm_info)
255{
256	usbd_bt_node *rm_node;
257
258	if ((tree == NULL) || (p_info == NULL) || (rm_info == NULL))
259		return (-1);
260
261	rm_node = usbd_pre_order_bt_node(tree, rm_info);
262	if (rm_node == NULL) {
263		BT_DEBUG("Find err, remove fail!\n");
264		return (-1);
265	}
266
267	usbd_release_bt_node(rm_node);
268
269	/* release parent left node */
270	rm_node = usbd_pre_order_bt_node(tree, p_info);
271	if (rm_node == NULL) {
272		PRINT_ERR("Parent find err, remove fail!\n");
273		return (-1);
274	}
275	rm_node->lbt_node = NULL;
276
277	return (0);
278}
279
280