← Back to branch summary

~ubuntu-branches/ubuntu/wily/ruby-ferret/wily

« back to all changes in this revision

Viewing changes to ext/hashset.c

  • Committer: Bazaar Package Importer
  • Author(s): Antonio Terceiro
  • Date: 2011-07-28 00:02:49 UTC
  • Revision ID: james.westby@ubuntu.com-20110728000249-v0443y69ftcpxwi6
Tags: upstream-0.11.6
Import upstream version 0.11.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/hashset.c
 
1
#include "hashset.h"
 
2
#include <string.h>
 
3
 
 
4
/*
 
5
 * The HashSet contains an array +elems+ of the elements that have been added.
 
6
 * It always has +size+ elements so +size+ ane +elems+ can be used to iterate
 
7
 * over all alements in the HashSet. It also uses a HashTable to keep track of
 
8
 * which elements have been added and their index in the +elems+ array.
 
9
 */
 
10
static HashSet *hs_alloc(void (*free_elem) (void *p))
 
11
{
 
12
    HashSet *hs = ALLOC(HashSet);
 
13
    hs->size = 0;
 
14
    hs->capa = HS_MIN_SIZE;
 
15
    hs->elems = ALLOC_N(void *, HS_MIN_SIZE);
 
16
    hs->free_elem_i = free_elem ? free_elem : &dummy_free;
 
17
    return hs;
 
18
}
 
19
 
 
20
HashSet *hs_new(unsigned long (*hash)(const void *p),
 
21
                int (*eq)(const void *p1, const void *p2),
 
22
                void (*free_elem)(void *p))
 
23
{
 
24
    HashSet *hs = hs_alloc(free_elem);
 
25
    hs->ht = h_new(hash, eq, NULL, &free);
 
26
    return hs;
 
27
}
 
28
 
 
29
HashSet *hs_new_str(void (*free_elem) (void *p))
 
30
{
 
31
    HashSet *hs = hs_alloc(free_elem);
 
32
    hs->ht = h_new_str((free_ft) NULL, &free);
 
33
    return hs;
 
34
}
 
35
 
 
36
void hs_free(HashSet *hs)
 
37
{
 
38
    h_destroy(hs->ht);
 
39
    free(hs->elems);
 
40
    free(hs);
 
41
}
 
42
 
 
43
void hs_clear(HashSet *hs)
 
44
{
 
45
    int i;
 
46
    for (i = hs->size - 1; i >= 0; i--) {
 
47
        hs_del(hs, hs->elems[i]);
 
48
    }
 
49
}
 
50
 
 
51
void hs_destroy(HashSet *hs)
 
52
{
 
53
    int i;
 
54
    if (hs->free_elem_i != &dummy_free) {
 
55
        for (i = 0; i < hs->size; i++) {
 
56
            hs->free_elem_i(hs->elems[i]);
 
57
        }
 
58
    }
 
59
    h_destroy(hs->ht);
 
60
    free(hs->elems);
 
61
    free(hs);
 
62
}
 
63
 
 
64
int hs_add(HashSet *hs, void *elem)
 
65
{
 
66
    int has_elem = h_has_key(hs->ht, elem);
 
67
    if (has_elem == HASH_KEY_EQUAL) {
 
68
        /* We don't want to keep two of the same elem so free if necessary */
 
69
        hs->free_elem_i(elem);
 
70
    }
 
71
    else if (has_elem == HASH_KEY_SAME) {
 
72
        /* No need to do anything */
 
73
    }
 
74
    else {
 
75
        /* add the elem to the array, resizing if necessary */
 
76
        if (hs->size >= hs->capa) {
 
77
            hs->capa *= 2;
 
78
            REALLOC_N(hs->elems, void *, hs->capa);
 
79
        }
 
80
        hs->elems[hs->size] = elem;
 
81
        h_set(hs->ht, elem, imalloc(hs->size));
 
82
        hs->size++;
 
83
    }
 
84
    return has_elem;
 
85
}
 
86
 
 
87
int hs_add_safe(HashSet *hs, void *elem)
 
88
{
 
89
    int has_elem = h_has_key(hs->ht, elem);
 
90
    if (has_elem == HASH_KEY_EQUAL) {
 
91
        /* element can't be added */
 
92
        return false;
 
93
    }
 
94
    else if (has_elem == HASH_KEY_SAME) {
 
95
        /* the exact same element has already been added */
 
96
        return true;
 
97
    }
 
98
    else {
 
99
        /* add the elem to the array, resizing if necessary */
 
100
        if (hs->size >= hs->capa) {
 
101
            hs->capa *= 2;
 
102
            REALLOC_N(hs->elems, void *, hs->capa);
 
103
        }
 
104
        hs->elems[hs->size] = elem;
 
105
        h_set(hs->ht, elem, imalloc(hs->size));
 
106
        hs->size++;
 
107
        return true;
 
108
    }
 
109
}
 
110
 
 
111
int hs_del(HashSet *hs, void *elem)
 
112
{
 
113
    void *tmp_elem = hs_rem(hs, elem);
 
114
    if (tmp_elem != NULL) {
 
115
        hs->free_elem_i(tmp_elem);
 
116
        return 1;
 
117
    }
 
118
    else {
 
119
        return 0;
 
120
    }
 
121
}
 
122
 
 
123
void *hs_rem(HashSet *hs, void *elem)
 
124
{
 
125
    void *ret_elem;
 
126
    int *index = (int *)h_get(hs->ht, elem);
 
127
    if (index == NULL) {
 
128
        return NULL;
 
129
    }
 
130
    else {
 
131
        int i = *index;
 
132
        int j;
 
133
        ret_elem = hs->elems[i];
 
134
        h_del(hs->ht, elem);
 
135
        hs->size--;
 
136
        for (j = i; j < hs->size; j++) {
 
137
            hs->elems[j] = hs->elems[j+1];
 
138
            h_set(hs->ht, hs->elems[j], imalloc(j));
 
139
        }
 
140
        return ret_elem;
 
141
    }
 
142
}
 
143
 
 
144
int hs_exists(HashSet *hs, void *elem)
 
145
{
 
146
    return h_has_key(hs->ht, elem);
 
147
}
 
148
 
 
149
HashSet *hs_merge(HashSet *hs, HashSet * other)
 
150
{
 
151
    int i;
 
152
    for (i = 0; i < other->size; i++) {
 
153
        hs_add(hs, other->elems[i]);
 
154
    }
 
155
    /* Now free the other hashset. It is no longer needed. No need, however, to
 
156
     * delete the elements as they're either destroyed or in the new hash set */
 
157
    hs_free(other);
 
158
    return hs;
 
159
}
 
160
 
 
161
void *hs_orig(HashSet *hs, void *elem)
 
162
{
 
163
    int *index = h_get(hs->ht, elem);
 
164
    if (index) {
 
165
        return hs->elems[*index];
 
166
    }
 
167
    else {
 
168
        return NULL;
 
169
    }
 
170
}