perftests/panorama/feature_stab/db_vlvm/db_utilities_indexing.cpp

/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/* $Id: db_utilities_indexing.cpp,v 1.3 2011/06/17 14:03:31 mbansal Exp $ */

#include "db_utilities_indexing.h"
#include "db_utilities.h"



/*****************************************************************
*    Lean and mean begins here                                   *
*****************************************************************/

void db_Zero(double *d,long nr)
{
    long i;
    for(i=0;i<nr;i++) d[i]=0.0;
}

/*This routine breaks number in source into values smaller and larger than
a pivot element. Values equal to the pivot are ignored*/
void db_LeanPartitionOnPivot(double pivot,double *dest,const double *source,long first,long last,long *first_equal,long *last_equal)
{
    double temp;
    const double *s_point;
    const double *s_top;
    double *d_bottom;
    double *d_top;

    s_point=source+first;
    s_top=source+last;
    d_bottom=dest+first;
    d_top=dest+last;

    for(;s_point<=s_top;)
    {
        temp= *(s_point++);
        if(temp<pivot) *(d_bottom++)=temp;
        else if(temp>pivot) *(d_top--)=temp;
    }
    *first_equal=d_bottom-dest;
    *last_equal=d_top-dest;
}

double db_LeanQuickSelect(const double *s,long nr_elements,long pos,double *temp)
{
  long first=0;
  long last=nr_elements-1;
  double pivot;
  long first_equal,last_equal;
  double *tempA;
  double *tempB;
  double *tempC;
  const double *source;
  double *dest;

  tempA=temp;
  tempB=temp+nr_elements;
  source=s;
  dest=tempA;

  for(;last-first>2;)
  {
      pivot=db_TripleMedian(source[first],source[last],source[(first+last)/2]);
      db_LeanPartitionOnPivot(pivot,dest,source,first,last,&first_equal,&last_equal);

      if(first_equal>pos) last=first_equal-1;
      else if(last_equal<pos) first=last_equal+1;
      else
      {
        return(pivot);
      }

      /*Swap pointers*/
      tempC=tempA;
      tempA=tempB;
      tempB=tempC;
      source=tempB;
      dest=tempA;
  }
  pivot=db_TripleMedian(source[first],source[last],source[(first+last)/2]);

  return(pivot);
}

float* db_AlignPointer_f(float *p,unsigned long nr_bytes)
{
    float *ap;
    unsigned long m;

    m=((unsigned long)p)%nr_bytes;
    if(m) ap=(float*) (((unsigned long)p)-m+nr_bytes);
    else ap=p;
    return(ap);
}

short* db_AlignPointer_s(short *p,unsigned long nr_bytes)
{
    short *ap;
    unsigned long m;

    m=((unsigned long)p)%nr_bytes;
    if(m) ap=(short*) (((unsigned long)p)-m+nr_bytes);
    else ap=p;
    return(ap);
}