[dovecot-cvs] dovecot/src/lib Makefile.am, 1.56, 1.57 bsearch-insert-pos.c, NONE, 1.1 bsearch-insert-pos.h, NONE, 1.1

[cras at dovecot.org]

Update of /var/lib/cvs/dovecot/src/lib
In directory talvi:/tmp/cvs-serv29545

Modified Files:
	Makefile.am 
Added Files:
	bsearch-insert-pos.c bsearch-insert-pos.h 
Log Message:
Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
returns the position where it would be inserted.



Index: Makefile.am
===================================================================
RCS file: /var/lib/cvs/dovecot/src/lib/Makefile.am,v
retrieving revision 1.56
retrieving revision 1.57
diff -u -d -r1.56 -r1.57
--- Makefile.am	14 Dec 2005 18:51:52 -0000	1.56
+++ Makefile.am	21 Dec 2005 17:47:25 -0000	1.57
@@ -2,6 +2,7 @@
 
 liblib_a_SOURCES = \
 	base64.c \
+	bsearch-insert-pos.c \
 	buffer.c \
 	compat.c \
 	data-stack.c \
@@ -81,6 +82,7 @@
 	array.h \
 	array-decl.h \
 	base64.h \
+	bsearch-insert-pos.h \
 	buffer.h \
 	compat.h \
 	data-stack.h \

--- NEW FILE: bsearch-insert-pos.c ---
/* Copyright (C) 2005 Timo Sirainen */

#include "lib.h"
#include "bsearch-insert-pos.h"

void *bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
			 size_t size, int (*cmp)(const void *, const void *))
{
	const void *p;
	unsigned int idx, left_idx, right_idx;
	int ret;

	/* we're probably appending it, check */
	idx = 0; left_idx = 0; right_idx = nmemb;
	while (left_idx < right_idx) {
		idx = (left_idx + right_idx) / 2;

		p = CONST_PTR_OFFSET(base, idx * size);
		ret = cmp(key, p);
		if (ret > 0)
			left_idx = idx+1;
		else if (ret < 0)
			right_idx = idx;
		else
			return (void *)p;
	}

	p = CONST_PTR_OFFSET(base, idx * size);
	if (idx < nmemb && cmp(key, p) > 0)
		p = CONST_PTR_OFFSET(p, size);
	return (void *)p;
}


--- NEW FILE: bsearch-insert-pos.h ---
#ifndef __BSEARCH_INSERT_POS
#define __BSEARCH_INSERT_POS

/* If key is found, returns the pointer to it. If not, returns a pointer to
   where it should be inserted. */
void *bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
			 size_t size, int (*cmp)(const void *, const void *));

#endif