AVA_Sort function in slapd/dn.c

[Bret Lambert <blambert@gsipt.net>]

Doing some lint(1) sweeps (some of which ando@ has committed), I got a
message stating that the end of the loop in this function was never
reached. Looking into it, I think that the code as it currently is is
incorrect:

static void
AVA_Sort( LDAPRDN rdn, int iAVA )
{
	int		i;
	LDAPAVA		*ava_in = rdn[ iAVA ];

	assert( rdn != NULL );
	assert( ava_in != NULL );
	
	for ( i = 0; i < iAVA; i++ ) {
		LDAPAVA		*ava = rdn[ i ];
		int		a, j;

		assert( ava != NULL );

		a = strcmp( ava_in->la_attr.bv_val, ava->la_attr.bv_val );

		if ( a > 0 ) {
			break;
		}

		while ( a == 0 ) {
			int		v, d;

			d = ava_in->la_value.bv_len - ava->la_value.bv_len;

			v = memcmp( ava_in->la_value.bv_val, 
					ava->la_value.bv_val,
					d <= 0 ? ava_in->la_value.bv_len 
						: ava->la_value.bv_len );

			if ( v == 0 && d != 0 ) {
				v = d;
			}

			if ( v <= 0 ) {
				/* 
				 * got it!
				 */
				break;
			}

			if ( ++i == iAVA ) {
				/*
				 * already sorted
				 */
				return;
			}

			ava = rdn[ i ];
			a = strcmp( ava_in->la_attr.bv_val, 
					ava->la_attr.bv_val );
		}

		/*
		 * move ahead
		 */
		for ( j = iAVA; j > i; j-- ) {
			rdn[ j ] = rdn[ j - 1 ];
		}
		rdn[ i ] = ava_in;

		return;
	}
}

It's that unconditional return at the end of the for() loop that caused lint(1)
to hiccup (also, insofar as I can see, invalidates the entire function). It's
easy to see that the intent of the code is to take the element indicated by iAVA
and compare it to all previous items in rdn[]. However, all it does is compare it
to the first item, and it does the correct thing in that case, but then terminates.

So, I whipped up what looks to me to be a better, functioning, and more legible
chunk of code. Please flame or reward with cash as appropriate:

static void
AVA_Sort( LDAPRDN rdn, int iAVA )
{
	int		i = 0;
	LDAPAVA		*ava_in = rdn[ iAVA ];

	assert( rdn != NULL );
	assert( ava_in != NULL );
	
	LDAPAVA		*ava = rdn[ i ];
	int		a, j;

	assert( ava != NULL );

	while ( ( a = strcmp( ava_in->la_attr.bv_val, ava->la_attr.bv_val ) ) < 0 ) {
		ava = rdn[ ++i ];
	}

	if ( a > 0 ) {
		return;
	}

	do {
		int		v, d;

		d = ava_in->la_value.bv_len - ava->la_value.bv_len;

		v = memcmp( ava_in->la_value.bv_val, 
				ava->la_value.bv_val,
				min( ava_in->la_value.bv_len,
					ava->la_value.bv_len ) );

		if ( v < 0 || ( v == 0 && d <= 0 ) ) {
			/* 
			 * got it!
			 */
			break;
		}

		if ( ++i == iAVA ) {
			/*
			 * already sorted
			 */
			return;
		}
		ava = rdn[ i ];
	} while ( strcmp( ava_in->la_attr.bv_val, 
				ava->la_attr.bv_val ) == 0);

	/*
	 * move ahead
	 */
	for ( j = iAVA; j > i; j-- ) {
		rdn[ j ] = rdn[ j - 1 ];
	}
	rdn[ i ] = ava_in;
}