e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Copyright (c) 2007 D. Richard Hipp e15fe43153 2007-08-31 drh: ** e15fe43153 2007-08-31 drh: ** This program is free software; you can redistribute it and/or e15fe43153 2007-08-31 drh: ** modify it under the terms of the GNU General Public e15fe43153 2007-08-31 drh: ** License version 2 as published by the Free Software Foundation. e15fe43153 2007-08-31 drh: ** e15fe43153 2007-08-31 drh: ** This program is distributed in the hope that it will be useful, e15fe43153 2007-08-31 drh: ** but WITHOUT ANY WARRANTY; without even the implied warranty of e15fe43153 2007-08-31 drh: ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU e15fe43153 2007-08-31 drh: ** General Public License for more details. e15fe43153 2007-08-31 drh: ** e15fe43153 2007-08-31 drh: ** You should have received a copy of the GNU General Public e15fe43153 2007-08-31 drh: ** License along with this library; if not, write to the e15fe43153 2007-08-31 drh: ** Free Software Foundation, Inc., 59 Temple Place - Suite 330, e15fe43153 2007-08-31 drh: ** Boston, MA 02111-1307, USA. e15fe43153 2007-08-31 drh: ** e15fe43153 2007-08-31 drh: ** Author contact information: e15fe43153 2007-08-31 drh: ** drh@hwaci.com e15fe43153 2007-08-31 drh: ** http://www.hwaci.com/drh/ e15fe43153 2007-08-31 drh: ** e15fe43153 2007-08-31 drh: ******************************************************************************* e15fe43153 2007-08-31 drh: ** e15fe43153 2007-08-31 drh: ** This file contains code used to implement a "bag" of integers. e15fe43153 2007-08-31 drh: ** A bag is an unordered collection without duplicates. In this e15fe43153 2007-08-31 drh: ** implementation, all elements must be positive integers. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: #include "config.h" e15fe43153 2007-08-31 drh: #include "bag.h" e15fe43153 2007-08-31 drh: #include <assert.h> e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: #if INTERFACE e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** An integer can appear in the bag at most once. e15fe43153 2007-08-31 drh: ** Integers must be positive. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: struct Bag { e15fe43153 2007-08-31 drh: int cnt; /* Number of integers in the bag */ e15fe43153 2007-08-31 drh: int sz; /* Number of slots in a[] */ e15fe43153 2007-08-31 drh: int used; /* Number of used slots in a[] */ e15fe43153 2007-08-31 drh: int *a; /* Hash table of integers that are in the bag */ e15fe43153 2007-08-31 drh: }; e15fe43153 2007-08-31 drh: #endif e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Initialize a Bag structure e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: void bag_init(Bag *p){ e15fe43153 2007-08-31 drh: memset(p, 0, sizeof(*p)); e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Destroy a Bag. Delete all of its content. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: void bag_clear(Bag *p){ e15fe43153 2007-08-31 drh: free(p->a); e15fe43153 2007-08-31 drh: bag_init(p); e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** The hash function e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: #define bag_hash(i) (i*101) e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Change the size of the hash table on a bag so that e15fe43153 2007-08-31 drh: ** it contains N slots e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: static void bag_resize(Bag *p, int newSize){ e15fe43153 2007-08-31 drh: int i; e15fe43153 2007-08-31 drh: Bag old; e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: old = *p; e15fe43153 2007-08-31 drh: assert( newSize>old.cnt ); e15fe43153 2007-08-31 drh: p->a = malloc( sizeof(p->a[0])*newSize ); e15fe43153 2007-08-31 drh: p->sz = newSize; e15fe43153 2007-08-31 drh: memset(p->a, 0, sizeof(p->a[0])*newSize ); e15fe43153 2007-08-31 drh: for(i=0; i<old.sz; i++){ e15fe43153 2007-08-31 drh: int e = old.a[i]; e15fe43153 2007-08-31 drh: if( e>0 ){ e15fe43153 2007-08-31 drh: unsigned h = bag_hash(e)%newSize; e15fe43153 2007-08-31 drh: while( p->a[h] ){ e15fe43153 2007-08-31 drh: h++; e15fe43153 2007-08-31 drh: if( h==newSize ) h = 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: p->a[h] = e; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: p->used = p->cnt; e15fe43153 2007-08-31 drh: bag_clear(&old); e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Insert element e into the bag if it is not there already. e15fe43153 2007-08-31 drh: ** Return TRUE if the insert actually occurred. Return FALSE e15fe43153 2007-08-31 drh: ** if the element was already in the bag. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: int bag_insert(Bag *p, int e){ e15fe43153 2007-08-31 drh: unsigned h; e15fe43153 2007-08-31 drh: int rc = 0; e15fe43153 2007-08-31 drh: assert( e>0 ); e15fe43153 2007-08-31 drh: if( p->used+1 >= p->sz/2 ){ e15fe43153 2007-08-31 drh: bag_resize(p, p->cnt*2 + 20 ); e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: h = bag_hash(e)%p->sz; e15fe43153 2007-08-31 drh: while( p->a[h] && p->a[h]!=e ){ e15fe43153 2007-08-31 drh: h++; e15fe43153 2007-08-31 drh: if( h>=p->sz ) h = 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: if( p->a[h]==0 ){ e15fe43153 2007-08-31 drh: p->a[h] = e; e15fe43153 2007-08-31 drh: p->used++; e15fe43153 2007-08-31 drh: p->cnt++; e15fe43153 2007-08-31 drh: rc = 1; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: return rc; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Return true if e in the bag. Return false if it is no. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: int bag_find(Bag *p, int e){ e15fe43153 2007-08-31 drh: unsigned h; e15fe43153 2007-08-31 drh: assert( e>0 ); e15fe43153 2007-08-31 drh: if( p->sz==0 ){ e15fe43153 2007-08-31 drh: return 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: h = bag_hash(e)%p->sz; e15fe43153 2007-08-31 drh: while( p->a[h] && p->a[h]!=e ){ e15fe43153 2007-08-31 drh: h++; e15fe43153 2007-08-31 drh: if( h>=p->sz ) h = 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: return p->a[h]==e; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Remove element e from the bag if it exists in the bag. e15fe43153 2007-08-31 drh: ** If e is not in the bag, this is a no-op. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: void bag_remove(Bag *p, int e){ e15fe43153 2007-08-31 drh: unsigned h; e15fe43153 2007-08-31 drh: assert( e>0 ); e15fe43153 2007-08-31 drh: if( p->sz==0 ) return; e15fe43153 2007-08-31 drh: h = bag_hash(e)%p->sz; e15fe43153 2007-08-31 drh: while( p->a[h] && p->a[h]!=e ){ e15fe43153 2007-08-31 drh: h++; e15fe43153 2007-08-31 drh: if( h>=p->sz ) h = 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: if( p->a[h] ){ e15fe43153 2007-08-31 drh: p->a[h] = -1; e15fe43153 2007-08-31 drh: p->cnt--; e15fe43153 2007-08-31 drh: if( p->sz>20 && p->cnt<p->sz/8 ){ e15fe43153 2007-08-31 drh: bag_resize(p, p->sz/2); e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Return the first element in the bag. Return 0 if the bag e15fe43153 2007-08-31 drh: ** is empty. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: int bag_first(Bag *p){ e15fe43153 2007-08-31 drh: int i; e15fe43153 2007-08-31 drh: for(i=0; i<p->sz && p->a[i]<=0; i++){} e15fe43153 2007-08-31 drh: if( i<p->sz ){ e15fe43153 2007-08-31 drh: return p->a[i]; e15fe43153 2007-08-31 drh: }else{ e15fe43153 2007-08-31 drh: return 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Return the next element in the bag after e. Return 0 if e15fe43153 2007-08-31 drh: ** is the last element in the bag. Any insert or removal from e15fe43153 2007-08-31 drh: ** the bag might reorder the bag. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: int bag_next(Bag *p, int e){ e15fe43153 2007-08-31 drh: unsigned h; e15fe43153 2007-08-31 drh: assert( p->sz>0 ); e15fe43153 2007-08-31 drh: assert( e>0 ); e15fe43153 2007-08-31 drh: h = bag_hash(e)%p->sz; e15fe43153 2007-08-31 drh: while( p->a[h] && p->a[h]!=e ){ e15fe43153 2007-08-31 drh: h++; e15fe43153 2007-08-31 drh: if( h>=p->sz ) h = 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: assert( p->a[h] ); e15fe43153 2007-08-31 drh: h++; e15fe43153 2007-08-31 drh: while( h<p->sz && p->a[h]<=0 ){ e15fe43153 2007-08-31 drh: h++; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: return h<p->sz ? p->a[h] : 0; e15fe43153 2007-08-31 drh: } e15fe43153 2007-08-31 drh: e15fe43153 2007-08-31 drh: /* e15fe43153 2007-08-31 drh: ** Return the number of elements in the bag. e15fe43153 2007-08-31 drh: */ e15fe43153 2007-08-31 drh: int bag_count(Bag *p){ e15fe43153 2007-08-31 drh: return p->cnt; e15fe43153 2007-08-31 drh: }
File Annotation