nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free
16 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17 */
18  
19 /*
20 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
21 * file for a list of people on the GLib Team. See the ChangeLog
22 * files for a list of changes. These files are distributed with
23 * GLib at ftp://ftp.gtk.org/pub/gtk/.
24 */
25  
26 /*
27 * MT safe
28 */
29  
30 #include "config.h"
31  
32 /* we know we are deprecated here, no need for warnings */
33 #define GLIB_DISABLE_DEPRECATION_WARNINGS
34  
35 #include "grel.h"
36  
37 #include <glib/gmessages.h>
38 #include <glib/gtestutils.h>
39 #include <glib/gstring.h>
40 #include <glib/gslice.h>
41 #include <glib/ghash.h>
42  
43 #include <stdarg.h>
44 #include <string.h>
45  
46 /**
47 * SECTION:relations
48 * @title: Relations and Tuples
49 * @short_description: tables of data which can be indexed on any
50 * number of fields
51 *
52 * A #GRelation is a table of data which can be indexed on any number
53 * of fields, rather like simple database tables. A #GRelation contains
54 * a number of records, called tuples. Each record contains a number of
55 * fields. Records are not ordered, so it is not possible to find the
56 * record at a particular index.
57 *
58 * Note that #GRelation tables are currently limited to 2 fields.
59 *
60 * To create a GRelation, use g_relation_new().
61 *
62 * To specify which fields should be indexed, use g_relation_index().
63 * Note that this must be called before any tuples are added to the
64 * #GRelation.
65 *
66 * To add records to a #GRelation use g_relation_insert().
67 *
68 * To determine if a given record appears in a #GRelation, use
69 * g_relation_exists(). Note that fields are compared directly, so
70 * pointers must point to the exact same position (i.e. different
71 * copies of the same string will not match.)
72 *
73 * To count the number of records which have a particular value in a
74 * given field, use g_relation_count().
75 *
76 * To get all the records which have a particular value in a given
77 * field, use g_relation_select(). To access fields of the resulting
78 * records, use g_tuples_index(). To free the resulting records use
79 * g_tuples_destroy().
80 *
81 * To delete all records which have a particular value in a given
82 * field, use g_relation_delete().
83 *
84 * To destroy the #GRelation, use g_relation_destroy().
85 *
86 * To help debug #GRelation objects, use g_relation_print().
87 *
88 * GRelation has been marked as deprecated, since this API has never
89 * been fully implemented, is not very actively maintained and rarely
90 * used.
91 **/
92  
93 typedef struct _GRealTuples GRealTuples;
94  
95 /**
96 * GRelation:
97 *
98 * The #GRelation struct is an opaque data structure to represent a
99 * [Relation][glib-Relations-and-Tuples]. It should
100 * only be accessed via the following functions.
101 **/
102 struct _GRelation
103 {
104 gint fields;
105 gint current_field;
106  
107 GHashTable *all_tuples;
108 GHashTable **hashed_tuple_tables;
109  
110 gint count;
111 };
112  
113 /**
114 * GTuples:
115 * @len: the number of records that matched.
116 *
117 * The #GTuples struct is used to return records (or tuples) from the
118 * #GRelation by g_relation_select(). It only contains one public
119 * member - the number of records that matched. To access the matched
120 * records, you must use g_tuples_index().
121 **/
122 struct _GRealTuples
123 {
124 gint len;
125 gint width;
126 gpointer *data;
127 };
128  
129 static gboolean
130 tuple_equal_2 (gconstpointer v_a,
131 gconstpointer v_b)
132 {
133 gpointer* a = (gpointer*) v_a;
134 gpointer* b = (gpointer*) v_b;
135  
136 return a[0] == b[0] && a[1] == b[1];
137 }
138  
139 static guint
140 tuple_hash_2 (gconstpointer v_a)
141 {
142 #if GLIB_SIZEOF_VOID_P > GLIB_SIZEOF_LONG
143 /* In practise this snippet has been written for 64-bit Windows
144 * where ints are 32 bits, pointers 64 bits. More exotic platforms
145 * need more tweaks.
146 */
147 guint* a = (guint*) v_a;
148  
149 return (a[0] ^ a[1] ^ a[2] ^ a[3]);
150 #else
151 gpointer* a = (gpointer*) v_a;
152  
153 return (gulong)a[0] ^ (gulong)a[1];
154 #endif
155 }
156  
157 static GHashFunc
158 tuple_hash (gint fields)
159 {
160 switch (fields)
161 {
162 case 2:
163 return tuple_hash_2;
164 default:
165 g_error ("no tuple hash for %d", fields);
166 }
167  
168 return NULL;
169 }
170  
171 static GEqualFunc
172 tuple_equal (gint fields)
173 {
174 switch (fields)
175 {
176 case 2:
177 return tuple_equal_2;
178 default:
179 g_error ("no tuple equal for %d", fields);
180 }
181  
182 return NULL;
183 }
184  
185 /**
186 * g_relation_new:
187 * @fields: the number of fields.
188 *
189 * Creates a new #GRelation with the given number of fields. Note that
190 * currently the number of fields must be 2.
191 *
192 * Returns: a new #GRelation.
193 *
194 * Deprecated: 2.26: Rarely used API
195 **/
196 GRelation*
197 g_relation_new (gint fields)
198 {
199 GRelation* rel = g_new0 (GRelation, 1);
200  
201 rel->fields = fields;
202 rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
203 rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
204  
205 return rel;
206 }
207  
208 static void
209 relation_delete_value_tuple (gpointer tuple_key,
210 gpointer tuple_value,
211 gpointer user_data)
212 {
213 GRelation *relation = user_data;
214 gpointer *tuple = tuple_value;
215 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
216 }
217  
218 static void
219 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
220 {
221 g_hash_table_destroy ((GHashTable*) value);
222 }
223  
224 /**
225 * g_relation_destroy:
226 * @relation: a #GRelation.
227 *
228 * Destroys the #GRelation, freeing all memory allocated. However, it
229 * does not free memory allocated for the tuple data, so you should
230 * free that first if appropriate.
231 *
232 * Deprecated: 2.26: Rarely used API
233 **/
234 void
235 g_relation_destroy (GRelation *relation)
236 {
237 gint i;
238  
239 if (relation)
240 {
241 for (i = 0; i < relation->fields; i += 1)
242 {
243 if (relation->hashed_tuple_tables[i])
244 {
245 g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);
246 g_hash_table_destroy (relation->hashed_tuple_tables[i]);
247 }
248 }
249  
250 g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);
251 g_hash_table_destroy (relation->all_tuples);
252  
253 g_free (relation->hashed_tuple_tables);
254 g_free (relation);
255 }
256 }
257  
258 /**
259 * g_relation_index:
260 * @relation: a #GRelation.
261 * @field: the field to index, counting from 0.
262 * @hash_func: a function to produce a hash value from the field data.
263 * @key_equal_func: a function to compare two values of the given field.
264 *
265 * Creates an index on the given field. Note that this must be called
266 * before any records are added to the #GRelation.
267 *
268 * Deprecated: 2.26: Rarely used API
269 **/
270 void
271 g_relation_index (GRelation *relation,
272 gint field,
273 GHashFunc hash_func,
274 GEqualFunc key_equal_func)
275 {
276 g_return_if_fail (relation != NULL);
277  
278 g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);
279  
280 relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);
281 }
282  
283 /**
284 * g_relation_insert:
285 * @relation: a #GRelation.
286 * @...: the fields of the record to add. These must match the
287 * number of fields in the #GRelation, and of type #gpointer
288 * or #gconstpointer.
289 *
290 * Inserts a record into a #GRelation.
291 *
292 * Deprecated: 2.26: Rarely used API
293 **/
294 void
295 g_relation_insert (GRelation *relation,
296 ...)
297 {
298 gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
299 va_list args;
300 gint i;
301  
302 va_start (args, relation);
303  
304 for (i = 0; i < relation->fields; i += 1)
305 tuple[i] = va_arg (args, gpointer);
306  
307 va_end (args);
308  
309 g_hash_table_insert (relation->all_tuples, tuple, tuple);
310  
311 relation->count += 1;
312  
313 for (i = 0; i < relation->fields; i += 1)
314 {
315 GHashTable *table;
316 gpointer key;
317 GHashTable *per_key_table;
318  
319 table = relation->hashed_tuple_tables[i];
320  
321 if (table == NULL)
322 continue;
323  
324 key = tuple[i];
325 per_key_table = g_hash_table_lookup (table, key);
326  
327 if (per_key_table == NULL)
328 {
329 per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));
330 g_hash_table_insert (table, key, per_key_table);
331 }
332  
333 g_hash_table_insert (per_key_table, tuple, tuple);
334 }
335 }
336  
337 static void
338 g_relation_delete_tuple (gpointer tuple_key,
339 gpointer tuple_value,
340 gpointer user_data)
341 {
342 gpointer *tuple = (gpointer*) tuple_value;
343 GRelation *relation = (GRelation *) user_data;
344 gint j;
345  
346 g_assert (tuple_key == tuple_value);
347  
348 for (j = 0; j < relation->fields; j += 1)
349 {
350 GHashTable *one_table = relation->hashed_tuple_tables[j];
351 gpointer one_key;
352 GHashTable *per_key_table;
353  
354 if (one_table == NULL)
355 continue;
356  
357 if (j == relation->current_field)
358 /* can't delete from the table we're foreaching in */
359 continue;
360  
361 one_key = tuple[j];
362  
363 per_key_table = g_hash_table_lookup (one_table, one_key);
364  
365 g_hash_table_remove (per_key_table, tuple);
366 }
367  
368 if (g_hash_table_remove (relation->all_tuples, tuple))
369 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
370  
371 relation->count -= 1;
372 }
373  
374 /**
375 * g_relation_delete:
376 * @relation: a #GRelation.
377 * @key: the value to compare with.
378 * @field: the field of each record to match.
379 *
380 * Deletes any records from a #GRelation that have the given key value
381 * in the given field.
382 *
383 * Returns: the number of records deleted.
384 *
385 * Deprecated: 2.26: Rarely used API
386 **/
387 gint
388 g_relation_delete (GRelation *relation,
389 gconstpointer key,
390 gint field)
391 {
392 GHashTable *table;
393 GHashTable *key_table;
394 gint count;
395  
396 g_return_val_if_fail (relation != NULL, 0);
397  
398 table = relation->hashed_tuple_tables[field];
399 count = relation->count;
400  
401 g_return_val_if_fail (table != NULL, 0);
402  
403 key_table = g_hash_table_lookup (table, key);
404  
405 if (!key_table)
406 return 0;
407  
408 relation->current_field = field;
409  
410 g_hash_table_foreach (key_table, g_relation_delete_tuple, relation);
411  
412 g_hash_table_remove (table, key);
413  
414 g_hash_table_destroy (key_table);
415  
416 /* @@@ FIXME: Remove empty hash tables. */
417  
418 return count - relation->count;
419 }
420  
421 static void
422 g_relation_select_tuple (gpointer tuple_key,
423 gpointer tuple_value,
424 gpointer user_data)
425 {
426 gpointer *tuple = (gpointer*) tuple_value;
427 GRealTuples *tuples = (GRealTuples*) user_data;
428 gint stride = sizeof (gpointer) * tuples->width;
429  
430 g_assert (tuple_key == tuple_value);
431  
432 memcpy (tuples->data + (tuples->len * tuples->width),
433 tuple,
434 stride);
435  
436 tuples->len += 1;
437 }
438  
439 /**
440 * g_relation_select:
441 * @relation: a #GRelation.
442 * @key: the value to compare with.
443 * @field: the field of each record to match.
444 *
445 * Returns all of the tuples which have the given key in the given
446 * field. Use g_tuples_index() to access the returned records. The
447 * returned records should be freed with g_tuples_destroy().
448 *
449 * Returns: the records (tuples) that matched.
450 *
451 * Deprecated: 2.26: Rarely used API
452 **/
453 GTuples*
454 g_relation_select (GRelation *relation,
455 gconstpointer key,
456 gint field)
457 {
458 GHashTable *table;
459 GHashTable *key_table;
460 GRealTuples *tuples;
461 gint count;
462  
463 g_return_val_if_fail (relation != NULL, NULL);
464  
465 table = relation->hashed_tuple_tables[field];
466  
467 g_return_val_if_fail (table != NULL, NULL);
468  
469 tuples = g_new0 (GRealTuples, 1);
470 key_table = g_hash_table_lookup (table, key);
471  
472 if (!key_table)
473 return (GTuples*)tuples;
474  
475 count = g_relation_count (relation, key, field);
476  
477 tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);
478 tuples->width = relation->fields;
479  
480 g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
481  
482 g_assert (count == tuples->len);
483  
484 return (GTuples*)tuples;
485 }
486  
487 /**
488 * g_relation_count:
489 * @relation: a #GRelation.
490 * @key: the value to compare with.
491 * @field: the field of each record to match.
492 *
493 * Returns the number of tuples in a #GRelation that have the given
494 * value in the given field.
495 *
496 * Returns: the number of matches.
497 *
498 * Deprecated: 2.26: Rarely used API
499 **/
500 gint
501 g_relation_count (GRelation *relation,
502 gconstpointer key,
503 gint field)
504 {
505 GHashTable *table;
506 GHashTable *key_table;
507  
508 g_return_val_if_fail (relation != NULL, 0);
509  
510 table = relation->hashed_tuple_tables[field];
511  
512 g_return_val_if_fail (table != NULL, 0);
513  
514 key_table = g_hash_table_lookup (table, key);
515  
516 if (!key_table)
517 return 0;
518  
519 return g_hash_table_size (key_table);
520 }
521  
522 /**
523 * g_relation_exists:
524 * @relation: a #GRelation.
525 * @...: the fields of the record to compare. The number must match
526 * the number of fields in the #GRelation.
527 *
528 * Returns %TRUE if a record with the given values exists in a
529 * #GRelation. Note that the values are compared directly, so that, for
530 * example, two copies of the same string will not match.
531 *
532 * Returns: %TRUE if a record matches.
533 *
534 * Deprecated: 2.26: Rarely used API
535 **/
536 gboolean
537 g_relation_exists (GRelation *relation, ...)
538 {
539 gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
540 va_list args;
541 gint i;
542 gboolean result;
543  
544 va_start(args, relation);
545  
546 for (i = 0; i < relation->fields; i += 1)
547 tuple[i] = va_arg(args, gpointer);
548  
549 va_end(args);
550  
551 result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;
552  
553 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
554  
555 return result;
556 }
557  
558 /**
559 * g_tuples_destroy:
560 * @tuples: the tuple data to free.
561 *
562 * Frees the records which were returned by g_relation_select(). This
563 * should always be called after g_relation_select() when you are
564 * finished with the records. The records are not removed from the
565 * #GRelation.
566 *
567 * Deprecated: 2.26: Rarely used API
568 **/
569 void
570 g_tuples_destroy (GTuples *tuples0)
571 {
572 GRealTuples *tuples = (GRealTuples*) tuples0;
573  
574 if (tuples)
575 {
576 g_free (tuples->data);
577 g_free (tuples);
578 }
579 }
580  
581 /**
582 * g_tuples_index:
583 * @tuples: the tuple data, returned by g_relation_select().
584 * @index_: the index of the record.
585 * @field: the field to return.
586 *
587 * Gets a field from the records returned by g_relation_select(). It
588 * returns the given field of the record at the given index. The
589 * returned value should not be changed.
590 *
591 * Returns: the field of the record.
592 *
593 * Deprecated: 2.26: Rarely used API
594 **/
595 gpointer
596 g_tuples_index (GTuples *tuples0,
597 gint index,
598 gint field)
599 {
600 GRealTuples *tuples = (GRealTuples*) tuples0;
601  
602 g_return_val_if_fail (tuples0 != NULL, NULL);
603 g_return_val_if_fail (field < tuples->width, NULL);
604  
605 return tuples->data[index * tuples->width + field];
606 }
607  
608 /* Print
609 */
610  
611 static void
612 g_relation_print_one (gpointer tuple_key,
613 gpointer tuple_value,
614 gpointer user_data)
615 {
616 gint i;
617 GString *gstring;
618 GRelation* rel = (GRelation*) user_data;
619 gpointer* tuples = (gpointer*) tuple_value;
620  
621 gstring = g_string_new ("[");
622  
623 for (i = 0; i < rel->fields; i += 1)
624 {
625 g_string_append_printf (gstring, "%p", tuples[i]);
626  
627 if (i < (rel->fields - 1))
628 g_string_append (gstring, ",");
629 }
630  
631 g_string_append (gstring, "]");
632 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%s", gstring->str);
633 g_string_free (gstring, TRUE);
634 }
635  
636 static void
637 g_relation_print_index (gpointer tuple_key,
638 gpointer tuple_value,
639 gpointer user_data)
640 {
641 GRelation* rel = (GRelation*) user_data;
642 GHashTable* table = (GHashTable*) tuple_value;
643  
644 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
645  
646 g_hash_table_foreach (table,
647 g_relation_print_one,
648 rel);
649 }
650  
651 /**
652 * g_relation_print:
653 * @relation: a #GRelation.
654 *
655 * Outputs information about all records in a #GRelation, as well as
656 * the indexes. It is for debugging.
657 *
658 * Deprecated: 2.26: Rarely used API
659 **/
660 void
661 g_relation_print (GRelation *relation)
662 {
663 gint i;
664  
665 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);
666  
667 g_hash_table_foreach (relation->all_tuples,
668 g_relation_print_one,
669 relation);
670  
671 for (i = 0; i < relation->fields; i += 1)
672 {
673 if (relation->hashed_tuple_tables[i] == NULL)
674 continue;
675  
676 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);
677  
678 g_hash_table_foreach (relation->hashed_tuple_tables[i],
679 g_relation_print_index,
680 relation);
681 }
682  
683 }