202 is_bitmap(struct unrhdr *uh, struct unr *up)  in is_bitmap()  argument
204 	return (up->ptr != uh && up->ptr != NULL);  in is_bitmap()
231 	struct unrhdr *uh;  member
238 create_iter_unr(struct unrhdr *uh)  in create_iter_unr()  argument
244 	iter->uh = uh;  in create_iter_unr()
251 next_iter_unrl(struct unrhdr *uh, struct unrhdr_iter *iter)  in next_iter_unrl()  argument
259 		if (iter->upos == uh)  in next_iter_unrl()
261 		y = uh->low - 1;  in next_iter_unrl()
262 		if (uh->first == 0) {  in next_iter_unrl()
263 			up = TAILQ_FIRST(&uh->head);  in next_iter_unrl()
265 				iter->upos = uh;  in next_iter_unrl()
272 				iter->upos_first_item = uh->low;  in next_iter_unrl()
282 		if (y + 1 < uh->low + uh->first) {  in next_iter_unrl()
286 		up = iter->upos = TAILQ_FIRST(&uh->head);  in next_iter_unrl()
287 		iter->upos_first_item = uh->low + uh->first;  in next_iter_unrl()
292 			if (up->ptr == uh) {  in next_iter_unrl()
295 			} else if (is_bitmap(uh, up)) {  in next_iter_unrl()
311 			iter->upos = uh;  in next_iter_unrl()
323 	struct unrhdr *uh;  in next_iter_unr()  local
327 	uh = iter->uh;  in next_iter_unr()
328 	if (uh->mtx != NULL)  in next_iter_unr()
329 		mtx_lock(uh->mtx);  in next_iter_unr()
330 	next_iter_unrl(uh, iter);  in next_iter_unr()
331 	if (uh->mtx != NULL)  in next_iter_unr()
332 		mtx_unlock(uh->mtx);  in next_iter_unr()
355 check_unrhdr(struct unrhdr *uh, int line)  in check_unrhdr()  argument
362 	y = uh->first;  in check_unrhdr()
364 	TAILQ_FOREACH(up, &uh->head, list) {  in check_unrhdr()
366 		if (is_bitmap(uh, up)) {  in check_unrhdr()
378 	KASSERT (y == uh->busy,  in check_unrhdr()
380 	    uh->busy, y, line));  in check_unrhdr()
381 	KASSERT (z == uh->alloc,  in check_unrhdr()
383 	    uh->alloc, z, line));  in check_unrhdr()
389 check_unrhdr(struct unrhdr *uh __unused, int line __unused)  in check_unrhdr()
402 new_unr(struct unrhdr *uh, void **p1, void **p2)  in new_unr()  argument
406 	uh->alloc++;  in new_unr()
420 delete_unr(struct unrhdr *uh, void *ptr)  in delete_unr()  argument
424 	uh->alloc--;  in delete_unr()
426 	TAILQ_INSERT_TAIL(&uh->ppfree, up, list);  in delete_unr()
430 clean_unrhdrl(struct unrhdr *uh)  in clean_unrhdrl()  argument
434 	if (uh->mtx != NULL)  in clean_unrhdrl()
435 		mtx_assert(uh->mtx, MA_OWNED);  in clean_unrhdrl()
436 	while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {  in clean_unrhdrl()
437 		TAILQ_REMOVE(&uh->ppfree, up, list);  in clean_unrhdrl()
438 		if (uh->mtx != NULL)  in clean_unrhdrl()
439 			mtx_unlock(uh->mtx);  in clean_unrhdrl()
441 		if (uh->mtx != NULL)  in clean_unrhdrl()
442 			mtx_lock(uh->mtx);  in clean_unrhdrl()
448 clean_unrhdr(struct unrhdr *uh)  in clean_unrhdr()  argument
451 	if (uh->mtx != NULL)  in clean_unrhdr()
452 		mtx_lock(uh->mtx);  in clean_unrhdr()
453 	clean_unrhdrl(uh);  in clean_unrhdr()
454 	if (uh->mtx != NULL)  in clean_unrhdr()
455 		mtx_unlock(uh->mtx);  in clean_unrhdr()
459 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)  in init_unrhdr()  argument
465 		uh->mtx = NULL;  in init_unrhdr()
467 		uh->mtx = mutex;  in init_unrhdr()
469 		uh->mtx = &unitmtx;  in init_unrhdr()
470 	TAILQ_INIT(&uh->head);  in init_unrhdr()
471 	TAILQ_INIT(&uh->ppfree);  in init_unrhdr()
472 	uh->low = low;  in init_unrhdr()
473 	uh->high = high;  in init_unrhdr()
474 	uh->first = 0;  in init_unrhdr()
475 	uh->last = 1 + (high - low);  in init_unrhdr()
476 	uh->busy = 0;  in init_unrhdr()
477 	uh->alloc = 0;  in init_unrhdr()
478 	check_unrhdr(uh, __LINE__);  in init_unrhdr()
490 	struct unrhdr *uh;  in new_unrhdr()  local
492 	uh = Malloc(sizeof *uh);  in new_unrhdr()
493 	init_unrhdr(uh, low, high, mutex);  in new_unrhdr()
494 	return (uh);  in new_unrhdr()
498 delete_unrhdr(struct unrhdr *uh)  in delete_unrhdr()  argument
501 	check_unrhdr(uh, __LINE__);  in delete_unrhdr()
502 	KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));  in delete_unrhdr()
503 	KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));  in delete_unrhdr()
504 	KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,  in delete_unrhdr()
506 	Free(uh);  in delete_unrhdr()
510 clear_unrhdr(struct unrhdr *uh)  in clear_unrhdr()  argument
514 	KASSERT(TAILQ_EMPTY(&uh->ppfree),  in clear_unrhdr()
516 	TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) {  in clear_unrhdr()
517 		if (up->ptr != uh) {  in clear_unrhdr()
522 	uh->busy = 0;  in clear_unrhdr()
523 	uh->alloc = 0;  in clear_unrhdr()
524 	init_unrhdr(uh, uh->low, uh->high, uh->mtx);  in clear_unrhdr()
526 	check_unrhdr(uh, __LINE__);  in clear_unrhdr()
539 optimize_unr(struct unrhdr *uh)  in optimize_unr()  argument
551 	TAILQ_FOREACH(uf, &uh->head, list) {  in optimize_unr()
555 		if (is_bitmap(uh, uf))  in optimize_unr()
566 			if (is_bitmap(uh, up))  in optimize_unr()
583 	if (!is_bitmap(uh, us)) {  in optimize_unr()
585 		TAILQ_REMOVE(&uh->head, us, list);  in optimize_unr()
587 		l = us->ptr == uh ? 1 : 0;  in optimize_unr()
592 		if (!is_bitmap(uh, uf)) {  in optimize_unr()
609 			delete_unr(uh, uf->ptr);  in optimize_unr()
624 			TAILQ_REMOVE(&uh->head, uf, list);  in optimize_unr()
625 			delete_unr(uh, uf);  in optimize_unr()
626 		} else if (uf->ptr == uh) {  in optimize_unr()
629 			TAILQ_REMOVE(&uh->head, uf, list);  in optimize_unr()
630 			delete_unr(uh, uf);  in optimize_unr()
639 			TAILQ_REMOVE(&uh->head, uf, list);  in optimize_unr()
640 			delete_unr(uh, ubf);  in optimize_unr()
641 			delete_unr(uh, uf);  in optimize_unr()
652 collapse_unr(struct unrhdr *uh, struct unr *up)  in collapse_unr()  argument
658 	if (is_bitmap(uh, up)) {  in collapse_unr()
661 			delete_unr(uh, up->ptr);  in collapse_unr()
662 			up->ptr = uh;  in collapse_unr()
664 			delete_unr(uh, up->ptr);  in collapse_unr()
674 		TAILQ_REMOVE(&uh->head, up, list);  in collapse_unr()
675 		delete_unr(uh, up);  in collapse_unr()
684 			TAILQ_REMOVE(&uh->head, upp, list);  in collapse_unr()
685 			delete_unr(uh, upp);  in collapse_unr()
690 			TAILQ_REMOVE(&uh->head, upp, list);  in collapse_unr()
691 			delete_unr(uh, upp);  in collapse_unr()
696 	upp = TAILQ_FIRST(&uh->head);  in collapse_unr()
697 	if (upp != NULL && upp->ptr == uh) {  in collapse_unr()
698 		uh->first += upp->len;  in collapse_unr()
699 		TAILQ_REMOVE(&uh->head, upp, list);  in collapse_unr()
700 		delete_unr(uh, upp);  in collapse_unr()
706 	upp = TAILQ_LAST(&uh->head, unrhd);  in collapse_unr()
708 		uh->last += upp->len;  in collapse_unr()
709 		TAILQ_REMOVE(&uh->head, upp, list);  in collapse_unr()
710 		delete_unr(uh, upp);  in collapse_unr()
716 	while (optimize_unr(uh))  in collapse_unr()
724 alloc_unrl(struct unrhdr *uh)  in alloc_unrl()  argument
731 	if (uh->mtx != NULL)  in alloc_unrl()
732 		mtx_assert(uh->mtx, MA_OWNED);  in alloc_unrl()
733 	check_unrhdr(uh, __LINE__);  in alloc_unrl()
734 	x = uh->low + uh->first;  in alloc_unrl()
736 	up = TAILQ_FIRST(&uh->head);  in alloc_unrl()
741 	if (up == NULL && uh->last > 0) {  in alloc_unrl()
742 		uh->first++;  in alloc_unrl()
743 		uh->last--;  in alloc_unrl()
744 		uh->busy++;  in alloc_unrl()
755 	KASSERT(up->ptr != uh, ("UNR first element is allocated"));  in alloc_unrl()
758 		uh->first++;  in alloc_unrl()
767 	uh->busy++;  in alloc_unrl()
768 	collapse_unr(uh, up);  in alloc_unrl()
773 alloc_unr(struct unrhdr *uh)  in alloc_unr()  argument
777 	if (uh->mtx != NULL)  in alloc_unr()
778 		mtx_lock(uh->mtx);  in alloc_unr()
779 	i = alloc_unrl(uh);  in alloc_unr()
780 	clean_unrhdrl(uh);  in alloc_unr()
781 	if (uh->mtx != NULL)  in alloc_unr()
782 		mtx_unlock(uh->mtx);  in alloc_unr()
787 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)  in alloc_unr_specificl()  argument
793 	if (uh->mtx != NULL)  in alloc_unr_specificl()
794 		mtx_assert(uh->mtx, MA_OWNED);  in alloc_unr_specificl()
796 	if (item < uh->low + uh->first || item > uh->high)  in alloc_unr_specificl()
799 	up = TAILQ_FIRST(&uh->head);  in alloc_unr_specificl()
801 	if (up == NULL && item - uh->low == uh->first) {  in alloc_unr_specificl()
802 		uh->first++;  in alloc_unr_specificl()
803 		uh->last--;  in alloc_unr_specificl()
804 		uh->busy++;  in alloc_unr_specificl()
805 		check_unrhdr(uh, __LINE__);  in alloc_unr_specificl()
809 	i = item - uh->low - uh->first;  in alloc_unr_specificl()
812 		up = new_unr(uh, p1, p2);  in alloc_unr_specificl()
815 		TAILQ_INSERT_TAIL(&uh->head, up, list);  in alloc_unr_specificl()
816 		up = new_unr(uh, p1, p2);  in alloc_unr_specificl()
817 		up->ptr = uh;  in alloc_unr_specificl()
819 		TAILQ_INSERT_TAIL(&uh->head, up, list);  in alloc_unr_specificl()
820 		uh->last = uh->high - uh->low - i;  in alloc_unr_specificl()
821 		uh->busy++;  in alloc_unr_specificl()
822 		check_unrhdr(uh, __LINE__);  in alloc_unr_specificl()
826 		TAILQ_FOREACH(up, &uh->head, list) {  in alloc_unr_specificl()
835 			up = new_unr(uh, p1, p2);  in alloc_unr_specificl()
838 			TAILQ_INSERT_TAIL(&uh->head, up, list);  in alloc_unr_specificl()
840 		up = new_unr(uh, p1, p2);  in alloc_unr_specificl()
841 		up->ptr = uh;  in alloc_unr_specificl()
843 		TAILQ_INSERT_TAIL(&uh->head, up, list);  in alloc_unr_specificl()
847 	if (is_bitmap(uh, up)) {  in alloc_unr_specificl()
854 	} else if (up->ptr == uh)  in alloc_unr_specificl()
863 		upn = new_unr(uh, p1, p2);  in alloc_unr_specificl()
866 		TAILQ_INSERT_AFTER(&uh->head, up, upn, list);  in alloc_unr_specificl()
871 		upn = new_unr(uh, p1, p2);  in alloc_unr_specificl()
877 	up->ptr = uh;  in alloc_unr_specificl()
880 	last = uh->high - uh->low - (item - uh->low);  in alloc_unr_specificl()
881 	if (uh->last > last)  in alloc_unr_specificl()
882 		uh->last = last;  in alloc_unr_specificl()
883 	uh->busy++;  in alloc_unr_specificl()
884 	collapse_unr(uh, up);  in alloc_unr_specificl()
885 	check_unrhdr(uh, __LINE__);  in alloc_unr_specificl()
890 alloc_unr_specific(struct unrhdr *uh, u_int item)  in alloc_unr_specific()  argument
900 	if (uh->mtx != NULL)  in alloc_unr_specific()
901 		mtx_lock(uh->mtx);  in alloc_unr_specific()
902 	i = alloc_unr_specificl(uh, item, &p1, &p2);  in alloc_unr_specific()
903 	if (uh->mtx != NULL)  in alloc_unr_specific()
904 		mtx_unlock(uh->mtx);  in alloc_unr_specific()
920 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)  in free_unrl()  argument
926 	KASSERT(item >= uh->low && item <= uh->high,  in free_unrl()
928 	     item, uh->low, uh->high));  in free_unrl()
929 	check_unrhdr(uh, __LINE__);  in free_unrl()
930 	item -= uh->low;  in free_unrl()
931 	upp = TAILQ_FIRST(&uh->head);  in free_unrl()
935 	if (item + 1 == uh->first && upp == NULL) {  in free_unrl()
936 		uh->last++;  in free_unrl()
937 		uh->first--;  in free_unrl()
938 		uh->busy--;  in free_unrl()
939 		check_unrhdr(uh, __LINE__);  in free_unrl()
946 	if (item < uh->first) {  in free_unrl()
947 		up = new_unr(uh, p1, p2);  in free_unrl()
948 		up->ptr = uh;  in free_unrl()
949 		up->len = uh->first - item;  in free_unrl()
950 		TAILQ_INSERT_HEAD(&uh->head, up, list);  in free_unrl()
951 		uh->first -= up->len;  in free_unrl()
954 	item -= uh->first;  in free_unrl()
957 	TAILQ_FOREACH(up, &uh->head, list) {  in free_unrl()
964 	if (is_bitmap(uh, up)) {  in free_unrl()
970 		uh->busy--;  in free_unrl()
971 		collapse_unr(uh, up);  in free_unrl()
975 	KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));  in free_unrl()
980 		uh->busy--;  in free_unrl()
981 		collapse_unr(uh, up);  in free_unrl()
990 		uh->busy--;  in free_unrl()
991 		collapse_unr(uh, up);  in free_unrl()
1000 		uh->busy--;  in free_unrl()
1001 		collapse_unr(uh, up);  in free_unrl()
1008 		upp = new_unr(uh, p1, p2);  in free_unrl()
1009 		upp->ptr = uh;  in free_unrl()
1011 		TAILQ_INSERT_AFTER(&uh->head, up, upp, list);  in free_unrl()
1016 		upp = new_unr(uh, p1, p2);  in free_unrl()
1018 		upp->ptr = uh;  in free_unrl()
1023 	uh->busy--;  in free_unrl()
1024 	collapse_unr(uh, up);  in free_unrl()
1028 free_unr(struct unrhdr *uh, u_int item)  in free_unr()  argument
1035 	if (uh->mtx != NULL)  in free_unr()
1036 		mtx_lock(uh->mtx);  in free_unr()
1037 	free_unrl(uh, item, &p1, &p2);  in free_unr()
1038 	clean_unrhdrl(uh);  in free_unr()
1039 	if (uh->mtx != NULL)  in free_unr()
1040 		mtx_unlock(uh->mtx);  in free_unr()
1061 print_unr(struct unrhdr *uh, struct unr *up)  in print_unr()  argument
1069 	else if (up->ptr == uh)  in print_unr()
1085 print_unrhdr(struct unrhdr *uh)  in print_unrhdr()  argument
1092 	    uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);  in print_unrhdr()
1093 	x = uh->low + uh->first;  in print_unrhdr()
1094 	TAILQ_FOREACH(up, &uh->head, list) {  in print_unrhdr()
1096 		print_unr(uh, up);  in print_unrhdr()
1097 		if (up->ptr == NULL || up->ptr == uh)  in print_unrhdr()
1121 	    iter, iter->uh, iter->ipos, iter->upos, iter->upos_first_item);  in print_unrhdr_iter()
1146 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])  in test_alloc_unr()  argument
1152 		free_unr(uh, i);  in test_alloc_unr()
1156 		j = alloc_unr(uh);  in test_alloc_unr()
1166 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])  in test_alloc_unr_specific()  argument
1170 	j = alloc_unr_specific(uh, i);  in test_alloc_unr_specific()
1174 		free_unr(uh, i);  in test_alloc_unr_specific()
1192 test_iter_fill(int *vals, struct unrhdr *uh, int i, int v, int *res)  in test_iter_fill()  argument
1197 	x = alloc_unr_specific(uh, v);  in test_iter_fill()
1207 	struct unrhdr *uh;  in test_iter()  local
1213 	uh = new_unrhdr(TBASE, INT_MAX, NULL);  in test_iter()
1216 		x = alloc_unr_specific(uh, i + TBASE);  in test_iter()
1235 		test_iter_fill(vals, uh, i, v, &res);  in test_iter()
1238 			test_iter_fill(vals, uh, i, v, &res);  in test_iter()
1242 	ihandle = create_iter_unr(uh);  in test_iter()
1249 					print_unrhdr(uh);  in test_iter()
1258 	clean_unrhdr(uh);  in test_iter()
1259 	clear_unrhdr(uh);  in test_iter()
1260 	delete_unrhdr(uh);  in test_iter()
1273 	struct unrhdr *uh;  in main()  local
1313 	uh = new_unrhdr(0, count - 1, NULL);  in main()
1314 	print_unrhdr(uh);  in main()
1331 			test_alloc_unr(uh, i, a);  in main()
1333 			test_alloc_unr_specific(uh, i, a);  in main()
1336 			print_unrhdr(uh);  in main()
1337 		check_unrhdr(uh, __LINE__);  in main()
1343 				print_unrhdr(uh);  in main()
1345 			free_unr(uh, i);  in main()
1348 	print_unrhdr(uh);  in main()
1349 	delete_unrhdr(uh);  in main()