void MSHashTable::resize(unsigned size_)
{
  MSHashEntry **oldBuckets=bucket();
  unsigned oldSize=size();
  
  _size=computeSize(size_);
  _bucket=new MSHashEntry*[size()];
  unsigned i=size();
  MSHashEntry **p=bucket();
  while(i--) *p++=0;

  if (oldBuckets!=0)
   {
     for (unsigned j=0;j<oldSize;j++)
      {
        // we want to add them in reverse order of the chains, i.e. add them in the order that they
        // were originally added - latest additions are at the top of the bucket chain
	MSHashEntry *entry=oldBuckets[j];
	MSHashEntry *prev;
	while (entry!=0&&entry->next()!=0) entry=entry->next(); 
	while (entry!=0)
	 {
	   prev=entry->prev();
           entry->prev(0),entry->next(0);
	   addEntry(entry); // rehash and add to the new table
	   entry=prev;
	 }
	oldBuckets[j]=0;
      }
     delete [] oldBuckets;  
   }
}

// special add method for adding an entry back into the table i.e. rehashing it is
// useful for a hash table resize
void MSHashTable::addEntry(MSHashEntry *entry_)
{
  unsigned whichBucket=(entry_->stringKey()==0)?hash(entry_->key()):hash(entry_->stringKey());
  entry_->next(bucket(whichBucket));
  if (bucket(whichBucket)!=0) bucket(whichBucket)->prev(entry_);
  bucket(whichBucket,entry_);
}

void Dictionary::reorder_dictionary() {

  // Copy all the dictionary entries into a single master list.

  DictionaryEntry* master_list = NULL;
  for (int i = 0; i < table_size(); ++i) {
    DictionaryEntry* p = bucket(i);
    while (p != NULL) {
      DictionaryEntry* tmp;
      tmp = p->next();
      p->set_next(master_list);
      master_list = p;
      p = tmp;
    }
    set_entry(i, NULL);
  }

  // Add the dictionary entries back to the list in the correct buckets.
  while (master_list != NULL) {
    DictionaryEntry* p = master_list;
    master_list = master_list->next();
    p->set_next(NULL);
    Symbol* class_name = InstanceKlass::cast((Klass*)(p->klass()))->name();
    // Since the null class loader data isn't copied to the CDS archive,
    // compute the hash with NULL for loader data.
    unsigned int hash = compute_hash(class_name, NULL);
    int index = hash_to_index(hash);
    p->set_hash(hash);
    p->set_loader_data(NULL);   // loader_data isn't copied to CDS
    p->set_next(bucket(index));
    set_entry(index, p);
  }
}

MSHashEntry *MSHashTable::addElement(const char *key_,unsigned whichBucket_)
{
  MSHashEntry *entry=new MSHashEntry(key_);
  entry->next(bucket(whichBucket_));
  if (bucket(whichBucket_)) bucket(whichBucket_)->prev(entry);
  bucket(whichBucket_,entry);
  return entry;
}

  void *reallocate(size_t newsize, void *ptr, size_t size, const char *name=NULL, int ignore=0) {
    uint32_t b1 = bucket(newsize);
    uint32_t b2 = bucket(size);

    if (b1==b2 && b1!=maxbits) return ptr;

    void *ret = allocate(newsize, name);
    memcpy(ret, ptr, size<newsize?size:newsize);
    deallocate(ptr, size, name);
    return ret;
  }

void MSHashTable::init(unsigned size_)
{
  if (bucket()==0)
   {
     _size=computeSize(size_);
     _bucket=new MSHashEntry*[size()];
     unsigned i=size();
     MSHashEntry **p=bucket();
     while(i--) *p++=0;
   }
  else resize(size_);
}

MSBoolean MSHashTable::remove(const char *key_)
{
  unsigned whichBucket=hash(key_);  
  MSHashEntry *entry=searchBucketFor(bucket(whichBucket),key_);
  if (entry!=0)
   {
     if (bucket(whichBucket)==entry) bucket(whichBucket,entry->next());
     delete entry;
     return MSTrue;
   }  
  return MSFalse;
}

