/* * Copyright (c) 2002, The Tendra Project * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice unmodified, this list of conditions, and the following * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * * Crown Copyright (c) 1997 * * This TenDRA(r) Computer Program is subject to Copyright * owned by the United Kingdom Secretary of State for Defence * acting through the Defence Evaluation and Research Agency * (DERA). It is made available to Recipients with a * royalty-free licence for its use, reproduction, transfer * to other parties and amendment for any purpose not excluding * product development provided that any such use et cetera * shall be deemed to be acceptance of the following conditions:- * * (1) Its Recipients shall ensure that this Notice is * reproduced upon any copies or amended versions of it; * * (2) Any amended version of it shall be clearly marked to * show both the nature of and the organisation responsible * for the relevant amendment or amendments; * * (3) Its onward transfer from a recipient to another * party shall be deemed to be that party's acceptance of * these conditions; * * (4) DERA gives no warranty or assurance as to its * quality or suitability for any purpose and DERA accepts * no liability whatsoever in relation to any use to which * it may be put. * * $TenDRA: tendra/src/tools/tspec/hash.c,v 1.8 2004/08/08 08:50:20 stefanf Exp $ */ #include "config.h" #include "fmm.h" #include "msgcat.h" #include "object.h" #include "hash.h" #include "type.h" #include "utility.h" /* * STANDARD HASH TABLES * * These hash tables represent the various namespaces permitted in C * plus the TDF token namespace. */ hash_table *exps; hash_table *files; hash_table *keywords; hash_table *subsets; hash_table *tags; hash_table *tag_fields; hash_table *tokens; hash_table *types; hash_table *type_fields; /* * INITIALISATION ROUTINE * * This routine initialises the standard hash tables and sets a few * miscellaneous variables. */ void init_hash(void) { buffer = xalloc (buffsize + 100); exps = make_hash_table ("Expression"); files = make_hash_table ("Output file"); keywords = make_hash_table ("Keyword"); subsets = make_hash_table ("Set"); tags = make_hash_table ("Tag"); tag_fields = make_hash_table ("Field selector struct/union"); tokens = make_hash_table ("Token"); types = make_hash_table ("Type"); type_fields = make_hash_table ("Field selector"); return; } /* * HASHING ROUTINE * * This routine finds the hash value of the string nm. This value must * lie in the range [ 0, hash_size). */ static int hash(char *nm) { char *s; int n = 0; for (s = nm; *s; s++) n += *s; return (n % hash_size); } /* * CREATE A NEW HASH TABLE * * This routine creates a new hash table called nm. */ hash_table * make_hash_table(char *nm) { int i; hash_table *t = xalloc (sizeof (*t)); t->name = nm; for (i = 0; i < hash_size; i++) t->array [i] = null; return (t); } /* * LOOK UP A NAME IN A HASH TABLE * * This routine looks up the object nm (version v) in the hth column * of hash table t. It returns the object if it is found, or null * otherwise. */ static object * lookup_hash(hash_table *t, char *nm, int v, int h) { hash_elem *e = t->array [h]; while (e) { if (streq (nm, e->obj->name)) { if (v == e->vers || v == any_version) return (e->obj); } e = e->next; } return (null); } /* * ADD AN OBJECT TO A HASH TABLE * * This routine adds the object p (version v) to the hash table t, * reporting an error and returning the old value if it is already * defined. Otherwise it returns p. */ object * add_hash(hash_table *t, object *p, int v) { hash_elem *e; char *nm = p->name; int h = hash (nm); object *q = lookup_hash (t, nm, v, h); if (q != null) { char *fn = q->filename; if (fn) { MSG_name_already_defined_at(t->name, nm, fn, q->line_no); } else { MSG_name_already_defined(t->name, nm); } return (q); } e = xalloc (sizeof (*e)); e->obj = p; e->vers = v; e->next = t->array [h]; t->array [h] = e; return (p); } /* * SEARCH A HASH TABLE FOR AN OBJECT * * This routine searches the hash table t for the object named nm * (version v), returning it if it is found. If it is not found then * null is returned. */ object * search_hash(hash_table *t, char *nm, int v) { int h = hash (nm); return (lookup_hash (t, nm, v, h)); } /* * SORT THE ELEMENTS OF A HASH LIST * * This routine sorts the elements of the hash table t into a single * alphabetical list. The table cannot be used subsequently. */ hash_elem * sort_hash(hash_table *t) { int i; hash_elem *r = null; for (i = 0; i < hash_size; i++) { hash_elem *p = t->array [i]; while (p) { hash_elem *pn = p->next; hash_elem *q = r, *s = null; while (q) { if (strcmp (p->obj->name, q->obj->name) <= 0) break; s = q; q = q->next; } if (s == null) { p->next = r; r = p; } else { p->next = s->next; s->next = p; } p = pn; } } return (r); }