/usr/include/BasicUsageEnvironment/BasicHashTable.hh is in liblivemedia-dev 2014.01.13-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | /**********
This library 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 2.1 of the License, or (at your
option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
This library 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 this library; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
**********/
// Copyright (c) 1996-2014 Live Networks, Inc. All rights reserved.
// Basic Hash Table implementation
// C++ header
#ifndef _BASIC_HASH_TABLE_HH
#define _BASIC_HASH_TABLE_HH
#ifndef _HASH_TABLE_HH
#include "HashTable.hh"
#endif
#ifndef _NET_COMMON_H
#include <NetCommon.h> // to ensure that "uintptr_t" is defined
#endif
// A simple hash table implementation, inspired by the hash table
// implementation used in Tcl 7.6: <http://www.tcl.tk/>
#define SMALL_HASH_TABLE_SIZE 4
class BasicHashTable: public HashTable {
private:
class TableEntry; // forward
public:
BasicHashTable(int keyType);
virtual ~BasicHashTable();
// Used to iterate through the members of the table:
class Iterator; friend class Iterator; // to make Sun's C++ compiler happy
class Iterator: public HashTable::Iterator {
public:
Iterator(BasicHashTable const& table);
private: // implementation of inherited pure virtual functions
void* next(char const*& key); // returns 0 if none
private:
BasicHashTable const& fTable;
unsigned fNextIndex; // index of next bucket to be enumerated after this
TableEntry* fNextEntry; // next entry in the current bucket
};
private: // implementation of inherited pure virtual functions
virtual void* Add(char const* key, void* value);
// Returns the old value if different, otherwise 0
virtual Boolean Remove(char const* key);
virtual void* Lookup(char const* key) const;
// Returns 0 if not found
virtual unsigned numEntries() const;
private:
class TableEntry {
public:
TableEntry* fNext;
char const* key;
void* value;
};
TableEntry* lookupKey(char const* key, unsigned& index) const;
// returns entry matching "key", or NULL if none
Boolean keyMatches(char const* key1, char const* key2) const;
// used to implement "lookupKey()"
TableEntry* insertNewEntry(unsigned index, char const* key);
// creates a new entry, and inserts it in the table
void assignKey(TableEntry* entry, char const* key);
// used to implement "insertNewEntry()"
void deleteEntry(unsigned index, TableEntry* entry);
void deleteKey(TableEntry* entry);
// used to implement "deleteEntry()"
void rebuild(); // rebuilds the table as its size increases
unsigned hashIndexFromKey(char const* key) const;
// used to implement many of the routines above
unsigned randomIndex(uintptr_t i) const {
return (unsigned)(((i*1103515245) >> fDownShift) & fMask);
}
private:
TableEntry** fBuckets; // pointer to bucket array
TableEntry* fStaticBuckets[SMALL_HASH_TABLE_SIZE];// used for small tables
unsigned fNumBuckets, fNumEntries, fRebuildSize, fDownShift, fMask;
int fKeyType;
};
#endif
|