From: mgh Date: Mon, 16 Jul 2007 12:15:32 +0000 (+0000) Subject: Added a hash table implementation X-Git-Url: https://rtime.felk.cvut.cz/gitweb/frescor/frsh-include.git/commitdiff_plain/65ab1df93cbab6c97a8eee20aed9353e18cc8ace Added a hash table implementation git-svn-id: http://www.frescor.org/private/svn/frescor/frsh/trunk/include@533 35b4ef3e-fd22-0410-ab77-dab3279adceb --- diff --git a/frsh_hash_table.h b/frsh_hash_table.h new file mode 100644 index 0000000..31fc0f2 --- /dev/null +++ b/frsh_hash_table.h @@ -0,0 +1,165 @@ +// ----------------------------------------------------------------------- +// Copyright (C) 2006 - 2007 FRESCOR consortium partners: +// +// Universidad de Cantabria, SPAIN +// University of York, UK +// Scuola Superiore Sant'Anna, ITALY +// Kaiserslautern University, GERMANY +// Univ. Politécnica Valencia, SPAIN +// Czech Technical University in Prague, CZECH REPUBLIC +// ENEA SWEDEN +// Thales Communication S.A. FRANCE +// Visual Tools S.A. SPAIN +// Rapita Systems Ltd UK +// Evidence ITALY +// +// See http://www.frescor.org for a link to partners' websites +// +// FRESCOR project (FP6/2005/IST/5-034026) is funded +// in part by the European Union Sixth Framework Programme +// The European Union is not liable of any use that may be +// made of this code. +// +// +// This file is part of FRSH Implementation +// +// FRSH API is free software; you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation; either version 2, or (at your option) +// any later version. +// +// FRSH API 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. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// distributed with FRSH API; see file COPYING. If not, write to the +// Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA +// 02111-1307, USA. +// +// As a special exception, if you include this header file into source +// files to be compiled, this header file does not by itself cause +// the resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. +// ----------------------------------------------------------------------- +//============================================== +// ******** ******* ******** ** ** +// **///// /**////** **////// /** /** +// ** /** /** /** /** /** +// ******* /******* /********* /********** +// **//// /**///** ////////** /**//////** +// ** /** //** /** /** /** +// ** /** //** ******** /** /** +// // // // //////// // // +// +// FRSH(FRescor ScHeduler), pronounced "fresh" +//============================================== +// + +// This header file defines the interface to a hash table used to map +// from a string key into an integer value. The number of entries in +// the hash table is bounded by a maximum value, and therefore it is +// not necessary to have a dynamic size table. The integer values are +// non negative, so a negative value can be used as an error +// indication. The key strings are assumed constant, so there is no +// need to copy them. + + +#ifndef FRSH_HASH_TABLE +#define FRSH_HASH_TABLE + +#include + +/** + * A configurable constant that defines the maximum length of the string keys + */ + +#define FRSH_HASH_TABLE_MAX_CHARS 21 + +// Type that contains the status of an entry +typedef enum {frsh_hash_empty, frsh_hash_valid, frsh_hash_cleaned} +frsh_hash_entry_status_t; + +/** + * Type that defines a table entry + */ +typedef struct { + char key[FRSH_HASH_TABLE_MAX_CHARS]; // array where the key is stored + int value; // integer value (assumed non negative) + frsh_hash_entry_status_t status; // indicates the entry status +} frsh_hash_entry_t; + +/** + * Type that defines a hash table + */ +typedef struct { + int size; // size of the table + int max_chars; // maximum characters of the key strings + int num; // current number of entries + int cleaned; // current number of cleaned entries + frsh_hash_entry_t * entry; // pointer to table of entries + frsh_hash_entry_t * old_entry; // pointer to old table of entries, used + // to recreate the table when necessary +} frsh_hash_table_t; + +/** + * Function that maps a string key into an integer value + */ +unsigned int frsh_hash_function (const char *str, int max_chars); + + +/** + * Create a hash table to store up to the specified number of + * keys equal to max_size. The maximum size of the String values + * is specified in max_chars. + * Returns: 0 if successful + * FRSH_ERR_NO_SPACE if there is not enough memory available + * FRSH_ERR_TOO_LARGE if max_chars exceeds FRSH_HASH_TABLE_MAX_CHARS + */ +int frsh_hash_table_init (frsh_hash_table_t *table, + int max_size, int max_chars); + +/** + * Delete a hash table, eliminating the resources allocated to it + */ +void frsh_hash_table_destroy (frsh_hash_table_t *table); + +/** + * Empty a hash table, eliminating all entries from it + */ +void frsh_hash_table_clean (frsh_hash_table_t *table); + +/** + * Assign a value to a key. An older value is removed if present + * Returns: 0 if successful + * FRSH_ERR_NO_SPACE if the maximum number of keys would be exceeded + */ +int frsh_hash_table_put (frsh_hash_table_t *table, + const char * key, int value); + +/** + * Get the value assigned to a key. + * Returns -1 if the key is not present + */ +int frsh_hash_table_get (frsh_hash_table_t *table, const char * key); + +/** + * Indicate whether or not the specified key is contained in the table + */ +bool frsh_hash_table_contains_key (frsh_hash_table_t *table, const char * key); + +/** + * Remove an entry from the table + * Returns 0 if successful, or -1 if the key is not contained in the table + */ +int frsh_hash_table_remove (frsh_hash_table_t *table, const char * key); + + + +#endif // FRSH_HASH_TABLE + + +