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