X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytreehash_list1.h;h=5caf9425d3c927dbc756b36b1f4fbf492350531b;hb=b1eaa47f003b6a9a227a56967e2c650515a6432b;hp=fac02b6aed32dc47965eb10942d5a133e75a2c6d;hpb=935e9f0bda3d20a28516e3e369946fe6fbe60043;p=gnulib.git diff --git a/lib/gl_anytreehash_list1.h b/lib/gl_anytreehash_list1.h index fac02b6ae..5caf9425d 100644 --- a/lib/gl_anytreehash_list1.h +++ b/lib/gl_anytreehash_list1.h @@ -1,11 +1,11 @@ /* Sequential list data type implemented by a hash table with a binary tree. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2007, 2009-2010 Free Software Foundation, Inc. Written by Bruno Haible , 2006. - This program is free software; you can redistribute it and/or modify + This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -13,8 +13,7 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software Foundation, - Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + along with this program. If not, see . */ /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */ @@ -52,14 +51,14 @@ node_position (gl_list_node_t node) gl_list_node_t parent = node->parent; if (parent == NULL) - return position; + return position; /* position is now relative to the subtree of node. */ if (parent->right == node) - { - position += 1; - if (parent->left != NULL) - position += parent->left->branch_size; - } + { + position += 1; + if (parent->left != NULL) + position += parent->left->branch_size; + } /* position is now relative to the subtree of parent. */ node = parent; } @@ -75,7 +74,7 @@ compare_by_position (const void *x1, const void *x2) size_t position2 = node_position (node2); return (position1 > position2 ? 1 : - position1 < position2 ? -1 : 0); + position1 < position2 ? -1 : 0); } /* Compares a node's position in the tree with a given threshold. */ @@ -102,11 +101,12 @@ gl_oset_first (gl_oset_t set) /* Add a node to the hash table structure. If duplicates are allowed, this function performs in average time - O((log n)^2): gl_oset_add may need to add an element to an ordered set of - size O(n), needing O(log n) comparison function calls. The comparison + O((log n)^2): gl_oset_nx_add may need to add an element to an ordered set + of size O(n), needing O(log n) comparison function calls. The comparison function is compare_by_position, which is O(log n) worst-case. - If duplicates are forbidden, this function is O(1). */ -static void + If duplicates are forbidden, this function is O(1). + Return 0 upon success, -1 upon out-of-memory. */ +static int add_to_bucket (gl_list_t list, gl_list_node_t new_node) { size_t bucket = new_node->h.hashcode % list->table_size; @@ -120,60 +120,75 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node) gl_hash_entry_t *entryp; for (entryp = &list->table[bucket]; *entryp != NULL; entryp = &(*entryp)->hash_next) - { - gl_hash_entry_t entry = *entryp; + { + gl_hash_entry_t entry = *entryp; - 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; - /* Only the first node is interesting. */ - gl_list_node_t node = gl_oset_first (nodes); - if (equals != NULL ? equals (value, node->value) : value == node->value) - { - /* Found already multiple nodes with the same value. - Add the new_node to it. */ - gl_oset_add (nodes, new_node); - return; - } - } - else - { - /* An entry representing a single node. */ - gl_list_node_t node = (struct gl_list_node_impl *) entry; - if (equals != NULL ? equals (value, node->value) : value == node->value) - { - /* Found already a node with the same value. Turn it - into an ordered set, and add new_node to it. */ - gl_oset_t nodes; - struct gl_multiple_nodes *multi_entry; + 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; + /* Only the first node is interesting. */ + gl_list_node_t node = gl_oset_first (nodes); + if (equals != NULL ? equals (value, node->value) : value == node->value) + { + /* Found already multiple nodes with the same value. + Add the new_node to it. */ + return gl_oset_nx_add (nodes, new_node); + } + } + else + { + /* An entry representing a single node. */ + gl_list_node_t node = (struct gl_list_node_impl *) entry; + if (equals != NULL ? equals (value, node->value) : value == node->value) + { + /* Found already a node with the same value. Turn it + into an ordered set, and add new_node to it. */ + gl_oset_t nodes; + struct gl_multiple_nodes *multi_entry; - nodes = - gl_oset_create_empty (OSET_TREE_FLAVOR, - compare_by_position); + nodes = + gl_oset_nx_create_empty (OSET_TREE_FLAVOR, + compare_by_position, NULL); + if (nodes == NULL) + return -1; - gl_oset_add (nodes, node); - gl_oset_add (nodes, new_node); + if (gl_oset_nx_add (nodes, node) < 0) + goto fail; + if (gl_oset_nx_add (nodes, new_node) < 0) + goto fail; - multi_entry = - (struct gl_multiple_nodes *) xmalloc (sizeof (struct gl_multiple_nodes)); - multi_entry->h.hash_next = entry->hash_next; - multi_entry->h.hashcode = entry->hashcode; - multi_entry->magic = MULTIPLE_NODES_MAGIC; - multi_entry->nodes = nodes; - *entryp = &multi_entry->h; - return; - } - } - } - } + multi_entry = + (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes)); + if (multi_entry == NULL) + goto fail; + multi_entry->h.hash_next = entry->hash_next; + multi_entry->h.hashcode = entry->hashcode; + multi_entry->magic = MULTIPLE_NODES_MAGIC; + multi_entry->nodes = nodes; + *entryp = &multi_entry->h; + return 0; + + fail: + gl_oset_free (nodes); + return -1; + } + } + } + } } /* If no duplicates are allowed, multiple nodes are not needed. */ new_node->h.hash_next = list->table[bucket]; list->table[bucket] = &new_node->h; + return 0; } +/* Tell GCC that the likely return value is 0. */ +#if __GNUC__ >= 3 +# define add_to_bucket(list,node) \ + __builtin_expect ((add_to_bucket) (list, node), 0) +#endif /* Remove a node from the hash table structure. If duplicates are allowed, this function performs in average time @@ -194,45 +209,45 @@ remove_from_bucket (gl_list_t list, gl_list_node_t old_node) gl_hash_entry_t *entryp; for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next) - { - gl_hash_entry_t entry = *entryp; + { + gl_hash_entry_t entry = *entryp; - if (entry == &old_node->h) - { - /* Found old_node as a single node in the bucket. Remove it. */ - *entryp = old_node->h.hash_next; - break; - } - if (entry == NULL) - /* node is not in the right bucket. Did the hash codes - change inadvertently? */ - abort (); - if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC - && entry->hashcode == hashcode) - { - /* An entry representing multiple nodes. */ - gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; - /* Only the first node is interesting. */ - gl_list_node_t node = gl_oset_first (nodes); - if (equals != NULL ? equals (value, node->value) : value == node->value) - { - /* Found multiple nodes with the same value. - old_node must be one of them. Remove it. */ - if (!gl_oset_remove (nodes, old_node)) - abort (); - if (gl_oset_size (nodes) == 1) - { - /* Replace a one-element set with a single node. */ - node = gl_oset_first (nodes); - node->h.hash_next = entry->hash_next; - *entryp = &node->h; - gl_oset_free (nodes); - free (entry); - } - break; - } - } - } + if (entry == &old_node->h) + { + /* Found old_node as a single node in the bucket. Remove it. */ + *entryp = old_node->h.hash_next; + break; + } + if (entry == NULL) + /* node is not in the right bucket. Did the hash codes + change inadvertently? */ + abort (); + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC + && entry->hashcode == hashcode) + { + /* An entry representing multiple nodes. */ + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + /* Only the first node is interesting. */ + gl_list_node_t node = gl_oset_first (nodes); + if (equals != NULL ? equals (value, node->value) : value == node->value) + { + /* Found multiple nodes with the same value. + old_node must be one of them. Remove it. */ + if (!gl_oset_remove (nodes, old_node)) + abort (); + if (gl_oset_size (nodes) == 1) + { + /* Replace a one-element set with a single node. */ + node = gl_oset_first (nodes); + node->h.hash_next = entry->hash_next; + *entryp = &node->h; + gl_oset_free (nodes); + free (entry); + } + break; + } + } + } } else { @@ -240,23 +255,24 @@ remove_from_bucket (gl_list_t list, gl_list_node_t old_node) gl_hash_entry_t *entryp; for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next) - { - if (*entryp == &old_node->h) - { - *entryp = old_node->h.hash_next; - break; - } - if (*entryp == NULL) - /* node is not in the right bucket. Did the hash codes - change inadvertently? */ - abort (); - } + { + if (*entryp == &old_node->h) + { + *entryp = old_node->h.hash_next; + break; + } + if (*entryp == NULL) + /* node is not in the right bucket. Did the hash codes + change inadvertently? */ + abort (); + } } } /* Build up the hash table during initialization: Store all the nodes of - list->root in the hash table. */ -static inline void + list->root in the hash table. + Return 0 upon success, -1 upon out-of-memory. */ +static inline int add_nodes_to_buckets (gl_list_t list) { /* Iterate across all nodes. */ @@ -268,33 +284,75 @@ add_nodes_to_buckets (gl_list_t list) { /* Descend on left branch. */ for (;;) - { - if (node == NULL) - break; - stack_ptr->node = node; - stack_ptr->rightp = false; - node = node->left; - stack_ptr++; - } + { + 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]) - return; - stack_ptr--; - if (!stack_ptr->rightp) - break; - } + { + if (stack_ptr == &stack[0]) + goto done; + stack_ptr--; + if (!stack_ptr->rightp) + break; + } node = stack_ptr->node; /* Add the current node to the hash table. */ node->h.hashcode = - (list->base.hashcode_fn != NULL - ? list->base.hashcode_fn (node->value) - : (size_t)(uintptr_t) node->value); - add_to_bucket (list, node); + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + if (add_to_bucket (list, node) < 0) + goto fail; /* Descend on right branch. */ stack_ptr->rightp = true; node = node->right; stack_ptr++; } + done: + return 0; + + fail: + /* Undo everything. */ + for (;;) + { + /* Descend on left branch. */ + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + /* Descend on right branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto fail_done; + stack_ptr--; + if (stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Remove the current node from the hash table. */ + remove_from_bucket (list, node); + } + fail_done: + return -1; } +/* Tell GCC that the likely return value is 0. */ +#if __GNUC__ >= 3 +# define add_nodes_to_buckets(list) \ + __builtin_expect ((add_nodes_to_buckets) (list), 0) +#endif