Mercurial > hg > octave-shane > gnulib-hg

comparison lib/gl_anytreehash_list2.h @ 7405:0de49c40e105

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add searching operations, limited to a subsequence of the list.
author Bruno Haible <bruno@clisp.org>
date Thu, 05 Oct 2006 12:45:16 +0000
parents de9a21fc207a
children c9738ed4c499
comparison
equal deleted inserted replaced
7404:71b958155bb9 7405:0de49c40e105
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
18 18
19 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */ 19 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */
20 20
21 static gl_list_node_t 21 static gl_list_node_t
22 gl_tree_search (gl_list_t list, const void *elt) 22 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
23 const void *elt)
23 { 24 {
24 size_t hashcode = 25 if (!(start_index <= end_index
25 (list->base.hashcode_fn != NULL 26 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
26 ? list->base.hashcode_fn (elt) 27 /* Invalid arguments. */
27 : (size_t)(uintptr_t) elt); 28 abort ();
28 size_t index = hashcode % list->table_size; 29 {
29 gl_listelement_equals_fn equals = list->base.equals_fn; 30 size_t hashcode =
30 gl_hash_entry_t entry; 31 (list->base.hashcode_fn != NULL
31 32 ? list->base.hashcode_fn (elt)
32 if (list->base.allow_duplicates) 33 : (size_t)(uintptr_t) elt);
33 { 34 size_t index = hashcode % list->table_size;
34 for (entry = list->table[index]; entry != NULL; entry = entry->hash_next) 35 gl_listelement_equals_fn equals = list->base.equals_fn;
35 if (entry->hashcode == hashcode) 36 gl_hash_entry_t entry;
36 { 37
37 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) 38 if (list->base.allow_duplicates)
38 { 39 {
39 /* An entry representing multiple nodes. */ 40 for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
40 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; 41 if (entry->hashcode == hashcode)
41 /* Only the first node is interesting. */ 42 {
42 gl_list_node_t node = gl_oset_first (nodes); 43 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
43 if (equals != NULL ? equals (elt, node->value) : elt == node->value) 44 {
44 /* All nodes in the entry are equal to the given ELT. 45 /* An entry representing multiple nodes. */
45 But we have to return only the one at the minimal position, 46 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
46 and this is the first one in the ordered set. */ 47 /* The first node is interesting. */
47 return node; 48 gl_list_node_t node = gl_oset_first (nodes);
48 } 49 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
49 else 50 {
50 { 51 /* All nodes in the entry are equal to the given ELT. */
51 /* An entry representing a single node. */ 52 if (start_index == 0)
52 gl_list_node_t node = (struct gl_list_node_impl *) entry; 53 {
53 if (equals != NULL ? equals (elt, node->value) : elt == node->value) 54 /* We have to return only the one at the minimal
54 return node; 55 position, and this is the first one in the ordered
55 } 56 set. */
56 } 57 if (end_index == list->root->branch_size
57 } 58 || node_position (node) < end_index)
58 else 59 return node;
59 { 60 }
60 /* If no duplicates are allowed, multiple nodes are not needed. */ 61 else
61 for (entry = list->table[index]; entry != NULL; entry = entry->hash_next) 62 {
62 if (entry->hashcode == hashcode) 63 /* We have to return only the one at the minimal
63 { 64 position >= start_index. */
64 gl_list_node_t node = (struct gl_list_node_impl *) entry; 65 const void *elt;
65 if (equals != NULL ? equals (elt, node->value) : elt == node->value) 66 if (gl_oset_search_atleast (nodes,
66 return node; 67 compare_position_threshold,
67 } 68 (void *)(uintptr_t)start_index,
68 } 69 &elt))
69 70 {
70 return NULL; 71 node = (gl_list_node_t) elt;
72 if (end_index == list->root->branch_size
73 || node_position (node) < end_index)
74 return node;
75 }
76 }
77 break;
78 }
79 }
80 else
81 {
82 /* An entry representing a single node. */
83 gl_list_node_t node = (struct gl_list_node_impl *) entry;
84 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
85 {
86 bool position_in_bounds;
87 if (start_index == 0 && end_index == list->root->branch_size)
88 position_in_bounds = true;
89 else
90 {
91 size_t position = node_position (node);
92 position_in_bounds =
93 (position >= start_index && position < end_index);
94 }
95 if (position_in_bounds)
96 return node;
97 break;
98 }
99 }
100 }
101 }
102 else
103 {
104 /* If no duplicates are allowed, multiple nodes are not needed. */
105 for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
106 if (entry->hashcode == hashcode)
107 {
108 gl_list_node_t node = (struct gl_list_node_impl *) entry;
109 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
110 {
111 bool position_in_bounds;
112 if (start_index == 0 && end_index == list->root->branch_size)
113 position_in_bounds = true;
114 else
115 {
116 size_t position = node_position (node);
117 position_in_bounds =
118 (position >= start_index && position < end_index);
119 }
120 if (position_in_bounds)
121 return node;
122 break;
123 }
124 }
125 }
126
127 return NULL;
128 }
71 } 129 }
72 130
73 static size_t 131 static size_t
74 gl_tree_indexof (gl_list_t list, const void *elt) 132 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
133 const void *elt)
75 { 134 {
76 gl_list_node_t node = gl_tree_search (list, elt); 135 gl_list_node_t node =
136 gl_tree_search_from_to (list, start_index, end_index, elt);
77 137
78 if (node != NULL) 138 if (node != NULL)
79 return node_position (node); 139 return node_position (node);
80 else 140 else
81 return (size_t)(-1); 141 return (size_t)(-1);