uyota 匠の一手

/***************************************************************************
 *   Copyright (C) 2007 by Yoshihiro Ota
 *   ota@j.email.ne.jp
 *                                                                         
 *   This program is free software; you can redistribute it and/or modify  
 *   it under the terms of the GNU General Public License as published by  
 *   the Free Software Foundation; either version 2 of the License, or     
 *   (at your option) any later version.                                   
 *                                                                         
 *   This program is distributed in the hope that it will be useful,       
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         
 *   GNU General Public License for more details.                          
 *                                                                         
 *   You should have received a copy of the GNU General Public License     
 *   along with this program; if not, write to the                         
 *   Free Software Foundation, Inc.,                                       
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             
 *
 ***************************************************************************/
#include "binsert.h"

/*

Binary search INSERTion takes the same arguments as qsort except that
all the members from the 1st to (nmemb - 1)th are already sorted.

binsert requires all elements be sorted except the last one.  It finds
where the last element belongs by the binary search algorithm
based on 'compar' function.  Once it finds the location, it shifts
all of the ones come after and inserts the last element in the spot.

The interface is the same as qsort to make transition easy. 
It is most convenient when searches are being performed while
new items are added from time to time.
The order of qsort is N * log(N); that of binsert is log(N) when all
except the last one is sorted.

This implementation of binsert maintains elements with the same key in
the order as input.  For example, let's assume "33", "35", and "32" are
inserted where the only first character is the key.  All of these
three elements has the same priority.  Therefore, the result is
"33", "35", "32".

*/

void binsert(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *))
{
        char *ptr = base;
        char item[size];
        int left = 0, right = nmemb - 2, middle = 0;

        memmove(item, &ptr[(nmemb - 1) * size], size); /* save the new entry */

        while(left <= right)
        {
                middle = (left + right) / 2;
                if(compar(&ptr[middle * size], item) <= 0)
                        left = middle + 1;
                else
                        right = middle - 1;
        }

        memmove(&ptr[(left + 1) * size], /* shift by one element */
                &ptr[left * size],
                (nmemb - left - 1) * size);
        memmove(&ptr[left * size], item, size); /* copy the new one */
}