I was updating the manual for RakNet and was reminded of how many data structures I’ve written for it.
From the manual:
DS_BinarySearchTree.h – Binary search tree, and an AVL balanced binary search tree.
DS_BPlusTree.h – BPlus tree for fast lookup, delete, and insert.
DS_BytePool.h – Returns data blocks at certain size thresholds to reduce memory fragmentation.
DS_ByteQueue.h – A queue specialized for reading and writing bytes.
DS_Heap.h – Heap data structure, includes both minheap and maxheap.
DS_HuffmanEncodingTree.h – Huffman encoding tree, used to find the minimal bitwise representation given a frequency table.
DS_HuffmanEncodingTreeFactory.h – Creates instances of the Huffman encoding tree.
DS_HuffmanEncodingTreeNode.h – Node in the Huffman encoding tree.
DS_LinkedList.h – Standard linked list.
DS_List.h – Dynamic array (sometimes improperly called a vector). Also doubles as a stack.
DS_Map.h – (Associative array) Ordered list with an per-element sort key.
DS_MemoryPool.h – Allocate and free reused instances of a fixed size structure, used to reduce memory fragmentation.
DS_OrderedChannelHeap.h – Maxheap which returns a node based on the relative weight of the node’s associated channel. Used for task scheduling with priorities.
DS_OrderedList.h – List ordered by an arbitrary key via quicksort.
DS_Queue.h – Standard queue implemented with an array
DS_QueueLinkedList.h – Standard queue implemented with a linked list
DS_RangeList.h – Stores a list of numerical values, and when the values are sequential, represents them as a range rather than individual elements. Useful when storing many values that are usually sequential.
DS_Table.h – Table with columns and rows, and operations on that table.
DS_Tree.h – Noncyclic graph
DS_WeightedGraph.h – Graph with weighted edges, used for routing via Dijkstra’s algorithm
Data structures is one of the few classes in college that has a significant real-world bearing. It’s one of the cornerstones of good design and optimization.
A few times I’ve been asked why I don’t just use STL.
1. STL can cause linker errors
2. STL uses exceptions.
3. STL doesn’t have every feature I need.
4. I don’t know how well STL is optimized, but I know exactly how well my code is optimized.
5. In college I was confused for months before I figured out when people said ‘vector’ they meant ‘dynamic array.’ It became a pet-peeve of mine.
6. In college I started writing my own data structures before I knew STL existed. None of my classes ever covered it And once I started I had momentum to keep going.
5. It’s something I find interesting and enjoy writing.
Aside from STL, of the game companies I’ve worked at, I’ve never seen any of them with as sophisticated a set of data structures as what I have in RakNet. When you need to process and track 30,000 messages a second you need heavy duty data structures like my memory-pool optimized B+ tree. Being able to support 30,000 messages vs. your standard game’s 20-30 messages a second is part of the polish you get with a dedicated mature library.