GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
diglib/cindex.c
Go to the documentation of this file.
1 
2 /*****************************************************************************
3 *
4 * MODULE: Vector library
5 *
6 * AUTHOR(S): Radim Blazek
7 *
8 * PURPOSE: Lower level functions for reading/writing/manipulating vectors.
9 *
10 * COPYRIGHT: (C) 2001 by the GRASS Development Team
11 *
12 * This program is free software under the GNU General Public
13 * License (>=v2). Read the file COPYING that comes with GRASS
14 * for details.
15 *
16 *****************************************************************************/
17 #include <stdlib.h>
18 #include <string.h>
19 #include <grass/vector.h>
20 
21 /*!
22  * \brief Initialize Plus_head structure (cidx)
23  *
24  * \param Plus pointer to Plus_head structure
25  *
26  * \return 1 OK
27  * \return 0 on error
28  */
29 int dig_cidx_init(struct Plus_head *Plus)
30 {
31  G_debug(3, "dig_cidx_init()");
32 
33  Plus->n_cidx = 0;
34  Plus->a_cidx = 5;
35  Plus->cidx =
36  (struct Cat_index *)G_malloc(Plus->a_cidx * sizeof(struct Cat_index));
37  if (!Plus->cidx)
38  return 0;
39  Plus->cidx_up_to_date = 0;
40  return 1;
41 }
42 
43 /* Free category index */
44 void dig_cidx_free(struct Plus_head *Plus)
45 {
46  int i;
47  struct Cat_index *ci;
48 
49  G_debug(2, "dig_cidx_free()");
50  for (i = 0; i < Plus->n_cidx; i++) {
51  ci = &(Plus->cidx[i]);
52  G_free(ci->cat);
53  ci->cat = NULL;
54  ci->field = ci->n_cats = ci->a_cats = ci->n_types = 0;
55  }
56  if (Plus->cidx) {
57  G_free(Plus->cidx);
58  Plus->cidx = NULL;
59  }
60  Plus->a_cidx = 0;
61  Plus->n_cidx = 0;
62  Plus->cidx_up_to_date = 0;
63 }
64 
65 /*
66  * dig_cidx_add_cat ()
67  * add new field - cat - line record, space is allocated if necessary
68  *
69  * returns 1 OK
70  * 0 on error
71  */
72 int
73 dig_cidx_add_cat(struct Plus_head *Plus, int field, int cat, int line,
74  int type)
75 {
76  int i, si, found;
77  struct Cat_index *ci;
78 
79  G_debug(3, "dig_cidx_add_cat(): field = %d cat = %d line = %d type = %d",
80  field, cat, line, type);
81 
82  /* Find field or add new */
83  si = -1;
84  for (i = 0; i < Plus->n_cidx; i++) {
85  if (Plus->cidx[i].field == field) {
86  si = i;
87  }
88  }
89  if (si == -1) { /* not found add new */
90  if (Plus->n_cidx == Plus->a_cidx) {
91  Plus->a_cidx += 10;
92  Plus->cidx =
93  (struct Cat_index *)G_realloc(Plus->cidx,
94  Plus->a_cidx *
95  sizeof(struct Cat_index));
96  if (!Plus->cidx)
97  return 0;
98  }
99  si = Plus->n_cidx;
100  ci = &(Plus->cidx[si]);
101  ci->field = field;
102  ci->n_cats = ci->a_cats = 0;
103  ci->cat = NULL;
104  ci->n_types = 0;
105  ci->offset = 0;
106  Plus->n_cidx++;
107  }
108 
109  /* Add new cat - line record */
110  ci = &(Plus->cidx[si]);
111  if (ci->n_cats == ci->a_cats) {
112  ci->a_cats += 5000;
113  ci->cat = G_realloc(ci->cat, ci->a_cats * 3 * sizeof(int));
114  }
115 
116  ci->cat[ci->n_cats][0] = cat;
117  ci->cat[ci->n_cats][1] = type;
118  ci->cat[ci->n_cats][2] = line;
119  ci->n_cats++;
120 
121  /* Add type */
122  found = 0;
123  for (i = 0; i < ci->n_types; i++) {
124  if (ci->type[i][0] == type) {
125  ci->type[i][1]++;
126  found = 1;
127  }
128  }
129  if (!found) {
130  ci->type[ci->n_types][0] = type;
131  ci->type[ci->n_types][1] = 1;
132  ci->n_types++;
133  }
134 
135  return 1;
136 }
137 
138 /* Compare by cat, resolve ties by type, resolve ties by id */
139 static int cmp_cat(const void *pa, const void *pb)
140 {
141  int *p1 = (int *)pa;
142  int *p2 = (int *)pb;
143 
144  if (p1[0] < p2[0])
145  return -1;
146  if (p1[0] > p2[0])
147  return 1;
148  if (p1[1] < p2[1])
149  return -1;
150  if (p1[1] > p2[1])
151  return 1;
152  if (p1[2] < p2[2])
153  return -1;
154  if (p1[2] > p2[2])
155  return 1;
156  return 0;
157 }
158 
159 /* Compare by field */
160 static int cmp_field(const void *pa, const void *pb)
161 {
162  struct Cat_index *p1 = (struct Cat_index *)pa;
163  struct Cat_index *p2 = (struct Cat_index *)pb;
164 
165  if (p1->field < p2->field)
166  return -1;
167  if (p1->field > p2->field)
168  return 1;
169  return 0;
170 }
171 
172 /*
173  * dig_cidx_add_cat_sorted ()
174  * add new field - cat - line record to sorted category index, space is allocated if necessary
175  *
176  * returns 1 OK
177  * 0 on error
178  */
179 int
180 dig_cidx_add_cat_sorted(struct Plus_head *Plus, int field, int cat, int line,
181  int type)
182 {
183  int i, si, found, position;
184  struct Cat_index *ci;
185 
186  G_debug(3,
187  "dig_cidx_add_cat_sorted(): field = %d cat = %d line = %d type = %d",
188  field, cat, line, type);
189 
190  /* Find field or add new */
191  si = -1;
192  for (i = 0; i < Plus->n_cidx; i++) {
193  if (Plus->cidx[i].field == field) {
194  si = i;
195  }
196  }
197  if (si == -1) { /* not found add new */
198  if (Plus->n_cidx == Plus->a_cidx) {
199  Plus->a_cidx += 10;
200  Plus->cidx =
201  (struct Cat_index *)G_realloc(Plus->cidx,
202  Plus->a_cidx *
203  sizeof(struct Cat_index));
204  if (!Plus->cidx)
205  return 0;
206  }
207  si = Plus->n_cidx;
208  ci = &(Plus->cidx[si]);
209  ci->field = field;
210  ci->n_cats = ci->a_cats = 0;
211  ci->cat = NULL;
212  ci->n_types = 0;
213  ci->offset = 0;
214  Plus->n_cidx++;
215  }
216 
217  /* Add new cat - line record */
218  ci = &(Plus->cidx[si]);
219  if (ci->n_cats == ci->a_cats) {
220  ci->a_cats += 5000;
221  ci->cat = G_realloc(ci->cat, ci->a_cats * 3 * sizeof(int));
222  }
223 
224  /* Find position and move on the way */
225  for (position = ci->n_cats; position > 0; position--) {
226  if (ci->cat[position - 1][0] < cat ||
227  (ci->cat[position - 1][0] == cat && ci->cat[position - 1][1] <= type)) {
228  break;
229  }
230  ci->cat[position][0] = ci->cat[position - 1][0];
231  ci->cat[position][1] = ci->cat[position - 1][1];
232  ci->cat[position][2] = ci->cat[position - 1][2];
233  }
234 
235  G_debug(4, "position = %d", position);
236 
237  ci->cat[position][0] = cat;
238  ci->cat[position][1] = type;
239  ci->cat[position][2] = line;
240  ci->n_cats++;
241 
242  /* Add type */
243  found = 0;
244  for (i = 0; i < ci->n_types; i++) {
245  if (ci->type[i][0] == type) {
246  ci->type[i][1]++;
247  found = 1;
248  }
249  }
250  if (!found) {
251  ci->type[ci->n_types][0] = type;
252  ci->type[ci->n_types][1] = 1;
253  ci->n_types++;
254  }
255 
256  /* Sort by field */
257  qsort(Plus->cidx, Plus->n_cidx, sizeof(struct Cat_index), cmp_field);
258 
259  G_debug(3, "Added new category to index");
260 
261  return 1;
262 }
263 
264 /*
265  * dig_cidx_del_cat ()
266  * delete old field - cat - line record from _sorted_ category index
267  *
268  * returns 1 OK
269  * 0 on error
270  */
271 int
272 dig_cidx_del_cat(struct Plus_head *Plus, int field, int cat, int line,
273  int type)
274 {
275  int i, position;
276  struct Cat_index *ci;
277 
278  G_debug(3, "dig_cidx_del_cat(): field = %d cat = %d line = %d", field,
279  cat, line);
280 
281  /* Find field or add new */
282  ci = NULL;
283  for (i = 0; i < Plus->n_cidx; i++) {
284  if (Plus->cidx[i].field == field) {
285  ci = &(Plus->cidx[i]);
286  }
287  }
288  if (ci == NULL) { /* should not happen */
289  G_warning("BUG: Category index not found for field %d.", field);
290  return 0;
291  }
292 
293  /* Find position */
294  G_debug(3, "n_cats = %d", ci->n_cats);
295  for (position = 0; position < ci->n_cats; position++) {
296  if (ci->cat[position][0] == cat && ci->cat[position][1] == type &&
297  ci->cat[position][2] == line) {
298  break;
299  }
300  }
301 
302  G_debug(4, "position = %d", position);
303 
304  if (position == ci->n_cats) {
305  G_warning("BUG: Category not found in category index.");
306  return 0;
307  }
308 
309  /* Delete */
310  for (i = position; i < ci->n_cats - 1; i++) {
311  ci->cat[i][0] = ci->cat[i + 1][0];
312  ci->cat[i][1] = ci->cat[i + 1][1];
313  ci->cat[i][2] = ci->cat[i + 1][2];
314  }
315 
316  ci->n_cats--;
317 
318  for (i = 0; i < ci->n_types; i++) {
319  if (ci->type[i][0] == type) {
320  ci->type[i][1]--;
321  }
322  }
323 
324  G_debug(3, "Deleted from category index");
325  return 1;
326 }
327 
328 /*
329  * dig_cidx_sort ()
330  * sort all records in cat index
331  *
332  */
333 void dig_cidx_sort(struct Plus_head *Plus)
334 {
335  int f;
336  struct Cat_index *ci;
337 
338  G_debug(2, "dig_cidx_sort()");
339 
340  for (f = 0; f < Plus->n_cidx; f++) {
341  int c, nucats = 0;
342 
343  ci = &(Plus->cidx[f]);
344 
345  /* Sort by 1. category, 2. type, 3. line id */
346  qsort(ci->cat, ci->n_cats, 3 * sizeof(int), cmp_cat);
347 
348  /* Calculate number of unique cats */
349  if (ci->n_cats > 0)
350  nucats++;
351  for (c = 1; c < ci->n_cats; c++) {
352  if (ci->cat[c][0] != ci->cat[c - 1][0])
353  nucats++;
354  }
355  ci->n_ucats = nucats;
356  }
357 
358  /* Sort by field */
359  qsort(Plus->cidx, Plus->n_cidx, sizeof(struct Cat_index), cmp_field);
360 }
#define G_malloc(n)
Definition: defs/gis.h:112
int a_cidx
Allocated space for category indexes.
Definition: dig_structs.h:1145
struct Version_info cidx
Version info for category index file.
Definition: dig_structs.h:793
int n_types
Number of types in type.
Definition: dig_structs.h:757
int dig_cidx_add_cat_sorted(struct Plus_head *Plus, int field, int cat, int line, int type)
off_t offset
Offset of the beginning of this index in cidx file.
Definition: dig_structs.h:773
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:149
Category index.
Definition: dig_structs.h:732
int field
Field (layer) number.
Definition: dig_structs.h:737
#define NULL
Definition: ccmath.h:32
int n_ucats
Number of unique cats (not updated)
Definition: dig_structs.h:753
int cidx_up_to_date
Category index to be updated.
Definition: dig_structs.h:1156
Basic topology-related info.
Definition: dig_structs.h:784
int dig_cidx_add_cat(struct Plus_head *Plus, int field, int cat, int line, int type)
Definition: diglib/cindex.c:73
int n_cats
Number of items in cat array.
Definition: dig_structs.h:741
void dig_cidx_sort(struct Plus_head *Plus)
int(* cat)[3]
Array of cats (cat, type, lines/area)
Definition: dig_structs.h:749
void dig_cidx_free(struct Plus_head *Plus)
Definition: diglib/cindex.c:44
int dig_cidx_init(struct Plus_head *Plus)
Initialize Plus_head structure (cidx)
Definition: diglib/cindex.c:29
int type[7][2]
Number of elements for each type.
Definition: dig_structs.h:769
int a_cats
Allocated space in cat array.
Definition: dig_structs.h:745
void G_warning(const char *,...) __attribute__((format(printf
#define G_realloc(p, n)
Definition: defs/gis.h:114
int dig_cidx_del_cat(struct Plus_head *Plus, int field, int cat, int line, int type)
int G_debug(int, const char *,...) __attribute__((format(printf
int n_cidx
Number of category indexes (one for each field/layer)
Definition: dig_structs.h:1141