--- 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)