Home | History | Annotate | Download | only in db_vlvm 
      1 /*
      2  * Copyright (C) 2011 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 /* $Id: db_utilities_indexing.cpp,v 1.3 2011/06/17 14:03:31 mbansal Exp $ */
     18 
     19 #include "db_utilities_indexing.h"
     20 #include "db_utilities.h"
     21 
     22 
     23 
     24 /*****************************************************************
     25 *    Lean and mean begins here                                   *
     26 *****************************************************************/
     27 
     28 void db_Zero(double *d,long nr)
     29 {
     30     long i;
     31     for(i=0;i<nr;i++) d[i]=0.0;
     32 }
     33 
     34 /*This routine breaks number in source into values smaller and larger than
     35 a pivot element. Values equal to the pivot are ignored*/
     36 void db_LeanPartitionOnPivot(double pivot,double *dest,const double *source,long first,long last,long *first_equal,long *last_equal)
     37 {
     38     double temp;
     39     const double *s_point;
     40     const double *s_top;
     41     double *d_bottom;
     42     double *d_top;
     43 
     44     s_point=source+first;
     45     s_top=source+last;
     46     d_bottom=dest+first;
     47     d_top=dest+last;
     48 
     49     for(;s_point<=s_top;)
     50     {
     51         temp= *(s_point++);
     52         if(temp<pivot) *(d_bottom++)=temp;
     53         else if(temp>pivot) *(d_top--)=temp;
     54     }
     55     *first_equal=d_bottom-dest;
     56     *last_equal=d_top-dest;
     57 }
     58 
     59 double db_LeanQuickSelect(const double *s,long nr_elements,long pos,double *temp)
     60 {
     61   long first=0;
     62   long last=nr_elements-1;
     63   double pivot;
     64   long first_equal,last_equal;
     65   double *tempA;
     66   double *tempB;
     67   double *tempC;
     68   const double *source;
     69   double *dest;
     70 
     71   tempA=temp;
     72   tempB=temp+nr_elements;
     73   source=s;
     74   dest=tempA;
     75 
     76   for(;last-first>2;)
     77   {
     78       pivot=db_TripleMedian(source[first],source[last],source[(first+last)/2]);
     79       db_LeanPartitionOnPivot(pivot,dest,source,first,last,&first_equal,&last_equal);
     80 
     81       if(first_equal>pos) last=first_equal-1;
     82       else if(last_equal<pos) first=last_equal+1;
     83       else
     84       {
     85         return(pivot);
     86       }
     87 
     88       /*Swap pointers*/
     89       tempC=tempA;
     90       tempA=tempB;
     91       tempB=tempC;
     92       source=tempB;
     93       dest=tempA;
     94   }
     95   pivot=db_TripleMedian(source[first],source[last],source[(first+last)/2]);
     96 
     97   return(pivot);
     98 }
     99 
    100 float* db_AlignPointer_f(float *p,unsigned long nr_bytes)
    101 {
    102     float *ap;
    103     unsigned long m;
    104 
    105     m=((unsigned long)p)%nr_bytes;
    106     if(m) ap=(float*) (((unsigned long)p)-m+nr_bytes);
    107     else ap=p;
    108     return(ap);
    109 }
    110 
    111 short* db_AlignPointer_s(short *p,unsigned long nr_bytes)
    112 {
    113     short *ap;
    114     unsigned long m;
    115 
    116     m=((unsigned long)p)%nr_bytes;
    117     if(m) ap=(short*) (((unsigned long)p)-m+nr_bytes);
    118     else ap=p;
    119     return(ap);
    120 }
    121