X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytreehash_list2.h;h=b15ae5b1ab9104dc9c417f6830adca33b005d8c3;hb=0e1c6ff93f27c939ba9e0df945b16ef98eaaeef1;hp=4e22bb7c07ff3632e304ac940bc08a691e54bcf2;hpb=57fdfd3f8ec62b105c53bcdf6f127c35c7fe7391;p=gnulib.git diff --git a/lib/gl_anytreehash_list2.h b/lib/gl_anytreehash_list2.h index 4e22bb7c0..b15ae5b1a 100644 --- a/lib/gl_anytreehash_list2.h +++ b/lib/gl_anytreehash_list2.h @@ -1,5 +1,5 @@ /* Sequential list data type implemented by a hash table with a binary tree. - Copyright (C) 2006-2007 Free Software Foundation, Inc. + Copyright (C) 2006-2007, 2009-2012 Free Software Foundation, Inc. Written by Bruno Haible , 2006. This program is free software: you can redistribute it and/or modify @@ -19,10 +19,10 @@ static gl_list_node_t gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index, - const void *elt) + const void *elt) { if (!(start_index <= end_index - && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) /* Invalid arguments. */ abort (); { @@ -36,91 +36,91 @@ gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index, if (list->base.allow_duplicates) { - for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next) - if (entry->hashcode == hashcode) - { - if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) - { - /* An entry representing multiple nodes. */ - gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; - /* The first node is interesting. */ - gl_list_node_t node = gl_oset_first (nodes); - if (equals != NULL ? equals (elt, node->value) : elt == node->value) - { - /* All nodes in the entry are equal to the given ELT. */ - if (start_index == 0) - { - /* We have to return only the one at the minimal - position, and this is the first one in the ordered - set. */ - if (end_index == list->root->branch_size - || node_position (node) < end_index) - return node; - } - else - { - /* We have to return only the one at the minimal - position >= start_index. */ - const void *elt; - if (gl_oset_search_atleast (nodes, - compare_position_threshold, - (void *)(uintptr_t)start_index, - &elt)) - { - node = (gl_list_node_t) elt; - if (end_index == list->root->branch_size - || node_position (node) < end_index) - return node; - } - } - break; - } - } - else - { - /* An entry representing a single node. */ - gl_list_node_t node = (struct gl_list_node_impl *) entry; - if (equals != NULL ? equals (elt, node->value) : elt == node->value) - { - bool position_in_bounds; - if (start_index == 0 && end_index == list->root->branch_size) - position_in_bounds = true; - else - { - size_t position = node_position (node); - position_in_bounds = - (position >= start_index && position < end_index); - } - if (position_in_bounds) - return node; - break; - } - } - } + for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next) + if (entry->hashcode == hashcode) + { + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) + { + /* An entry representing multiple nodes. */ + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + /* The first node is interesting. */ + gl_list_node_t node = gl_oset_first (nodes); + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + { + /* All nodes in the entry are equal to the given ELT. */ + if (start_index == 0) + { + /* We have to return only the one at the minimal + position, and this is the first one in the ordered + set. */ + if (end_index == list->root->branch_size + || node_position (node) < end_index) + return node; + } + else + { + /* We have to return only the one at the minimal + position >= start_index. */ + const void *elt; + if (gl_oset_search_atleast (nodes, + compare_position_threshold, + (void *)(uintptr_t)start_index, + &elt)) + { + node = (gl_list_node_t) elt; + if (end_index == list->root->branch_size + || node_position (node) < end_index) + return node; + } + } + break; + } + } + else + { + /* An entry representing a single node. */ + gl_list_node_t node = (struct gl_list_node_impl *) entry; + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + { + bool position_in_bounds; + if (start_index == 0 && end_index == list->root->branch_size) + position_in_bounds = true; + else + { + size_t position = node_position (node); + position_in_bounds = + (position >= start_index && position < end_index); + } + if (position_in_bounds) + return node; + break; + } + } + } } else { - /* If no duplicates are allowed, multiple nodes are not needed. */ - for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next) - if (entry->hashcode == hashcode) - { - gl_list_node_t node = (struct gl_list_node_impl *) entry; - if (equals != NULL ? equals (elt, node->value) : elt == node->value) - { - bool position_in_bounds; - if (start_index == 0 && end_index == list->root->branch_size) - position_in_bounds = true; - else - { - size_t position = node_position (node); - position_in_bounds = - (position >= start_index && position < end_index); - } - if (position_in_bounds) - return node; - break; - } - } + /* If no duplicates are allowed, multiple nodes are not needed. */ + for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next) + if (entry->hashcode == hashcode) + { + gl_list_node_t node = (struct gl_list_node_impl *) entry; + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + { + bool position_in_bounds; + if (start_index == 0 && end_index == list->root->branch_size) + position_in_bounds = true; + else + { + size_t position = node_position (node); + position_in_bounds = + (position >= start_index && position < end_index); + } + if (position_in_bounds) + return node; + break; + } + } } return NULL; @@ -129,7 +129,7 @@ gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index, static size_t gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, - const void *elt) + const void *elt) { gl_list_node_t node = gl_tree_search_from_to (list, start_index, end_index, elt); @@ -149,24 +149,24 @@ gl_tree_list_free (gl_list_t list) size_t i; for (i = list->table_size; i > 0; ) - { - gl_hash_entry_t entry = list->table[--i]; + { + gl_hash_entry_t entry = list->table[--i]; - while (entry != NULL) - { - gl_hash_entry_t next = entry->hash_next; + while (entry != NULL) + { + gl_hash_entry_t next = entry->hash_next; - if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) - { - gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) + { + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; - gl_oset_free (nodes); - free (entry); - } + gl_oset_free (nodes); + free (entry); + } - entry = next; - } - } + entry = next; + } + } } /* Iterate across all elements in post-order. */ @@ -177,34 +177,34 @@ gl_tree_list_free (gl_list_t list) for (;;) { - /* Descend on left branch. */ - for (;;) - { - if (node == NULL) - break; - stack_ptr->node = node; - stack_ptr->rightp = false; - node = node->left; - stack_ptr++; - } - /* Climb up again. */ - for (;;) - { - if (stack_ptr == &stack[0]) - goto done_iterate; - stack_ptr--; - node = stack_ptr->node; - if (!stack_ptr->rightp) - break; - /* Free the current node. */ - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (node->value); - free (node); - } - /* Descend on right branch. */ - stack_ptr->rightp = true; - node = node->right; - stack_ptr++; + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto done_iterate; + stack_ptr--; + node = stack_ptr->node; + if (!stack_ptr->rightp) + break; + /* Free the current node. */ + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; } } done_iterate: