Mercurial > gnulib
view lib/gl_anyrbtree_list1.h @ 40214:452ab00796c7
Fix undefined behaviour.
* lib/bitrotate.h (rotl16, rotr16, rotl8, rotr8): Case x to
'unsigned int', to avoid shift operations on 'int'.
* lib/xmemdup0.c (xmemdup0): Don't invoke memcpy with a zero size.
* tests/test-count-leading-zeros.c (main): Use a random number that has
as many bits as TYPE, not only 2*15 or 2*31 bits.
* tests/test-count-trailing-zeros.c (main): Likewise.
* tests/test-count-one-bits.c (main): Likewise.
* tests/test-memmem.c: Don't include "null-ptr.h".
(main): Use zerosize_ptr() instead of null_ptr().
* modules/memmem-tests (Files): Remove tests/null-ptr.h.
author | Bruno Haible <bruno@clisp.org> |
---|---|
date | Sat, 09 Mar 2019 20:32:25 +0100 |
parents | b06060465f09 |
children |
line wrap: on
line source
/* Sequential list data type implemented by a binary tree. Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. 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 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 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 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, see <https://www.gnu.org/licenses/>. */ /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ /* A red-black tree is a binary tree where every node is colored black or red such that 1. The root is black. 2. No red node has a red parent. Or equivalently: No red node has a red child. 3. All paths from the root down to any NULL endpoint contain the same number of black nodes. Let's call this the "black-height" bh of the tree. It follows that every such path contains exactly bh black and between 0 and bh red nodes. (The extreme cases are a path containing only black nodes, and a path colored alternately black-red-black-red-...-black-red.) The height of the tree therefore is >= bh, <= 2*bh. */ /* -------------------------- gl_list_t Data Type -------------------------- */ /* Color of a node. */ typedef enum color { BLACK, RED } color_t; /* Concrete list node implementation, valid for this file only. */ struct gl_list_node_impl { #if WITH_HASHTABLE struct gl_hash_entry h; /* hash table entry fields; must be first */ #endif struct gl_list_node_impl *left; /* left branch, or NULL */ struct gl_list_node_impl *right; /* right branch, or NULL */ /* Parent pointer, or NULL. The parent pointer is not needed for most operations. It is needed so that a gl_list_node_t can be returned without memory allocation, on which the functions gl_list_remove_node, gl_list_add_before, gl_list_add_after can be implemented. */ struct gl_list_node_impl *parent; color_t color; /* node's color */ size_t branch_size; /* number of nodes in this branch, = branchsize(left)+branchsize(right)+1 */ const void *value; }; /* Concrete gl_list_impl type, valid for this file only. */ struct gl_list_impl { struct gl_list_impl_base base; #if WITH_HASHTABLE /* A hash table: managed as an array of collision lists. */ struct gl_hash_entry **table; size_t table_size; #endif struct gl_list_node_impl *root; /* root node or NULL */ }; /* A red-black tree of height h has a black-height bh >= ceil(h/2) and therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree of height h >= 117 would have at least 2^59 - 1 elements, and because even on 64-bit machines, sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64 this would exceed the address space of the machine. */ #define MAXHEIGHT 116