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
28void 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
35a pivot element. Values equal to the pivot are ignored*/
36void 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
59double 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
100float* 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
111short* 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