← Back to branch summary

~ubuntu-branches/ubuntu/utopic/glame/utopic

« back to all changes in this revision

Viewing changes to src/include/hash.h

  • Committer: Bazaar Package Importer
  • Author(s): Daniel Kobras
  • Date: 2002-04-09 17:14:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020409171412-jzpnov7mbz2w6zsr
Tags: upstream-0.6.2
Import upstream version 0.6.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/include/hash.h
 
1
#ifndef _HASH_H
 
2
#define _HASH_H
 
3
 
 
4
/*
 
5
 * hash.h
 
6
 *
 
7
 * Copyright (C) 1999, 2000 Richard Guenther
 
8
 *
 
9
 * This program is free software; you can redistribute it and/or modify
 
10
 * it under the terms of the GNU General Public License as published by
 
11
 * the Free Software Foundation; either version 2 of the License, or
 
12
 * (at your option) any later version.
 
13
 *
 
14
 * This program is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
17
 * GNU General Public License for more details.
 
18
 *
 
19
 * You should have received a copy of the GNU General Public License
 
20
 * along with this program; if not, write to the Free Software
 
21
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
22
 *
 
23
 */
 
24
 
 
25
#ifdef HAVE_CONFIG_H
 
26
#include <config.h>
 
27
#endif
 
28
 
 
29
/* Static hashtable generator, use like
 
30
 *   struct node {
 
31
 *       struct node **pprev_node_hash;
 
32
 *       struct node *next_node_hash;
 
33
 *       int id;
 
34
 *       ...
 
35
 *   };
 
36
 *   HASH(node, struct node, 8,
 
37
 *        (node->id == id),
 
38
 *        (id),
 
39
 *        (node->id),
 
40
 *        int id)
 
41
 * to have a struct node hash with id as the hash key and a
 
42
 * 1<<8 sized hashtable. The following functions are created:
 
43
 *   hash_add_node(struct node *)
 
44
 *   hash_remove_node(struct node *)
 
45
 *   hash_find_node(int id)
 
46
 *   hash_find_next_node(int id, struct node *)
 
47
 *   hash_next_node(struct node *)
 
48
 *   hash_init_node(struct node *)
 
49
 *   is_hashed_node(struct node *)
 
50
 *   hash_getslot_node(int slot)
 
51
 * 
 
52
 * So the HASH macro would have the following prototype:
 
53
 * HASH(symbol name, type recordtype, int hashbits, expr comparison,
 
54
 *      expr hash(...), expr hash(recordtype), hash arguments...)
 
55
 */
 
56
 
 
57
 
 
58
 
 
59
#define HASH(FOOBAR, FOOBARtype, HASH_BITS, HASH_COMPARE, HASH_HASHFN_FROM_PARAMS, HASH_HASHFN_FROM_TYPE, params...) \
 
60
\
 
61
static FOOBARtype *FOOBAR##_hash_table[1<<HASH_BITS]; \
 
62
\
 
63
static inline FOOBARtype *hash_getslot_##FOOBAR(int slot) \
 
64
{ \
 
65
    return FOOBAR##_hash_table[slot&((1<<HASH_BITS)-1)]; \
 
66
} \
 
67
\
 
68
static inline FOOBARtype *hash_find_##FOOBAR(params) \
 
69
{ \
 
70
  FOOBARtype *FOOBAR = FOOBAR##_hash_table[(HASH_HASHFN_FROM_PARAMS)&((1<<HASH_BITS)-1)]; \
 
71
  goto inside; \
 
72
\
 
73
  for (;;) { \
 
74
    FOOBAR = FOOBAR->next_##FOOBAR##_hash; \
 
75
inside: \
 
76
    if (!FOOBAR) \
 
77
      break; \
 
78
    if (HASH_COMPARE) \
 
79
      break; \
 
80
  } \
 
81
  return FOOBAR; \
 
82
} \
 
83
\
 
84
static inline FOOBARtype *hash_find_next_##FOOBAR(params, FOOBARtype *FOOBAR) \
 
85
{ \
 
86
  if (!FOOBAR) { \
 
87
    FOOBAR = FOOBAR##_hash_table[(HASH_HASHFN_FROM_PARAMS)&((1<<HASH_BITS)-1)]; \
 
88
    goto inside; \
 
89
  } \
 
90
\
 
91
  for (;;) { \
 
92
    FOOBAR = FOOBAR->next_##FOOBAR##_hash; \
 
93
inside: \
 
94
    if (!FOOBAR) \
 
95
      break; \
 
96
    if (HASH_COMPARE) \
 
97
      break; \
 
98
  } \
 
99
  return FOOBAR; \
 
100
} \
 
101
\
 
102
static inline FOOBARtype *hash_next_##FOOBAR(FOOBARtype *FOOBAR) \
 
103
{ \
 
104
        return (FOOBAR)->next_##FOOBAR##_hash; \
 
105
} \
 
106
\
 
107
static inline void hash_add_##FOOBAR(FOOBARtype *FOOBAR) \
 
108
{ \
 
109
        FOOBARtype **tt = &FOOBAR##_hash_table[(HASH_HASHFN_FROM_TYPE)&((1<<HASH_BITS)-1)]; \
 
110
        if (((FOOBAR)->next_##FOOBAR##_hash = *(tt)) != NULL) \
 
111
                (*(tt))->pprev_##FOOBAR##_hash = &(FOOBAR)->next_##FOOBAR##_hash; \
 
112
        *(tt) = (FOOBAR); \
 
113
        (FOOBAR)->pprev_##FOOBAR##_hash = (tt); \
 
114
} \
 
115
\
 
116
static inline void hash_remove_##FOOBAR(FOOBARtype *t) \
 
117
{ \
 
118
        if (!t->pprev_##FOOBAR##_hash) \
 
119
                return; \
 
120
        if (t->next_##FOOBAR##_hash) \
 
121
                t->next_##FOOBAR##_hash->pprev_##FOOBAR##_hash = t->pprev_##FOOBAR##_hash; \
 
122
        *t->pprev_##FOOBAR##_hash = t->next_##FOOBAR##_hash; \
 
123
        t->pprev_##FOOBAR##_hash = NULL; \
 
124
} \
 
125
\
 
126
static inline void hash_init_##FOOBAR(FOOBARtype *t) \
 
127
{ \
 
128
        t->pprev_##FOOBAR##_hash = NULL; \
 
129
} \
 
130
\
 
131
static inline int is_hashed_##FOOBAR(FOOBARtype *t) \
 
132
{ \
 
133
        return t->pprev_##FOOBAR##_hash != NULL; \
 
134
}
 
135
 
 
136
 
 
137
#endif