void Dictionary::verify() {
  guarantee(number_of_entries() >= 0, "Verify of system dictionary failed");

  int element_count = 0;
  for (int index = 0; index < table_size(); index++) {
    for (DictionaryEntry* probe = bucket(index);
                          probe != NULL;
                          probe = probe->next()) {
      Klass* e = probe->klass();
      ClassLoaderData* loader_data = probe->loader_data();
      guarantee(e->oop_is_instance(),
                              "Verify of system dictionary failed");
      // class loader must be present;  a null class loader is the
      // boostrap loader
      guarantee(loader_data != NULL || DumpSharedSpaces ||
                loader_data->class_loader() == NULL ||
                loader_data->class_loader()->is_instance(),
                "checking type of class_loader");
      e->verify();
      probe->verify_protection_domain_set();
      element_count++;
    }
  }
  guarantee(number_of_entries() == element_count,
            "Verify of system dictionary failed");
  debug_only(verify_lookup_length((double)number_of_entries() / table_size()));

  _pd_cache_table->verify();
}

void Dictionary::print() {
  ResourceMark rm;
  HandleMark   hm;

  tty->print_cr("Java system dictionary (table_size=%d, classes=%d)",
                 table_size(), number_of_entries());
  tty->print_cr("^ indicates that initiating loader is different from "
                "defining loader");

  for (int index = 0; index < table_size(); index++) {
    for (DictionaryEntry* probe = bucket(index);
                          probe != NULL;
                          probe = probe->next()) {
      if (Verbose) tty->print("%4d: ", index);
      Klass* e = probe->klass();
      ClassLoaderData* loader_data =  probe->loader_data();
      bool is_defining_class =
         (loader_data == InstanceKlass::cast(e)->class_loader_data());
      tty->print("%s%s", is_defining_class ? " " : "^",
                   e->external_name());

        tty->print(", loader ");
      loader_data->print_value();
      tty->cr();
    }
  }
  tty->cr();
  _pd_cache_table->print();
  tty->cr();
}

	std::vector<std::string> anagrams(std::vector<std::string> &strs) {
		
		std::map<int, std::vector<Bucket> > buckets;
		
		for (size_t i = 0; i < strs.size(); ++i) {
			std::vector<int> key = this->calcKey(strs[i]);
			int hash = this->calcHash(key);
			
			std::vector<Bucket> &bucket(buckets[hash]);
			bool ok = false;
			for (size_t j = 0; j < bucket.size(); ++j) {
				Bucket &bk(bucket[j]);
				if (ok = this->equal(bk.key, key)) {
					bk.val.push_back(strs[i]);
					break;
				}
			}
			if (!ok) {
				bucket.push_back(Bucket());
				bucket.back().key = key;
				bucket.back().val.push_back(strs[i]);
			}
		}
		
		std::vector<std::string> result;
		for (std::map<int, std::vector<Bucket> >::const_iterator iter = buckets.begin(); iter != buckets.end(); ++iter) {
			const std::vector<Bucket> &bucket(iter->second);
			for (size_t j = 0; j < bucket.size(); ++j) {
				const Bucket &bk(bucket[j]);
				if (bk.val.size() > 1) std::copy(bk.val.begin(), bk.val.end(), std::back_inserter(result));
			}
		}
		
		return (result);
	}

void
FileStorModifiedBucketsTest::modifiedBucketsSendNotifyBucketChange()
{
    BucketCheckerInjector bcj(*_node, *this);
    TestFileStorComponents c(*this, "modifiedBucketsSendNotifyBucketChange", bcj);
    setClusterState("storage:1 distributor:1");

    uint32_t numBuckets = 10;

    for (uint32_t i = 0; i < numBuckets; ++i) {
        document::BucketId bucket(16, i);
        createBucket(makeSpiBucket(bucket));
        c.sendPut(bucket, DocumentIndex(0), PutTimestamp(1000));
    }
    c.top.waitForMessages(numBuckets, MSG_WAIT_TIME);
    c.top.reset();

    modifyBuckets(0, numBuckets);
    c.top.waitForMessages(numBuckets, MSG_WAIT_TIME);

    for (uint32_t i = 0; i < 10; ++i) {
        assertIsNotifyCommandWithActiveBucket(*c.top.getReply(i));

        StorBucketDatabase::WrappedEntry entry(
                _node->getStorageBucketDatabase().get(
                        document::BucketId(16, i), "foo"));

        CPPUNIT_ASSERT(entry->info.isActive());
    }
}

