/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=2 et sw=2 tw=80: */
/*
Copyright (c) 2013 D. Richard Hipp
This program is free software; you can redistribute it and/or
modify it under the terms of the Simplified BSD License (also
known as the "2-Clause License" or "FreeBSD License".)
This program is distributed in the hope that it will be useful,
but without any warranty; without even the implied warranty of
merchantability or fitness for a particular purpose.
Author contact information:
drh@hwaci.com
http://www.hwaci.com/drh/
*****************************************************************************
This file houses the code for the fsl_id_bag class.
*/
#include <assert.h>
#include <string.h> /* memset() */
#include "fossil-scm/fossil.h"
#include "fossil-scm/fossil-internal.h"
const fsl_id_bag fsl_id_bag_empty = fsl_id_bag_empty_m;
/* Only for debugging */
#include <stdio.h>
#define MARKER(pfexp) \
do{ printf("MARKER: %s:%d:%s():\t",__FILE__,__LINE__,__func__); \
printf pfexp; \
} while(0)
void fsl_id_bag_clear(fsl_id_bag *p){
if(p->list) 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 *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 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;
}
int fsl_id_bag_insert(fsl_id_bag *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 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;
}
char fsl_id_bag_contains(fsl_id_bag *p, fsl_id_t e){
fsl_size_t h;
assert( e>0 );
if( p->capacity==0 || 0==p->used ){
return 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
/*loop around to the start*/
;
}
return p->list[h]==e;
}
void fsl_id_bag_remove(fsl_id_bag *p, fsl_id_t e){
fsl_size_t h;
assert( e>0 );
if( !p->capacity || !p->used ) return;
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;
}
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. */;
}
}
}
fsl_id_t fsl_id_bag_first(fsl_id_bag *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 *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 *p){
return p->entryCount;
}
#undef fsl_id_bag_hash
#undef MARKER
#undef fsl_id_bag_hash