linux-master/lib/test_xarray.c

74 	XA_STATE_ORDER(xas, xa, index, order);
78 		xas_lock(&xas);
79 		curr = xas_store(&xas, entry);
80 		xas_unlock(&xas);
81 	} while (xas_nomem(&xas, gfp));
104 	XA_STATE(xas, xa, 0);
111 	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));
113 	XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));
114 	XA_BUG_ON(xa, xas_retry(&xas, NULL));
115 	XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));
116 	xas_reset(&xas);
117 	XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
118 	XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
119 	XA_BUG_ON(xa, xas.xa_node != NULL);
125 	XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
126 	xas.xa_node = XAS_RESTART;
127 	XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
131 	xas_lock(&xas);
132 	xas_set(&xas, 0);
133 	xas_store(&xas, XA_RETRY_ENTRY);
134 	xas_set(&xas, 1);
135 	xas_store(&xas, XA_RETRY_ENTRY);
137 	xas_set(&xas, 0);
138 	xas_for_each(&xas, entry, ULONG_MAX) {
139 		xas_store(&xas, xa_mk_index(xas.xa_index));
141 	xas_unlock(&xas);
220 			XA_STATE(xas, xa, i);
230 			xas_for_each(&xas, entry, ULONG_MAX)
236 			xas_set(&xas, 0);
239 			xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
256 	XA_STATE(xas, xa, 0);
263 	xas_lock(&xas);
264 	xas_load(&xas);
265 	xas_init_marks(&xas);
266 	xas_unlock(&xas);
274 	xas_reset(&xas);
276 	xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
281 	xas_lock(&xas);
282 	xas_for_each(&xas, entry, ULONG_MAX) {
283 		xas_init_marks(&xas);
284 		XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));
285 		XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));
287 	xas_unlock(&xas);
295 	XA_STATE(xas, xa, 0x41);
303 	xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) {
326 	XA_STATE(xas, xa, 1);
339 	xas_lock(&xas);
340 	XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));
341 	node = xas.xa_node;
343 	XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
345 	XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);
347 	XA_BUG_ON(xa, xas_load(&xas) != NULL);
348 	xas_unlock(&xas);
547 	XA_STATE(xas, xa, 0);
553 			xas_set(&xas, j);
555 				xas_lock(&xas);
556 				xas_store(&xas, xa_mk_index(j));
557 				xas_unlock(&xas);
558 			} while (xas_nomem(&xas, GFP_KERNEL));
561 		xas_set(&xas, ULONG_MAX);
563 			xas_lock(&xas);
564 			xas_store(&xas, xa_mk_value(0));
565 			xas_unlock(&xas);
566 		} while (xas_nomem(&xas, GFP_KERNEL));
568 		xas_lock(&xas);
569 		xas_store(&xas, NULL);
571 		xas_set(&xas, 0);
573 		xas_for_each(&xas, entry, ULONG_MAX) {
575 			xas_store(&xas, NULL);
578 		xas_unlock(&xas);
587 	XA_STATE(xas, xa, index);
597 	xas_lock(&xas);
598 	XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));
599 	xas_unlock(&xas);
612 	XA_STATE(xas, xa, index);
615 	xas_lock(&xas);
616 	XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
617 	XA_BUG_ON(xa, xas.xa_index != index);
618 	XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
619 	xas_unlock(&xas);
626 	XA_STATE(xas, xa, 0);
632 	xas_lock(&xas);
633 	xas_for_each(&xas, entry, ULONG_MAX) {
638 	xas_set(&xas, index + 1);
639 	xas_for_each(&xas, entry, ULONG_MAX) {
644 	xas_unlock(&xas);
737 	XA_STATE(xas, xa, index);
743 	xas_set_order(&xas, index, order);
746 		xas_lock_irq(&xas);
747 		xas_store(&xas, p);
748 		xas_unlock_irq(&xas);
756 		XA_BUG_ON(xa, xas_error(&xas) && xas_error(&xas) != -ENOMEM);
757 	} while (xas_nomem(&xas, GFP_KERNEL));
759 	XA_BUG_ON(xa, xas_error(&xas));
768 	XA_STATE(xas, xa, index);
770 	xas_set_order(&xas, index, order);
771 	xas_store(&xas, NULL);
772 	xas_init_marks(&xas);
787 	XA_STATE(xas, xa, index);
793 	xas_reset(&xas);
794 	p = xas_load(&xas);
795 	if (xas_retry(&xas, p))
1103 	XA_STATE_ORDER(xas, xa, start, order);
1108 	xas_lock(&xas);
1109 	xas_for_each_conflict(&xas, entry) {
1115 	xas_store(&xas, xa_mk_index(start));
1116 	xas_unlock(&xas);
1117 	if (xas_nomem(&xas, GFP_KERNEL)) {
1121 	XA_BUG_ON(xa, xas_error(&xas));
1208 			XA_STATE(xas, xa, j + index);
1213 			xas_for_each(&xas, entry, ULONG_MAX) {
1308 	XA_STATE(xas, xa, 0);
1316 				xas_set(&xas, j);
1317 				xas_for_each_marked(&xas, entry, k, XA_MARK_0)
1321 						xas.xa_node != XAS_RESTART);
1365 	XA_STATE(xas, xa, 0);
1370 	xas_for_each(&xas, entry, ULONG_MAX) {
1371 		if (xas_retry(&xas, entry))
1378 		xas_pause(&xas);
1382 	return entry ? xas.xa_index : -1;
1419 	XA_STATE(xas, xa, 0);
1432 	xas_for_each(&xas, entry, ULONG_MAX) {
1440 	xas_set(&xas, 0);
1442 	xas_for_each(&xas, entry, ULONG_MAX) {
1445 		xas_pause(&xas);
1455 	XA_STATE(xas, xa, 0);
1459 	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1460 	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1464 	xas_set(&xas, 0);
1465 	XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));
1466 	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1467 	xas_set(&xas, 0);
1468 	XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));
1469 	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1477 	XA_STATE(xas, xa, 0);
1481 	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1482 	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1485 	xas_set(&xas, 0);
1487 	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1488 	xas_pause(&xas);
1489 	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1498 	XA_STATE(xas, xa, 0);
1506 		void *entry = xas_next(&xas);
1508 			XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1509 		XA_BUG_ON(xa, xas.xa_index != i);
1515 	xas_next(&xas);
1516 	XA_BUG_ON(xa, xas.xa_index != i);
1519 		void *entry = xas_prev(&xas);
1522 			XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1523 		XA_BUG_ON(xa, xas.xa_index != i);
1530 	xas_set(&xas, ULONG_MAX);
1531 	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1532 	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1533 	XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
1534 	XA_BUG_ON(xa, xas.xa_index != 0);
1535 	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1536 	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1546 	XA_STATE(xas, xa, (1 << 16) - 1);
1554 		void *entry = xas_prev(&xas);
1557 		XA_BUG_ON(xa, i != xas.xa_index);
1560 	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1561 	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1564 		void *entry = xas_next(&xas);
1566 		XA_BUG_ON(xa, i != xas.xa_index);
1574 	i = xas.xa_index;
1578 		void *entry = xas_prev(&xas);
1584 		XA_BUG_ON(xa, i != xas.xa_index);
1587 	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1588 	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1591 		void *entry = xas_next(&xas);
1596 		XA_BUG_ON(xa, i != xas.xa_index);
1616 	XA_STATE_ORDER(xas, xa, index, order);
1620 		xas_lock(&xas);
1621 		XA_BUG_ON(xa, xas_find_conflict(&xas));
1622 		xas_create_range(&xas);
1623 		if (xas_error(&xas))
1626 			XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));
1627 			xas_next(&xas);
1630 		xas_unlock(&xas);
1631 	} while (xas_nomem(&xas, GFP_KERNEL));
1633 	XA_BUG_ON(xa, xas_error(&xas));
1661 	XA_STATE(xas, NULL, 0);
1662 	xas_set_err(&xas, -EEXIST);
1663 	xas_create_range(&xas);
1664 	XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1670 	XA_STATE_ORDER(xas, xa, index, order);
1671 	unsigned long base = xas.xa_index;
1676 		xas_lock(&xas);
1677 		xas_create_range(&xas);
1678 		if (xas_error(&xas))
1681 			void *old = xas_store(&xas, xa_mk_index(base + i));
1682 			if (xas.xa_index == index)
1686 			xas_next(&xas);
1689 		xas_unlock(&xas);
1690 	} while (xas_nomem(&xas, GFP_KERNEL));
1692 	XA_BUG_ON(xa, xas_error(&xas));
1702 	XA_STATE_ORDER(xas, xa, index, order);
1709 			xas_lock(&xas);
1710 			xas_create_range(&xas);
1711 			xas_unlock(&xas);
1712 		} while (xas_nomem(&xas, GFP_KERNEL));
1790 	XA_STATE_ORDER(xas, xa, index, new_order);
1797 	xas_split_alloc(&xas, xa, order, GFP_KERNEL);
1798 	xas_lock(&xas);
1799 	xas_split(&xas, xa, order);
1802 	xas_unlock(&xas);
1812 	xas_set_order(&xas, index, 0);
1815 	xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_1) {
1924 	XA_STATE(xas, xa, index);
1925 	xas_set_update(&xas, test_update_node);
1928 		xas_lock(&xas);
1929 		xas_store(&xas, xa_mk_value(0));
1930 		xas_next(&xas);
1931 		xas_store(&xas, xa_mk_value(1));
1932 		xas_unlock(&xas);
1933 	} while (xas_nomem(&xas, GFP_KERNEL));
1937 	xas_lock(&xas);
1938 	xas_next(&xas);
1939 	xas_store(&xas, &xas);
1942 	xas_store(&xas, xa_mk_value(2));
1943 	xas_unlock(&xas);
1961 		XA_STATE(xas, xa, 1 << order);
1965 		xas_load(&xas);
1966 		XA_BUG_ON(xa, xas.xa_node->count == 0);
1967 		XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1968 		XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1973 		XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1976 		XA_BUG_ON(xa, xas.xa_node->nr_values != 0);