/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=2 et sw=2 tw=80: */
/*
Copyright 2013-2021 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt
SPDX-License-Identifier: BSD-2-Clause-FreeBSD
SPDX-FileCopyrightText: 2021 The Libfossil Authors
SPDX-ArtifactOfProjectName: Libfossil
SPDX-FileType: Code
Heavily indebted to the Fossil SCM project (https://fossil-scm.org).
*/
/***************************************************************************
This file houses the code for the fsl_id_bag class.
*/
#include <assert.h>
#include <string.h> /* memset() */
#include "libfossil.h"
#include "fossil-scm/internal.h"
const fsl_id_bag fsl_id_bag_empty = fsl_id_bag_empty_m;
void fsl_id_bag_clear(fsl_id_bag * const p){
fsl_free(p->list);
*p = fsl_id_bag_empty;
}
/*
The hash function
*/
#define fsl_id_bag_hash(i) (i*101)
/*
Change the size of the hash table on a bag so that
it contains N slots
Completely reconstruct the hash table from scratch. Deleted
entries (indicated by a -1) are removed. When finished,
p->entryCount==p->used and p->capacity==newSize.
Returns on on success, FSL_RC_OOM on allocation error.
*/
static int fsl_id_bag_resize(fsl_id_bag * const p, fsl_size_t newSize){
fsl_size_t i;
fsl_id_bag old;
fsl_size_t nDel = 0; /* Number of deleted entries */
fsl_size_t nLive = 0; /* Number of live entries */
fsl_id_t * newList;
assert( newSize > p->entryCount );
newList = (fsl_id_t*)fsl_malloc( sizeof(p->list[0])*newSize );
if(!newList) return FSL_RC_OOM;
old = *p;
p->list = newList;
p->capacity = newSize;
memset(p->list, 0, sizeof(p->list[0])*newSize );
for(i=0; i<old.capacity; i++){
fsl_id_t const e = old.list[i];
if( e>0 ){
unsigned h = fsl_id_bag_hash(e)%newSize;
while( p->list[h] ){
h++;
if( h==newSize ) h = 0;
}
p->list[h] = e;
nLive++;
}else if( e<0 ){
nDel++;
}
}
assert( p->entryCount == nLive );
assert( p->used == nLive+nDel );
p->used = p->entryCount;
fsl_id_bag_clear(&old);
return 0;
}
void fsl_id_bag_reset(fsl_id_bag * const p){
p->entryCount = p->used = 0;
if(p->list){
memset(p->list, 0, sizeof(p->list[0])*p->capacity);
}
}
int fsl_id_bag_insert(fsl_id_bag * const p, fsl_id_t e){
fsl_size_t h;
int rc = 0;
assert( e>0 );
if( p->used+1 >= p->capacity/2 ){
fsl_size_t const n = p->capacity ? p->capacity*2 : 30;
rc = fsl_id_bag_resize(p, n );
if(rc) return rc;
}
h = fsl_id_bag_hash(e)%p->capacity;
while( p->list[h]>0 && p->list[h]!=e ){
h++;
if( h>=p->capacity ) h = 0;
}
if( p->list[h]<=0 ){
if( p->list[h]==0 ) ++p->used;
p->list[h] = e;
++p->entryCount;
rc = 0;
}
return rc;
}
bool fsl_id_bag_contains(fsl_id_bag const * const p, fsl_id_t e){
fsl_size_t h;
assert( e>0 );
if( p->capacity==0 || 0==p->used ){
return false;
}
assert(p->list);
h = fsl_id_bag_hash(e)%p->capacity;
while( p->list[h] && p->list[h]!=e ){
h++;
if( h>=p->capacity ) h = 0
/*loop around to the start*/
;
}
return p->list[h]==e;
}
bool fsl_id_bag_remove(fsl_id_bag * const p, fsl_id_t e){
fsl_size_t h;
bool rv = false;
assert( e>0 );
if( !p->capacity || !p->used ) return rv;
assert(p->list);
h = fsl_id_bag_hash(e)%p->capacity;
while( p->list[h] && p->list[h]!=e ){
++h;
if( h>=p->capacity ) h = 0;
}
rv = p->list[h]==e;
if( p->list[h] ){
fsl_size_t nx = h+1;
if( nx>=p->capacity ) nx = 0;
if( p->list[nx]==0 ){
p->list[h] = 0;
--p->used;
}else{
p->list[h] = -1;
}
--p->entryCount;
if( p->entryCount==0 ){
memset(p->list, 0, p->capacity*sizeof(p->list[0]));
p->used = 0;
}else if( p->capacity>40 && p->entryCount<p->capacity/8 ){
fsl_id_bag_resize(p, p->capacity/2)
/* ignore realloc error and keep the old size. */;
}
}
return rv;
}
fsl_id_t fsl_id_bag_first(fsl_id_bag const * const p){
if( p->capacity==0 || 0==p->used ){
return 0;
}else{
fsl_size_t i;
for(i=0; i<p->capacity && p->list[i]<=0; ++i){}
if( i<p->capacity ){
return p->list[i];
}else{
return 0;
}
}
}
fsl_id_t fsl_id_bag_next(fsl_id_bag const * const p, fsl_id_t e){
fsl_size_t h;
assert( p->capacity>0 );
assert( e>0 );
assert(p->list);
h = fsl_id_bag_hash(e)%p->capacity;
while( p->list[h] && p->list[h]!=e ){
++h;
if( h>=p->capacity ) h = 0;
}
assert( p->list[h] );
h++;
while( h<p->capacity && p->list[h]<=0 ){
h++;
}
return h<p->capacity ? p->list[h] : 0;
}
fsl_size_t fsl_id_bag_count(fsl_id_bag const * const p){
return p->entryCount;
}
void fsl_id_bag_swap(fsl_id_bag * const lhs, fsl_id_bag * const rhs){
fsl_id_bag x = *lhs;
*lhs = *rhs;
*rhs = x;
}
#undef fsl_id_bag_hash