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 (file)
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 <stdbool.h>
+
+/**
+ * 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
+
+
+