Statistics
| Branch: | Revision:

grapes / src / ChunkIDSet / chunkids_ops.c @ 31c9346c

History | View | Annotate | Download (4.22 KB)

1
/*
2
 *  Copyright (c) 2010 Luca Abeni
3
 *
4
 *  This is free software; see lgpl-2.1.txt
5
 */
6

    
7
#include <stdlib.h>
8
#include <stdint.h>
9
#include <limits.h>
10
#include <string.h>
11
#include <assert.h>
12

    
13
#include "chunkids_private.h"
14
#include "chunkidset.h"
15
#include "config.h"
16

    
17
#define DEFAULT_SIZE_INCREMENT 32
18

    
19
struct chunkID_set *chunkID_set_init(const char *config)
20
{
21
  struct chunkID_set *p;
22
  struct tag *cfg_tags;
23
  int res;
24
  const char *type;
25

    
26
  p = malloc(sizeof(struct chunkID_set));
27
  if (p == NULL) {
28
    return NULL;
29
  }
30
  p->n_elements = 0;
31
  cfg_tags = config_parse(config);
32
  if (!cfg_tags) {
33
    free(p);
34
    return NULL;
35
  }
36
  res = config_value_int(cfg_tags, "size", &p->size);
37
  if (!res) {
38
    p->size = 0;
39
  }
40
  if (p->size) {
41
    p->elements = malloc(p->size * sizeof(int));
42
    if (p->elements == NULL) {
43
      p->size = 0;
44
    }
45
  } else {
46
    p->elements = NULL;
47
  }
48
  p->type = CIST_PRIORITY;
49
  type = config_value_str(cfg_tags, "type");
50
  if (type) {
51
    if (!memcmp(type, "priority", strlen(type) - 1)) {
52
      p->type = CIST_PRIORITY;
53
    } else if (!memcmp(type, "bitmap", strlen(type) - 1)) {
54
      p->type = CIST_BITMAP;
55
    } else {
56
      chunkID_set_free(p);
57
      free(cfg_tags);
58

    
59
      return NULL; 
60
    }
61
  }
62
  free(cfg_tags);
63
  assert(p->type == CIST_PRIORITY || p->type == CIST_BITMAP);
64

    
65
  return p;
66
}
67

    
68
static int int_cmp(const void *pa, const void *pb)
69
{
70
  return (*(const int *)pa - *(const int *)pb);
71
}
72

    
73
static int check_insert_pos(const struct chunkID_set *h, int id)
74
{
75
  int a, b, c, r;
76

    
77
  if (! h->n_elements) {
78
    return 0;
79
  }
80

    
81
  a = 0;
82
  b = c = h->n_elements - 1;
83

    
84
  while ((r = int_cmp(&id, &h->elements[b])) != 0) {
85
    if (r > 0) {
86
      if (b == c) {
87
        return b + 1;
88
      } else {
89
        a = b + 1;
90
      }
91
    } else {
92
      if (b == a) {
93
        return b;
94
      } else {
95
        c = b;
96
      }
97
    }
98
    b = (a + c) / 2;
99
  }
100

    
101
  return -1;
102
}
103

    
104
static int chunkID_set_add_chunk_set(struct chunkID_set *h, int chunk_id)
105
{
106
  int pos;
107

    
108
  pos = check_insert_pos(h, chunk_id);
109
  if (pos < 0){
110
    return 0;
111
  }
112

    
113
  if (h->n_elements == h->size) {
114
    int *res;
115

    
116
    res = realloc(h->elements, (h->size + DEFAULT_SIZE_INCREMENT) * sizeof(int));
117
    if (res == NULL) {
118
      return -1;
119
    }
120
    h->size += DEFAULT_SIZE_INCREMENT;
121
    h->elements = res;
122
  }
123

    
124
  memmove(&h->elements[pos + 1], &h->elements[pos] , ((h->n_elements++) - pos) * sizeof(int));
125

    
126
  h->elements[pos] = chunk_id;
127

    
128
  return h->n_elements;
129
}
130

    
131
static int chunkID_set_add_chunk_list(struct chunkID_set *h, int chunk_id)
132
{
133
  if (chunkID_set_check(h, chunk_id) >= 0) {
134
    return 0;
135
  }
136

    
137
  if (h->n_elements == h->size) {
138
    int *res;
139

    
140
    res = realloc(h->elements, (h->size + DEFAULT_SIZE_INCREMENT) * sizeof(int));
141
    if (res == NULL) {
142
      return -1;
143
    }
144
    h->size += DEFAULT_SIZE_INCREMENT;
145
    h->elements = res;
146
  }
147
  h->elements[h->n_elements++] = chunk_id;
148

    
149
  return h->n_elements;
150
}
151

    
152
int chunkID_set_add_chunk(struct chunkID_set *h, int chunk_id)
153
{
154
  if (h->type == CIST_BITMAP) {
155
    return chunkID_set_add_chunk_set(h, chunk_id);
156
  } else {
157
    return chunkID_set_add_chunk_list(h, chunk_id);
158
  }
159
}
160

    
161

    
162
int chunkID_set_size(const struct chunkID_set *h)
163
{
164
  return h->n_elements;
165
}
166

    
167
int chunkID_set_get_chunk(const struct chunkID_set *h, int i)
168
{
169
  if (i < h->n_elements) {
170
    return h->elements[i];
171
  }
172

    
173
  return -1;
174
}
175

    
176
static inline int chunkID_set_check_set(const struct chunkID_set *h, int chunk_id)
177
{
178
  int *p;
179

    
180
  p = bsearch(&chunk_id, h->elements, (size_t) h->n_elements, sizeof(h->elements[0]), int_cmp);
181
  return p ? p - h->elements : -1;
182
}
183

    
184
static inline int chunkID_set_check_list(const struct chunkID_set *h, int chunk_id)
185
{
186
  int i;
187

    
188
  for (i = 0; i < h->n_elements; i++) {
189
    if (h->elements[i] == chunk_id) {
190
      return i;
191
    }
192
  }
193

    
194
  return -1;
195
}
196

    
197
int chunkID_set_check(const struct chunkID_set *h, int chunk_id)
198
{
199
  if (h->type == CIST_BITMAP) {
200
    return chunkID_set_check_set(h, chunk_id);
201
  } else {
202
    return chunkID_set_check_list(h, chunk_id);
203
  }
204
}
205

    
206
void chunkID_set_clear(struct chunkID_set *h, int size)
207
{
208
  h->n_elements = 0;
209
  h->size = size;
210
  h->elements = realloc(h->elements, size * sizeof(int));
211
  if (h->elements == NULL) {
212
    h->size = 0;
213
  }
214
}
215

    
216
void chunkID_set_free(struct chunkID_set *h)
217
{
218
  chunkID_set_clear(h,0);
219
  free(h->elements);
220
  free(h);
221
}