eg_keytab.h

Go to the documentation of this file.
00001 /* EGlib "Efficient General Library" provides some basic structures and
00002  * algorithms commons in many optimization algorithms.
00003  *
00004  * Copyright (C) 2005-2008 Daniel Espinoza
00005  * 
00006  * This library is free software; you can redistribute it and/or modify it
00007  * under the terms of the GNU Lesser General Public License as published by the
00008  * Free Software Foundation; either version 2.1 of the License, or (at your
00009  * option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful, but 
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
00013  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
00014  * License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation,
00018  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
00019  * */
00020 #include "eg_macros.h"
00021 #include "eg_mem.h"
00022 #ifndef __EG_KEYTAB_H__
00023 #define __EG_KEYTAB_H__
00024 /* ========================================================================= */
00025 /** @defgroup EGkeytab key table structure
00026  * This version suport addition and finding keys, as well as getting its
00027  * associated number, which correspond to the order in which it was added. For
00028  * now it does not support deletion of elements.
00029  * */
00030 /** @file
00031  * @ingroup EGkeytab */
00032 /** @addtogroup EGkeytab */
00033 /** @{ */
00034 /** @example eg_keytab.ex.c
00035  * This is a simple example of the usage of symbol tables using @ref EGkeytab */
00036 /* ========================================================================= */
00037 /** @brief minimal information to store in the hash table */
00038 typedef struct 
00039 {
00040   uint64_t key;       /**< @brief key being stored */
00041   int next;           /**< @brief next element in the hash list 
00042                             (offset of one)*/
00043   int pos;            /**< @brief position for the asociated key */
00044 } EGkeytabInfo_t;
00045 /* ========================================================================= */
00046 /** @brief structure to store a symbol table */
00047 typedef struct 
00048 {
00049   size_t nkey;        /**< @brief number of keys in the table */
00050   size_t sz;          /**< @brief actual size of #EGkeytab_t::key */
00051   size_t hash_sz;     /**< @brief actual size of #EGkeytab_t::hash */
00052   EGkeytabInfo_t*key; /**< @brief array of all key in table */ 
00053   int* hash;          /**< @brief hash table for inverse mapping */
00054 } EGkeytab_t;
00055 /* ========================================================================= */
00056 /** @brief initialize an EGkeytab_t structure
00057  * @param __keytab structure to initialize 
00058  * */
00059 #define EGkeytabInit(__keytab) do{\
00060   EGkeytab_t*const __EGkeytab = (__keytab);\
00061   memset(__EGkeytab,0,sizeof(EGkeytab_t));}while(0)
00062 /* ========================================================================= */
00063 /** @brief clear any internally allocated memory 
00064  * @param __keytab structure to clear
00065  * */
00066 #define EGkeytabClear(__keytab) do{\
00067   EGkeytab_t*const __EGkeytab = (__keytab);\
00068   EGfree(__EGkeytab->key);\
00069   EGfree(__EGkeytab->hash);\
00070   __EGkeytab->nkey = __EGkeytab->sz = __EGkeytab->hash_sz = 0;}while(0)
00071 /* ========================================================================= */
00072 /** @brief return the i-th symbol in the table
00073  * @note we don't check for limits, it should be >=0 < #EGkeytab_t::nkey
00074  * @param __i symbol we look for
00075  * @param __keytab table to use
00076  * @return pointer to the corresponding string 
00077  * */
00078 #define EGkeytabKey(__keytab,__i) ((const uint64_t)((__keytab)->key[__i].key))
00079 /* ========================================================================= */
00080 /** @brief Add a new element to the key table, if the element already
00081  * exists, then return non zero, otherwise return zero
00082  * @param keytab table where we will add the key
00083  * @param key to add to the table
00084  * @param check_duplicate if set to one, check that the added key was not added
00085  * before.
00086  * @return zero on success, non-zero otherwise
00087  * */
00088 int EGkeytabAdd(EGkeytab_t*const keytab,
00089                 const uint64_t key,
00090                 const int check_duplicate);
00091 /* ========================================================================= */
00092 /** @brief Look for a key in the table, and if found, report the position of
00093  * the key in the table.
00094  * @param keytab table where we will look for the key
00095  * @param key to look up in the table
00096  * @param pos if not null, return there the position of the key in the
00097  * table.
00098  * @return one if the key is in the table, zero otherwise.
00099  * */
00100 int EGkeytabLookUp( const EGkeytab_t*const keytab,
00101                     const uint64_t key,
00102                     int*const pos);
00103 /* ========================================================================= */
00104 /** @} */
00105 /* end eg_keytab.h */
00106 #endif