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
105
106
107
108
109
110
111
|
/**************************************************************/
/* ********************************************************** */
/* * * */
/* * HASHMAP * */
/* * * */
/* * $Module: HASHMAP * */
/* * * */
/* * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001 * */
/* * MPI fuer Informatik * */
/* * * */
/* * This program is free software; you can redistribute * */
/* * it and/or modify it under the terms of the FreeBSD * */
/* * Licence. * */
/* * * */
/* * This program 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 LICENCE file * */
/* * for more details. * */
/* * * */
/* * * */
/* $Revision: 1.5 $ * */
/* $State: Exp $ * */
/* $Date: 2011-11-27 12:13:11 $ * */
/* $Author: weidenb $ * */
/* * * */
/* * Contact: * */
/* * Christoph Weidenbach * */
/* * MPI fuer Informatik * */
/* * Stuhlsatzenhausweg 85 * */
/* * 66123 Saarbruecken * */
/* * Email: spass@mpi-inf.mpg.de * */
/* * Germany * */
/* * * */
/* ********************************************************** */
/**************************************************************/
#ifndef _HASHMAP_
#define _HASHMAP_
/**************************************************************/
/* Includes */
/**************************************************************/
#include "memory.h"
#include "misc.h"
#include "list.h"
/**************************************************************/
/* Structures */
/**************************************************************/
typedef uintptr_t HASHMAP_HASH;
typedef HASHMAP_HASH (*HM_GET_HASH_FUNCTION)(POINTER);
typedef BOOL (*HM_KEY_EQUAL_FUNCTION)(POINTER, POINTER);
typedef struct HASHMAPBOX_HELP {
POINTER key;
HASHMAP_HASH hash;
POINTER value;
} HASHMAPBOX_NODE;
typedef HASHMAPBOX_NODE *HASHMAPBOX;
typedef struct HASHMAP_HELP {
LIST* table; /* the actual array, it is an array of lists of hashmapboxes */
int size; /* size of the table, has to be a power of two */
int num_of_els; /* number of elements currently stored */
HM_GET_HASH_FUNCTION GetHash; /* function to compute hashes from keys */
HM_KEY_EQUAL_FUNCTION KeyEqual; /* function to test for equality of keys */
BOOL talking; /* debug field */
} HASHMAP_NODE;
typedef HASHMAP_NODE *HASHMAP;
/**************************************************************/
/* Functions */
/**************************************************************/
void hm_Init(void);
void hm_Free(void);
HASHMAP hm_Create(int, HM_GET_HASH_FUNCTION, HM_KEY_EQUAL_FUNCTION, BOOL);
void hm_Clear(HASHMAP);
void hm_ClearWithElement(HASHMAP,void (*)(POINTER));
void hm_Delete(HASHMAP);
void hm_DeleteWithElement(HASHMAP,void (*)(POINTER));
HASHMAP_HASH hm_StringHash(const char*);
HASHMAP_HASH hm_PointerHash(POINTER);
BOOL hm_PointerEqual(POINTER, POINTER);
void hm_Insert(HASHMAP,POINTER,POINTER);
POINTER hm_Retrieve(HASHMAP,POINTER);
POINTER hm_RetrieveFound(HASHMAP,POINTER, BOOL*);
void hm_Remove(HASHMAP,POINTER);
/* functions that make only sense when values stored are lists */
void hm_InsertListAppend(HASHMAP,POINTER,LIST);
void hm_InsertListInsertUnique(HASHMAP,POINTER,POINTER);
void hm_RemoveListDelete(HASHMAP,POINTER);
void hm_DeleteList(HASHMAP);
#endif
|
