blob: 1cc64ead993b574182d511738902e97910b35d8a [file] [log] [blame]
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you 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
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
#ifndef _HLLARRAY_HPP_
#define _HLLARRAY_HPP_
#include "HllSketchImpl.hpp"
#include "HllUtil.hpp"
namespace datasketches {
template<typename A>
class AuxHashMap;
template<typename A = std::allocator<char>>
class HllArray : public HllSketchImpl<A> {
explicit HllArray(int lgConfigK, target_hll_type tgtHllType, bool startFullSize);
explicit HllArray(const HllArray<A>& that);
static HllArray* newHll(const void* bytes, size_t len);
static HllArray* newHll(std::istream& is);
virtual vector_u8<A> serialize(bool compact, unsigned header_size_bytes) const;
virtual void serialize(std::ostream& os, bool compact) const;
virtual ~HllArray();
virtual std::function<void(HllSketchImpl<A>*)> get_deleter() const = 0;
virtual HllArray* copy() const = 0;
virtual HllArray* copyAs(target_hll_type tgtHllType) const;
virtual HllSketchImpl<A>* couponUpdate(int coupon) = 0;
virtual double getEstimate() const;
virtual double getCompositeEstimate() const;
virtual double getLowerBound(int numStdDev) const;
virtual double getUpperBound(int numStdDev) const;
inline void addToHipAccum(double delta);
inline void decNumAtCurMin();
inline int getCurMin() const;
inline int getNumAtCurMin() const;
inline double getHipAccum() const;
virtual int getHllByteArrBytes() const = 0;
virtual int getUpdatableSerializationBytes() const;
virtual int getCompactSerializationBytes() const;
virtual bool isOutOfOrderFlag() const;
virtual bool isEmpty() const;
virtual bool isCompact() const;
virtual void putOutOfOrderFlag(bool flag);
inline double getKxQ0() const;
inline double getKxQ1() const;
virtual int getMemDataStart() const;
virtual int getPreInts() const;
void putCurMin(int curMin);
void putHipAccum(double hipAccum);
inline void putKxQ0(double kxq0);
inline void putKxQ1(double kxq1);
void putNumAtCurMin(int numAtCurMin);
static int hllArrBytes(target_hll_type tgtHllType, int lgConfigK);
static int hll4ArrBytes(int lgConfigK);
static int hll6ArrBytes(int lgConfigK);
static int hll8ArrBytes(int lgConfigK);
virtual AuxHashMap<A>* getAuxHashMap() const;
class const_iterator;
virtual const_iterator begin(bool all = false) const;
virtual const_iterator end() const;
void hipAndKxQIncrementalUpdate(uint8_t oldValue, uint8_t newValue);
double getHllBitMapEstimate(int lgConfigK, int curMin, int numAtCurMin) const;
double getHllRawEstimate(int lgConfigK, double kxqSum) const;
double hipAccum;
double kxq0;
double kxq1;
uint8_t* hllByteArr; //init by sub-classes
int curMin; //always zero for Hll6 and Hll8, only tracked by Hll4Array
int numAtCurMin; //interpreted as num zeros when curMin == 0
bool oooFlag; //Out-Of-Order Flag
friend class HllSketchImplFactory<A>;
template<typename A>
class HllArray<A>::const_iterator: public std::iterator<std::input_iterator_tag, uint32_t> {
const_iterator(const uint8_t* array, size_t array_slze, size_t index, target_hll_type hll_type, const AuxHashMap<A>* exceptions, uint8_t offset, bool all);
//const_iterator(const uint8_t* array, size_t array_slze, size_t index, target_hll_type hll_type, const AuxHashMap<A>* exceptions, uint8_t offset);
const_iterator& operator++();
bool operator!=(const const_iterator& other) const;
uint32_t operator*() const;
const uint8_t* array;
size_t array_size;
size_t index;
target_hll_type hll_type;
const AuxHashMap<A>* exceptions;
uint8_t offset;
bool all;
uint8_t value; // cached value to avoid computing in operator++ and in operator*()
static inline uint8_t get_value(const uint8_t* array, size_t index, target_hll_type hll_type, const AuxHashMap<A>* exceptions, uint8_t offset);
#endif /* _HLLARRAY_HPP_ */