da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* http://www.opensource.org/licenses/cpl1.0.txt *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#pragma prototyped
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * Glenn Fowler
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * AT&T Research
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * hash table library
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include "hashlib.h"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * free (remove) a hash table
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * can be called for partially constructed tables
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * scope covered table pointer is returned
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * root info freed when last reference freed
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinHash_table_t*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinhashfree(register Hash_table_t* tab)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register Hash_bucket_t** sp;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register Hash_bucket_t* b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register Hash_bucket_t* p;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_bucket_t** sx;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_root_t* rp;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_table_t* tp;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_free_f freevalue;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_free_f freebucket;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_region_f region;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin void* handle;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!tab) return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (tab->table)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin freebucket = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin freevalue = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (tab->root->local->free)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (tab->root->flags & HASH_BUCKET) freebucket = tab->root->local->free;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else freevalue = tab->root->local->free;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (region = tab->root->local->region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin handle = tab->root->local->handle;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin sx = &tab->table[tab->size];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin sp = &tab->table[0];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin while (sp < sx)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b = *sp++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin while (b)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin p = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b = b->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (freebucket) (*freebucket)((char*)p);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if (freevalue && p->value) (*freevalue)(p->value);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (p->hash & HASH_FREENAME)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin p->hash &= ~HASH_FREENAME;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (region) (*region)(handle, p->name, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else free(p->name);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(p->hash & HASH_KEEP))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (region) (*region)(handle, p, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else free(p);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if (p->hash & HASH_HIDES)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin p->hash &= ~HASH_HIDES;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin p->name = ((Hash_bucket_t*)p->name)->name;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if ((tab->flags & (HASH_RESIZE|HASH_STATIC)) != HASH_STATIC)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (region) (*region)(handle, tab->table, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else free(tab->table);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else region = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (tab->root)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * remove from the table lists
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if ((tp = tab->root->references) != tab)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for (; tp; tp = tp->next)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (tp->next == tab)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin tp->next = tab->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if (!(tab->root->references = tp->next))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if ((rp = hash_info.list) != tab->root)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for (; rp; rp = rp->next)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (rp->next == tab->root)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin rp->next = tab->root->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else hash_info.list = rp->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(tab->root->references))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (tab->root->local)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(tab->root->local);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (region) (*region)(handle, tab->root, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else free(tab->root);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (tp = tab->scope) tp->frozen--;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (region) (*region)(handle, tab, 0, 0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else free(tab);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(tp);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}