mirror of
https://github.com/zerotier/lf.git
synced 2026-05-22 16:24:00 -07:00
Adam Ierymenko
67 lines
1.7 KiB
C
67 lines
1.7 KiB
C
/* This Source Code Form is subject to the terms of the Mozilla Public
|
|
* License, v. 2.0. If a copy of the MPL was not distributed with this
|
|
* file, You can obtain one at https://mozilla.org/MPL/2.0/.
|
|
*
|
|
* (c)2019-2021 ZeroTier, Inc.
|
|
* https://www.zerotier.com/
|
|
*/
|
|
|
|
#ifndef ZTLF_ISET_H
|
|
#define ZTLF_ISET_H
|
|
|
|
#include "common.h"
|
|
#include "vector.h"
|
|
|
|
#define ZTLF_ISET_BUCKET_COUNT 4194304
|
|
|
|
/**
|
|
* A fast integer set with a currently fixed number of buckets
|
|
*/
|
|
struct ZTLF_ISet { struct ZTLF_Vector_i64 buckets[ZTLF_ISET_BUCKET_COUNT]; };
|
|
|
|
static inline struct ZTLF_ISet *ZTLF_ISet_New()
|
|
{
|
|
struct ZTLF_ISet *s;
|
|
ZTLF_MALLOC_CHECK(s = (struct ZTLF_ISet *)malloc(sizeof(struct ZTLF_ISet)));
|
|
memset(s,0,sizeof(struct ZTLF_ISet));
|
|
return s;
|
|
}
|
|
|
|
static inline void ZTLF_ISet_Free(struct ZTLF_ISet *s)
|
|
{
|
|
for(unsigned long k=0;k<ZTLF_ISET_BUCKET_COUNT;++k) {
|
|
ZTLF_Vector_i64_Free(s->buckets + k);
|
|
}
|
|
free(s);
|
|
}
|
|
|
|
static inline void ZTLF_ISet_Clear(struct ZTLF_ISet *s)
|
|
{
|
|
for(unsigned long k=0;k<ZTLF_ISET_BUCKET_COUNT;++k) {
|
|
ZTLF_Vector_i64_Clear(s->buckets + k);
|
|
}
|
|
}
|
|
|
|
static inline bool ZTLF_ISet_Put(struct ZTLF_ISet *s,const int64_t i)
|
|
{
|
|
struct ZTLF_Vector_i64 *const v = s->buckets + ((unsigned long)(0x9e3779b97f4a7c13ULL * (uint64_t)i) % ZTLF_ISET_BUCKET_COUNT);
|
|
for(unsigned long k=0;k<v->size;k++) {
|
|
if (v->v[k] == i)
|
|
return false;
|
|
}
|
|
ZTLF_Vector_i64_Append(v,i);
|
|
return true;
|
|
}
|
|
|
|
static inline bool ZTLF_ISet_Contains(struct ZTLF_ISet *s,const int64_t i)
|
|
{
|
|
struct ZTLF_Vector_i64 *const v = s->buckets + ((unsigned long)(0x9e3779b97f4a7c13ULL * (uint64_t)i) % ZTLF_ISET_BUCKET_COUNT);
|
|
for(unsigned long k=0;k<v->size;k++) {
|
|
if (v->v[k] == i)
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
#endif
|