Loading...
Searching...
No Matches
XrdOucHash.hh
Go to the documentation of this file.
#ifndef __OOUC_HASH__
#define __OOUC_HASH__
/******************************************************************************/
/* */
/* X r d O u c H a s h . h h */
/* */
/* (c) 2004 by the Board of Trustees of the Leland Stanford, Jr., University */
/* Produced by Andrew Hanushevsky for Stanford University under contract */
/* DE-AC02-76-SFO0515 with the Department of Energy */
/* */
/* This file is part of the XRootD software suite. */
/* */
/* XRootD is free software: you can redistribute it and/or modify it under */
/* the terms of the GNU Lesser General Public License as published by the */
/* Free Software Foundation, either version 3 of the License, or (at your */
/* option) any later version. */
/* */
/* XRootD 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 Lesser General Public */
/* License for more details. */
/* */
/* You should have received a copy of the GNU Lesser General Public License */
/* along with XRootD in a file called COPYING.LESSER (LGPL license) and file */
/* COPYING (GPL license). If not, see <http://www.gnu.org/licenses/>. */
/* */
/* The copyright holder's institutional names and contributor's names may not */
/* be used to endorse or promote products derived from this software without */
/* specific prior written permission of the institution or contributor. */
/******************************************************************************/
#include <cstdlib>
#include <sys/types.h>
#include <cstring>
#include <ctime>
/*
Hash_data_is_key - The key and data are the same so when an item is added
the data pointer is set to the key address.
Hash_replace - When adding an item, any existing item is replaced.
Hash_count - The number of deletion requests must equal the number of
additions before the item is actually deleted.
Hash_keep - When the item is added, the key is not duplicated and
when the item is deleted, the key *and* data are not deleted.
Hash_dofree - When an item is deleted the data is released using free()
instead of delete().
Hash_keepdata - Works like Hash_keep but only applies to the data object.
When adding the entry, the key is strdup'd and when deleting
an entry, the key is freed.
*/
enum XrdOucHash_Options {Hash_default = 0x0000,
Hash_data_is_key = 0x0001,
Hash_replace = 0x0002,
Hash_count = 0x0004,
Hash_keep = 0x0008,
Hash_dofree = 0x0010,
Hash_keepdata = 0x0020
};
template<class T>
class XrdOucHash_Item
{
public:
int Count() {return keycount;}
T *Data() {return keydata;}
unsigned long Hash() {return keyhash;}
const char *Key() {return keyval;}
XrdOucHash_Item<T> *Next() {return next;}
time_t Time() {return keytime;}
void Update(int newcount, time_t newtime)
{keycount = newcount;
if (newtime) keytime = newtime;
}
int Same(const unsigned long KeyHash, const char *KeyVal)
{return keyhash == KeyHash && !strcmp(keyval, KeyVal);}
void SetNext(XrdOucHash_Item<T> *item) {next = item;}
XrdOucHash_Item(unsigned long KeyHash,
const char *KeyVal,
T *KeyData,
time_t KeyTime,
XrdOucHash_Item<T> *KeyNext,
XrdOucHash_Options KeyOpts)
{keyhash = KeyHash;
if (KeyOpts & Hash_keep) keyval = KeyVal;
else keyval = strdup(KeyVal);
if (KeyOpts & Hash_data_is_key) keydata = (T *)keyval;
else keydata = KeyData;
keytime = KeyTime;
entopts = KeyOpts;
next = KeyNext;
keycount= 0;
}
~XrdOucHash_Item()
{if (!(entopts & Hash_keep))
{if (keydata && keydata != (T *)keyval
&& !(entopts & Hash_keepdata))
{if (entopts & Hash_dofree) free(keydata);
else delete keydata;
}
if (keyval) free((void *)keyval);
}
keydata = 0; keyval = 0; keycount = 0;
}
private:
XrdOucHash_Item<T> *next;
const char *keyval;
unsigned long keyhash;
T *keydata;
time_t keytime;
int keycount;
XrdOucHash_Options entopts;
};
template<class T>
class XrdOucHash
{
public:
// Add() adds a new item to the hash. If it exists and repl = 0 then the old
// entry is returned and the new data is not added. Otherwise the current
// entry is replaced (see Rep()) and 0 is returned. If we have no memory
// to add the new entry, an ENOMEM exception is thrown. The
// LifeTime value is the number of seconds this entry is to be considered
// valid. When the time has passed, the entry may be deleted. A value
// of zero, keeps the entry until explicitly deleted. A special feature
// allows the data to be associated with the key to be the actual key
// using the Hash_data_is_key option. In this case, KeyData is ignored.
// The Hash_count option keeps track of duplicate key entries for Del.
//
T *Add(const char *KeyVal, T *KeyData, const int LifeTime=0,
XrdOucHash_Options opt=Hash_default);
// Del() deletes the item from the hash. If it doesn't exist, it returns
// -ENOENT. Otherwise 0 is returned. If the Hash_count option is specified
// tyhen the entry is only deleted when the entry count is below 0.
//
int Del(const char *KeyVal, XrdOucHash_Options opt = Hash_default);
// Find() simply looks up an entry in the cache. It can optionally return the
// lifetime associated with the entry. If the
//
T *Find(const char *KeyVal, time_t *KeyTime=0);
// Num() returns the number of items in the hash table
//
int Num() {return hashnum;}
// Purge() simply deletes all of the appendages to the table.
//
void Purge();
// Rep() is simply Add() that allows replacement.
//
T *Rep(const char *KeyVal, T *KeyData, const int LifeTime=0,
XrdOucHash_Options opt=Hash_default)
{return Add(KeyVal, KeyData, LifeTime,
(XrdOucHash_Options)(opt | Hash_replace));}
// Apply() applies the specified function to every item in the hash. The
// first argument is the key value, the second is the associated data,
// the third argument is whatever is the passed in void *variable, The
// following actions occur for values returned by the applied function:
// <0 - The hash table item is deleted.
// =0 - The next hash table item is processed.
// >0 - Processing stops and the hash table item is returned.
//
T *Apply(int (*func)(const char *, T *, void *), void *Arg);
// When allocateing a new hash, specify the required starting size. Make
// sure that the previous number is the correct Fibonocci antecedent. The
// series is simply n[j] = n[j-1] + n[j-2].
//
XrdOucHash(int psize = 89, int size=144, int load=80);
~XrdOucHash() {if (hashtable) {Purge(); free(hashtable); hashtable = 0;}}
private:
void Remove(int kent, XrdOucHash_Item<T> *hip, XrdOucHash_Item<T> *phip);
XrdOucHash_Item<T> *Search(XrdOucHash_Item<T> *hip,
const unsigned long khash,
const char *kval,
XrdOucHash_Item<T> **phip=0);
unsigned long HashVal(const char *KeyVal);
void Expand();
XrdOucHash_Item<T> **hashtable;
int prevtablesize;
int hashtablesize;
int hashnum;
int hashmax;
int hashload;
};
/******************************************************************************/
/* A c t u a l I m p l e m e n t a t i o n */
/******************************************************************************/
#include "XrdOuc/XrdOucHash.icc"
#endif
XrdOucHash_Options
XrdOucHash_Options
Definition XrdOucHash.hh:51
Hash_count
@ Hash_count
Definition XrdOucHash.hh:54
Hash_data_is_key
@ Hash_data_is_key
Definition XrdOucHash.hh:52
Hash_keepdata
@ Hash_keepdata
Definition XrdOucHash.hh:57
Hash_default
@ Hash_default
Definition XrdOucHash.hh:51
Hash_replace
@ Hash_replace
Definition XrdOucHash.hh:53
Hash_keep
@ Hash_keep
Definition XrdOucHash.hh:55
Hash_dofree
@ Hash_dofree
Definition XrdOucHash.hh:56
XrdOucHash.icc
XrdOucHash_Item
Definition XrdOucHash.hh:62
XrdOucHash_Item::Hash
unsigned long Hash()
Definition XrdOucHash.hh:68
XrdOucHash_Item::XrdOucHash_Item
XrdOucHash_Item(unsigned long KeyHash, const char *KeyVal, T *KeyData, time_t KeyTime, XrdOucHash_Item< T > *KeyNext, XrdOucHash_Options KeyOpts)
Definition XrdOucHash.hh:86
XrdOucHash_Item::Same
int Same(const unsigned long KeyHash, const char *KeyVal)
Definition XrdOucHash.hh:81
XrdOucHash_Item::Next
XrdOucHash_Item< T > * Next()
Definition XrdOucHash.hh:72
XrdOucHash_Item::~XrdOucHash_Item
~XrdOucHash_Item()
Definition XrdOucHash.hh:103
XrdOucHash_Item::Data
T * Data()
Definition XrdOucHash.hh:66
XrdOucHash_Item::Update
void Update(int newcount, time_t newtime)
Definition XrdOucHash.hh:76
XrdOucHash_Item::Time
time_t Time()
Definition XrdOucHash.hh:74
XrdOucHash_Item::Count
int Count()
Definition XrdOucHash.hh:64
XrdOucHash_Item::Key
const char * Key()
Definition XrdOucHash.hh:70
XrdOucHash_Item::SetNext
void SetNext(XrdOucHash_Item< T > *item)
Definition XrdOucHash.hh:84
XrdOucHash::Del
int Del(const char *KeyVal, XrdOucHash_Options opt=Hash_default)
Definition XrdOucHash.icc:136
XrdOucHash::Purge
void Purge()
Definition XrdOucHash.icc:193
XrdOucHash::~XrdOucHash
~XrdOucHash()
Definition XrdOucHash.hh:186
XrdOucHash::Rep
T * Rep(const char *KeyVal, T *KeyData, const int LifeTime=0, XrdOucHash_Options opt=Hash_default)
Definition XrdOucHash.hh:166
XrdOucHash::Apply
T * Apply(int(*func)(const char *, T *, void *), void *Arg)
Definition XrdOucHash.icc:102
XrdOucHash::Num
int Num()
Definition XrdOucHash.hh:158
XrdOucHash::Add
T * Add(const char *KeyVal, T *KeyData, const int LifeTime=0, XrdOucHash_Options opt=Hash_default)
Definition XrdOucHash.icc:61
XrdOucHash::Find
T * Find(const char *KeyVal, time_t *KeyTime=0)
Definition XrdOucHash.icc:160
XrdOucHash::XrdOucHash
XrdOucHash(int psize=89, int size=144, int load=80)
Definition XrdOucHash.icc:44