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