int newoffset=tailoffset+4;
struct ListNode *ptr=tail;
if (newoffset>=WLISTSIZE) {
- newoffset-=WLISTSIZE;
- struct ListNode *oldptr=ptr;
- ptr=ptr->next;
- free(oldptr);
+ if (newoffset!=WLISTSIZE||head!=tail) {
+ newoffset-=WLISTSIZE;
+ struct ListNode *oldptr=ptr;
+ ptr=ptr->next;
+ free(oldptr);
+ }
}
tail=ptr;
tailoffset=newoffset;
if (headoffset==WLISTSIZE) {
if (head->next==0) {
head->next=(struct ListNode *)malloc(sizeof(struct ListNode));
- head->next=0;
+ head->next->next=0;
}
headoffset=0;
head=head->next;
+ if (tailoffset==WLISTSIZE) { /* roll the tail over also */
+ tailoffset=0;
+ tail=tail->next;
+ }
}
head->data[headoffset++]=id;
head->data[headoffset++]=type;
return 0;
}
-
+void SimpleHash::addAll(SimpleHash * set) {
+ SimpleIterator it;
+ set->iterator(it);
+ while(it.hasNext()) {
+ int key=it.key();
+ int data=it.next();
+ add(key,data);
+ }
+}
int SimpleHash::add(int key, int data) {
- unsigned int hashkey = (unsigned int)key % size;
-
- struct SimpleNode **ptr = &bucket[hashkey];
-
- /* check that this key/object pair isn't already here */
- // TBD can be optimized for set v. relation */
- while (*ptr) {
- if ((*ptr)->key == key && (*ptr)->data == data) {
- return 0;
- }
- ptr = &((*ptr)->next);
- }
- if (tailindex==ARRAYSIZE) {
- listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
- tailindex=0;
- listtail=listtail->nextarray;
+ /* Rehash code */
+ if (numelements>=size) {
+ int newsize=2*size+1;
+ struct SimpleNode ** newbucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*newsize,1);
+ for(int i=size-1;i>=0;i--) {
+ for(struct SimpleNode *ptr=bucket[i];ptr!=NULL;) {
+ struct SimpleNode * nextptr=ptr->next;
+ unsigned int newhashkey=(unsigned int)ptr->key % newsize;
+ ptr->next=newbucket[newhashkey];
+ newbucket[newhashkey]=ptr;
+ ptr=nextptr;
+ }
}
-
- *ptr = &listtail->nodes[tailindex++];
- (*ptr)->key=key;
- (*ptr)->data=data;
- (*ptr)->inuse=1;
+ size=newsize;
+ free(bucket);
+ bucket=newbucket;
+ }
- numelements++;
-
- for (int i = 0; i < numparents; i++) {
- parents[i]->add(key, data);
- }
+ unsigned int hashkey = (unsigned int)key % size;
+ struct SimpleNode **ptr = &bucket[hashkey];
+
+ /* check that this key/object pair isn't already here */
+ /* TBD can be optimized for set v. relation */
- return 1;
+ while (*ptr) {
+ if ((*ptr)->key == key && (*ptr)->data == data) {
+ return 0;
+ }
+ ptr = &((*ptr)->next);
+ }
+ if (tailindex==ARRAYSIZE) {
+ listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
+ tailindex=0;
+ listtail=listtail->nextarray;
+ }
+
+ *ptr = &listtail->nodes[tailindex++];
+ (*ptr)->key=key;
+ (*ptr)->data=data;
+ (*ptr)->inuse=1;
+
+ numelements++;
+
+ for (int i = 0; i < numparents; i++) {
+ parents[i]->add(key, data);
+ }
+ return 1;
}
bool SimpleHash::contains(int key) {
return count;
}
+SimpleHash * SimpleHash::imageSet(int key) {
+ SimpleHash * newset=new SimpleHash(2*count(key)+4);
+ unsigned int hashkey = (unsigned int)key % size;
+
+ struct SimpleNode *ptr = bucket[hashkey];
+ while (ptr) {
+ if (ptr->key == key) {
+ newset->add(ptr->data,ptr->data);
+ }
+ ptr = ptr->next;
+ }
+ return newset;
+}
+
int SimpleHash::get(int key, int&data) {
unsigned int hashkey = (unsigned int)key % size;