• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
db_Zero(double * d,long nr)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*/
db_LeanPartitionOnPivot(double pivot,double * dest,const double * source,long first,long last,long * first_equal,long * last_equal)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 
db_LeanQuickSelect(const double * s,long nr_elements,long pos,double * temp)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 
db_AlignPointer_f(float * p,unsigned long nr_bytes)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 
db_AlignPointer_s(short * p,unsigned long nr_bytes)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