static int
fset_locate (fset_t *dbs, mem_hash_t *mem, void *key, size_t *ref, size_t *tomb)
{
    size_t              k = dbs->key_length;
    for (int i = 1; *mem == EMPTY || *mem == TOMB; i++) {
        *mem = MurmurHash32(key, k, i);
    }
    size_t              h = home_loc (*mem);
    *tomb = NONE;
    dbs->lookups++;
    //Debug ("Locating key %zu,%zu with hash %u", ((size_t*)data)[0], ((size_t*)data)[1], mem);
    for (size_t rh = 0; rh <= 1000; rh++) {
        *ref = h & dbs->mask;
        size_t              line_begin = *ref & CACHE_LINE_MEM_MASK;
        size_t              line_end = line_begin + CACHE_LINE_MEM_SIZE;
        for (size_t i = 0; i < CACHE_LINE_MEM_SIZE; i++) {
            dbs->probes++;
            if (*memoized(dbs,*ref) == TOMB) {
                if (*tomb == NONE)
                    *tomb = *ref; // first found tombstone
            } else if (*memoized(dbs,*ref) == EMPTY) {
                return 0;
            } else if ( *mem == *memoized(dbs,*ref) &&
                        memcmp (key, bucket(dbs,dbs->data,*ref), k) == 0 ) {
                return 1;
            }
            *ref = (*ref+1 == line_end ? line_begin : *ref+1); // next in line
        }
        h = rehash (h, *mem);
    }
    return FSET_FULL;
}

    string frequencySort(string s) {
        int n = s.length();
        const int MAX_CHAR = 256;
        vector<int> freq(MAX_CHAR, 0);
        for(int i = 0 ; i < n; ++i) {
            freq[s[i]]++;
        }
#if 0
        // bucket sort
        vector<vector<int>> bucket(n + 1);
        for (int i = 0; i < MAX_CHAR; i++) {
            bucket[freq[i]].push_back(i);    
        }
        string result = "";
        for (int i = bucket.size() - 1; i > 0; i--) {
            for (auto ch : bucket[i]) {
                result += string(i, ch);    
            }
        }
#endif
        // auto compare = [] (pair<int, int> const& lhs, pair<int, int> const& rhs) -> bool const { return lhs.first < rhs.first; };
        // priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> Q(compare);
        priority_queue<pair<int, int>> Q;
        for(int i = 0 ; i < MAX_CHAR; ++i) {
            if(freq[i] > 0) {
                Q.push({freq[i], i});
            }
        }
        string result = "";
        while(!Q.empty()) {
            result += string(Q.top().first, Q.top().second);
            Q.pop();
        }
        return result;
    }

void check_uniform_int(Generator & gen, int iter)
{
  std::cout << "testing uniform_int(" << (gen.min)() << "," << (gen.max)() 
            << ")" << std::endl;
  int range = (gen.max)()-(gen.min)()+1;
  std::vector<int> bucket(range);
  for(int j = 0; j < iter; j++) {
    int result = gen();
    if(result < (gen.min)() || result > (gen.max)())
      std::cerr << "   ... delivers " << result << std::endl;
    else
      bucket[result-(gen.min)()]++;
  }
  int sum = 0;
  // use a different variable name "k", because MSVC has broken "for" scoping
  for(int k = 0; k < range; k++)
    sum += bucket[k];
  double avg = static_cast<double>(sum)/range;
  double p = 1 / static_cast<double>(range);
  double threshold = 2*std::sqrt(static_cast<double>(iter)*p*(1-p));
  for(int i = 0; i < range; i++) {
    if(std::fabs(bucket[i] - avg) > threshold) {
      // 95% confidence interval
      std::cout << "   ... has bucket[" << i << "] = " << bucket[i] 
                << "  (distance " << (bucket[i] - avg) << ")" 
                << std::endl;
    }
  }
}

