Bug 1403444 - Use templates for rb_node and rb_tree, and rename them. r?njn
--- a/memory/build/mozjemalloc.cpp
+++ b/memory/build/mozjemalloc.cpp
@@ -464,31 +464,31 @@ enum ChunkType {
ARENA_CHUNK, // used to back arena runs created by arena_t::AllocRun
HUGE_CHUNK, // used to back huge allocations (e.g. huge_malloc)
RECYCLED_CHUNK, // chunk has been stored for future use by chunk_recycle
};
/* Tree of extents. */
struct extent_node_t {
/* Linkage for the size/address-ordered tree. */
- rb_node(extent_node_t) link_szad;
+ RedBlackTreeNode<extent_node_t> link_szad;
/* Linkage for the address-ordered tree. */
- rb_node(extent_node_t) link_ad;
+ RedBlackTreeNode<extent_node_t> link_ad;
/* Pointer to the extent that this tree node is responsible for. */
void *addr;
/* Total region size. */
size_t size;
/* What type of chunk is there; used by chunk recycling code. */
ChunkType chunk_type;
};
-typedef rb_tree(extent_node_t) extent_tree_t;
+typedef RedBlackTree<extent_node_t> extent_tree_t;
/******************************************************************************/
/*
* Radix tree data structures.
*/
/*
* Size of each radix tree node (must be a power of 2). This impacts tree
@@ -519,17 +519,17 @@ struct arena_bin_t;
struct arena_chunk_map_t {
/*
* Linkage for run trees. There are two disjoint uses:
*
* 1) arena_t's tree or available runs.
* 2) arena_run_t conceptually uses this linkage for in-use non-full
* runs, rather than directly embedding linkage.
*/
- rb_node(arena_chunk_map_t) link;
+ RedBlackTreeNode<arena_chunk_map_t> link;
/*
* Run address (or size) and various flags are stored together. The bit
* layout looks like (assuming 32-bit system):
*
* ???????? ???????? ????---- -mckdzla
*
* ? : Unallocated: Run address for first/last pages, unset for internal
@@ -590,26 +590,26 @@ struct arena_chunk_map_t {
#define CHUNK_MAP_DECOMMITTED ((size_t)0x20U)
#define CHUNK_MAP_MADVISED_OR_DECOMMITTED (CHUNK_MAP_MADVISED | CHUNK_MAP_DECOMMITTED)
#define CHUNK_MAP_KEY ((size_t)0x10U)
#define CHUNK_MAP_DIRTY ((size_t)0x08U)
#define CHUNK_MAP_ZEROED ((size_t)0x04U)
#define CHUNK_MAP_LARGE ((size_t)0x02U)
#define CHUNK_MAP_ALLOCATED ((size_t)0x01U)
};
-typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t;
-typedef rb_tree(arena_chunk_map_t) arena_run_tree_t;
+typedef RedBlackTree<arena_chunk_map_t> arena_avail_tree_t;
+typedef RedBlackTree<arena_chunk_map_t> arena_run_tree_t;
/* Arena chunk header. */
struct arena_chunk_t {
/* Arena that owns the chunk. */
arena_t *arena;
/* Linkage for the arena's tree of dirty chunks. */
- rb_node(arena_chunk_t) link_dirty;
+ RedBlackTreeNode<arena_chunk_t> link_dirty;
#ifdef MALLOC_DOUBLE_PURGE
/* If we're double-purging, we maintain a linked list of chunks which
* have pages which have been madvise(MADV_FREE)'d but not explicitly
* purged.
*
* We're currently lazy and don't remove a chunk from this list when
* all its madvised pages are recommitted. */
@@ -617,17 +617,17 @@ struct arena_chunk_t {
#endif
/* Number of dirty pages. */
size_t ndirty;
/* Map of pages within chunk that keeps track of free/large/small. */
arena_chunk_map_t map[1]; /* Dynamically sized. */
};
-typedef rb_tree(arena_chunk_t) arena_chunk_tree_t;
+typedef RedBlackTree<arena_chunk_t> arena_chunk_tree_t;
#ifdef MALLOC_DOUBLE_PURGE
namespace mozilla {
template<>
struct GetDoublyLinkedListElement<arena_chunk_t>
{
static DoublyLinkedListElement<arena_chunk_t>& Get(arena_chunk_t* aThis)
@@ -696,17 +696,17 @@ struct arena_bin_t {
struct arena_t {
#if defined(MOZ_DEBUG) || defined(MOZ_DIAGNOSTIC_ASSERT_ENABLED)
uint32_t mMagic;
# define ARENA_MAGIC 0x947d3d24
#endif
arena_id_t mId;
/* Linkage for the tree of arenas by id. */
- rb_node(arena_t) mLink;
+ RedBlackTreeNode<arena_t> mLink;
/* All operations on this arena require that lock be locked. */
malloc_spinlock_t mLock;
arena_stats_t mStats;
private:
/* Tree of dirty-page-containing chunks this arena manages. */
@@ -818,17 +818,17 @@ public:
bool RallocGrowLarge(arena_chunk_t* aChunk, void* aPtr, size_t aSize, size_t aOldSize);
void Purge(bool aAll);
void HardPurge();
};
-typedef rb_tree(arena_t) arena_tree_t;
+typedef RedBlackTree<arena_t> arena_tree_t;
/******************************************************************************/
/*
* Data.
*/
/*
* When MALLOC_STATIC_SIZES is defined most of the parameters
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -1,9 +1,16 @@
-/******************************************************************************
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/*
+ * Portions of this file were originally under the following license:
*
* Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
@@ -63,28 +70,30 @@
* that treat the first argument specially.
*
******************************************************************************/
#ifndef RB_H_
#define RB_H_
/* Node structure. */
-#define rb_node(a_type) \
-struct { \
- a_type *rbn_left; \
- a_type *rbn_right_red; \
-}
+template <typename T>
+struct RedBlackTreeNode
+{
+ T* rbn_left;
+ T* rbn_right_red;
+};
/* Root structure. */
-#define rb_tree(a_type) \
-struct { \
- a_type *rbt_root; \
- a_type rbt_nil; \
-}
+template <typename T>
+struct RedBlackTree
+{
+ T* rbt_root;
+ T rbt_nil;
+};
/* Left accessors. */
#define rbp_left_get(a_type, a_field, a_node) \
((a_node)->a_field.rbn_left)
#define rbp_left_set(a_type, a_field, a_node, a_left) do { \
(a_node)->a_field.rbn_left = a_left; \
} while (0)