FreeBSD/sys/kern/subr_unit.c
/*
 * Look for sequence of items which can be combined into a bitmap, if
 * multiple are present, take the one which saves most memory.
 * 
 * Return (1) if a sequence was found to indicate that another call
 * might be able to do more.  Return (0) if we found no suitable sequence.
 *
 * NB: called from alloc_unr(), no new memory allocation allowed.
 */
Look for sequence of items which can be combined into a bitmap, if
multiple are present, take the one which saves most memory.

Return (1) if a sequence was found to indicate that another call
might be able to do more.  Return (0) if we found no suitable sequence.

called from alloc_unr(), no new memory allocation allowed.
Look for sequence of items which can be combined into a bitmap if multiple are present take the one which saves most memory . Return ( 1 ) if a sequence was found to indicate that another call might be able to do more . Return ( 0 ) if we found no suitable sequence . called from alloc_unr () no new memory allocation allowed .
static int
optimize_unr(struct unrhdr *uh)
{
	struct unr *up, *uf, *us;
	struct unrb *ub, *ubf;
	u_int a, l, ba;
	us = NULL;
	ba = 0;
	TAILQ_FOREACH(uf, &uh->head, list) {
		if (uf->len >= NBITS)
			continue;
		a = 1;
		if (is_bitmap(uh, uf))
			a++;
		l = uf->len;
		up = uf;
		while (1) {
			up = TAILQ_NEXT(up, list);
			if (up == NULL)
				break;
			if ((up->len + l) > NBITS)
				break;
			a++;
			if (is_bitmap(uh, up))
				a++;
			l += up->len;
		}
		if (a > ba) {
			ba = a;
			us = uf;
		}
	}
	if (ba < 3)
		return (0);
	if (!is_bitmap(uh, us)) {
		uf = TAILQ_NEXT(us, list);
		TAILQ_REMOVE(&uh->head, us, list);
		a = us->len;
		l = us->ptr == uh ? 1 : 0;
		ub = (void *)us;
		bit_nclear(ub->map, 0, NBITS - 1);
		if (l)
			bit_nset(ub->map, 0, a);
		if (!is_bitmap(uh, uf)) {
			if (uf->ptr == NULL)
				bit_nclear(ub->map, a, a + uf->len - 1);
			else
				bit_nset(ub->map, a, a + uf->len - 1);
			uf->ptr = ub;
			uf->len += a;
			us = uf;
		} else {
			ubf = uf->ptr;
			for (l = 0; l < uf->len; l++, a++) {
				if (bit_test(ubf->map, l))
					bit_set(ub->map, a);
				else
					bit_clear(ub->map, a);
			}
			uf->len = a;
			delete_unr(uh, uf->ptr);
			uf->ptr = ub;
			us = uf;
		}
	}
	ub = us->ptr;
	while (1) {
		uf = TAILQ_NEXT(us, list);
		if (uf == NULL)
			return (1);
		if (uf->len + us->len > NBITS)
			return (1);
		if (uf->ptr == NULL) {
			bit_nclear(ub->map, us->len, us->len + uf->len - 1);
			us->len += uf->len;
			TAILQ_REMOVE(&uh->head, uf, list);
			delete_unr(uh, uf);
		} else if (uf->ptr == uh) {
			bit_nset(ub->map, us->len, us->len + uf->len - 1);
			us->len += uf->len;
			TAILQ_REMOVE(&uh->head, uf, list);
			delete_unr(uh, uf);
		} else {
			ubf = uf->ptr;
			for (l = 0; l < uf->len; l++, us->len++) {
				if (bit_test(ubf->map, l))
					bit_set(ub->map, us->len);
				else
					bit_clear(ub->map, us->len);
			}
			TAILQ_REMOVE(&uh->head, uf, list);
			delete_unr(uh, ubf);
			delete_unr(uh, uf);
		}
	}
}
static int optimize_unr ( struct unrhdr * uh ) { struct unr * up , * uf , * us ; struct unrb * ub , * ubf ; u_int a , l , ba ; us = NULL ; ba = 0 ; TAILQ_FOREACH ( uf , & uh -> head , list ) { if ( uf -> len >= NBITS ) continue ; a = 1 ; if ( is_bitmap ( uh , uf ) ) a ++ ; l = uf -> len ; up = uf ; while ( 1 ) { up = TAILQ_NEXT ( up , list ) ; if ( up == NULL ) break ; if ( ( up -> len + l ) > NBITS ) break ; a ++ ; if ( is_bitmap ( uh , up ) ) a ++ ; l += up -> len ; } if ( a > ba ) { ba = a ; us = uf ; } } if ( ba < 3 ) return ( 0 ) ; if ( ! is_bitmap ( uh , us ) ) { uf = TAILQ_NEXT ( us , list ) ; TAILQ_REMOVE ( & uh -> head , us , list ) ; a = us -> len ; l = us -> ptr == uh ? 1 : 0 ; ub = ( void * ) us ; bit_nclear ( ub -> map , 0 , NBITS - 1 ) ; if ( l ) bit_nset ( ub -> map , 0 , a ) ; if ( ! is_bitmap ( uh , uf ) ) { if ( uf -> ptr == NULL ) bit_nclear ( ub -> map , a , a + uf -> len - 1 ) ; else bit_nset ( ub -> map , a , a + uf -> len - 1 ) ; uf -> ptr = ub ; uf -> len += a ; us = uf ; } else { ubf = uf -> ptr ; for ( l = 0 ; l < uf -> len ; l ++ , a ++ ) { if ( bit_test ( ubf -> map , l ) ) bit_set ( ub -> map , a ) ; else bit_clear ( ub -> map , a ) ; } uf -> len = a ; delete_unr ( uh , uf -> ptr ) ; uf -> ptr = ub ; us = uf ; } } ub = us -> ptr ; while ( 1 ) { uf = TAILQ_NEXT ( us , list ) ; if ( uf == NULL ) return ( 1 ) ; if ( uf -> len + us -> len > NBITS ) return ( 1 ) ; if ( uf -> ptr == NULL ) { bit_nclear ( ub -> map , us -> len , us -> len + uf -> len - 1 ) ; us -> len += uf -> len ; TAILQ_REMOVE ( & uh -> head , uf , list ) ; delete_unr ( uh , uf ) ; } else if ( uf -> ptr == uh ) { bit_nset ( ub -> map , us -> len , us -> len + uf -> len - 1 ) ; us -> len += uf -> len ; TAILQ_REMOVE ( & uh -> head , uf , list ) ; delete_unr ( uh , uf ) ; } else { ubf = uf -> ptr ; for ( l = 0 ; l < uf -> len ; l ++ , us -> len ++ ) { if ( bit_test ( ubf -> map , l ) ) bit_set ( ub -> map , us -> len ) ; else bit_clear ( ub -> map , us -> len ) ; } TAILQ_REMOVE ( & uh -> head , uf , list ) ; delete_unr ( uh , ubf ) ; delete_unr ( uh , uf ) ; } } }
Look for sequence of items which can be combined into a bitmap, if
 multiple are present, take the one which saves most memory.
Look for sequence of items which can be combined into a bitmap if multiple are present take the one which saves most memory .
/*
	 * Look for the run of items (if any) which when collapsed into
	 * a bitmap would save most memory.
	 */ /*
	 * If the first element is not a bitmap, make it one.
	 * Trying to do so without allocating more memory complicates things
	 * a bit
	 */