int32_t HashMap::updateObject(
	TransactionContext& txn, const T key, uint32_t size, OId oId, OId newOId) {
	HashArrayObject topHashArrayObject(txn, *getObjectManager());
	hashArray_.getTopArray(txn, topHashArrayObject);

	uint32_t addr = hashBucketAddr<T>(key, size);
	Bucket bucket(
		txn, *getObjectManager(), maxArraySize_, maxCollisionArraySize_);
	hashArray_.get(txn, addr, bucket);
	Bucket::Cursor cursor(txn, *getObjectManager());
	bucket.set(txn, cursor);

	bool updated = false;
	while (bucket.next(txn, cursor)) {
		if (bucket.getCurrentOId(cursor) == oId) {
			bucket.setCurrentOId(cursor, newOId);
			updated = true;
			break;
		}
	}

	if (updated == false) {
		return GS_FAIL;
	}


	return GS_SUCCESS;
}

 void snap(const int p, const prevPlanes &pp, ColorVal &minv, ColorVal &maxv, ColorVal &v) const {
     const ColorBucket& b = bucket(p,pp);
     minv=b.min;
     maxv=b.max;
     if (b.min > b.max) { assert(false); e_printf("Corruption detected!\n"); exit(4); } // this should only happen on malicious input files
     v=b.snapColor(v);
 }

int32_t HashMap::removeObject(
	TransactionContext& txn, const T key, uint32_t size, OId oId) {
	size_t bucketSize;
	{
		uint32_t addr = hashBucketAddr<T>(key, size);
		Bucket bucket(
			txn, *getObjectManager(), maxArraySize_, maxCollisionArraySize_);
		hashArray_.get(txn, addr, bucket);
		if (bucket.remove(txn, oId, bucketSize) == true) {
			hashMapImage_->size_--;
		}
	}

	if (hashMapImage_->toMerge_) {
		merge<T>(txn);
	}

	if (static_cast<uint32_t>(bucketSize) < THRESHOLD_MERGE &&
		hashMapImage_->toSplit_ == false &&
		hashMapImage_->front_ > INITIAL_HASH_ARRAY_SIZE) {
		hashMapImage_->toMerge_ = true;  
	}

	return GS_SUCCESS;
}

 void StatFile::flushOneExpBucket()
 {
     //  flush the bucket being shifted out, but nothing else
     Bucket &eb0(expBucket[0]);
     Log(LL_Debug, "istat") << "StatFile::flushOneExpBucket()" << eb0.time();
     if (eb0.time() > 0)
     {
         int64_t ix = mapTimeToBucketIndex(eb0.time());
         int64_t oix = mapTimeToBucketIndex(eb0.time() - fileHeader_->season);
         Bucket *wb = writableBucket(ix);
         Bucket const &o = bucket(oix);
         if (o.time() > 0)
         {
             *wb = o;
             wb->expUpdate(eb0, fileHeader_->lambda);
         }
         else
         {
             *wb = eb0;
         }
     }
     //  must move one over
     memmove(expBucket, &expBucket[1], sizeof(expBucket)-sizeof(expBucket[0]));
     expBucket[sizeof(expBucket)/sizeof(expBucket[0])-1] = Bucket(true);
 }

static inline bool
internal_delete (fset_t *dbs, mem_hash_t *m, void *key, void **data)
{
    size_t              ref;
    size_t              k = dbs->key_length;
    size_t              tomb = NONE;
    mem_hash_t          mem = m == NULL ? EMPTY : *m;
    int found = fset_locate (dbs, &mem, key, &ref, &tomb);
    HREassert (found != FSET_FULL);
    if (found == 0)
        return false;
    wipe_chain (dbs, ref);

    *data = bucket(dbs, dbs->data, ref) + k;

    if (dbs->size != dbs->init_size && dbs->load < dbs->size >> 3) {
        memcpy (dbs->delled_data, *data, dbs->data_length);
        *data = dbs->delled_data;

        bool res = resize (dbs, SHRINK);                // <12.5% keys ==> shrink
        HREassert (res, "Cannot shrink table?");
    } else if (dbs->tombs << 1 > dbs->size) {
        memcpy (dbs->delled_data, *data, dbs->data_length);
        *data = dbs->delled_data;

        bool res = resize (dbs, REHASH);                // >50% tombs ==> rehash
        HREassert (res, "Cannot rehash table?");
    }
    return true;
}

void BucketTest::testToString() {
    BucketSpace bucketSpace(0x123450006789ULL);
    CPPUNIT_ASSERT_EQUAL(vespalib::string("BucketSpace(0x0000123450006789)"), bucketSpace.toString());
    Bucket bucket(bucketSpace, BucketId(0x123456789ULL));
    CPPUNIT_ASSERT_EQUAL(
            vespalib::string("Bucket(BucketSpace(0x0000123450006789), BucketId(0x0000000123456789))"),
            bucket.toString());
}