Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Linked list without objects  (Read 1177 times)
0 Members and 1 Guest are viewing this topic.
Offline Jono
« Posted 2009-07-25 06:23:12 »

Here's a linked list object pool for storing int values. It avoids using objects to represent linked list nodes, so it keeps memory use to a minimum. It's singly-linked, and the arrays for next node and stored values are interleaved for cache friendliness.

I've been using it to splat render 1 million particles and it's worked nicely for me. On the off chance that someone else might find it useful I thought I'd post it here.

Using it looks like:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
LinkedListPool listPool = new LinkedListPool(1000000);
int list = listPool.getNewList(1); //gets a list with a single node storing the value 1
int last = list; //last will point to the end of the list
for(int i = 2; i < 10; i++)
   last = listPool.insertAfter(last,i); //adds a new node to the end of the list

while(list > 0){ //nodes that are 0 or less are empty
   int value = listPool.getValue(list);
   System.out.print(value+",");
   list = listPool.nextNode(list);
}
System.out.println();
//prints "1,2,3,4,5,6,7,8,9,"


The class LinkedListPool:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
public class LinkedListPool {

   private int[] nextValues; //next nodes and values, interleaved
   
   private int[] availableStack;
   private int stackSize;
   private int stackOrderedTo;
   
   public LinkedListPool(int capacity) {
      nextValues = new int[capacity*2];
      availableStack = new int[capacity];
      stackOrderedTo = 0;
      clear();
   }
   
   /**
    * Gets a new single node list.
    * O(1)
    * @param value The value for the first list item
    * @return The node in the new list
    */

   public int getNewList(int value) {
      stackSize--;
      int newNode = availableStack[stackSize];
      nextValues[newNode] = -1;
      nextValues[newNode+1] = value;
      return newNode;
   }
   
   /**
    * Clears all lists.
    * Number of operations = lowest ID of all nodes deleted since last clear.
    */

   public void clear() {
      for(int i = stackOrderedTo; i < availableStack.length; i++)
         availableStack[i] = i*2;
     
      stackSize = availableStack.length;
      stackOrderedTo = availableStack.length;
   }
   
   /**
    * Whether the pool has run out of nodes or not.
    * O(1)
    * @return
    */

   public boolean isEmpty() {
      return stackSize < 1; //don't use 0th entry
   }
   
   /**
    * Starts a new list by attaching to the front of node.
    * Take care. Node ought not be in the middle of an existing list.
    * O(1)
    * @param node The first node in a list.
    * @param insertValue The value to insert
    * @return The new first node in the list.
    */

   public int insertAtFront(int node, int insertValue) {
      int newNode = availableStack[stackSize-1];
      stackSize--;
      nextValues[newNode] = node;
      nextValues[newNode+1] = insertValue;
      return newNode;
   }
   
   /**
    * Inserts an item into a list after the given node.
    * O(1)
    * @param node The node to add an item after
    * @param insertValue The value to insert
    * @return The new node.
    */

   public int insertAfter(int node, int insertValue) {
      int newNode = availableStack[stackSize-1];
      stackSize--;
      nextValues[newNode] = nextValues[node];
      nextValues[node] = newNode;
      nextValues[newNode+1] = insertValue;
      return newNode;
   }
   
   /**
    * Appends to the end of the list that this node belongs to.
    * O(listLength)
    * @param node Any node in the list.
    * @param appendValue The value to append
    * @return The new node.
    */

   public int append(int node, int appendValue) {
      while(nextValues[node] > 0) node = nextValues[node];
      int newNode = availableStack[stackSize-1];
      stackSize--;
      nextValues[newNode] = -1;
      nextValues[node] = newNode;
      nextValues[newNode+1] = appendValue;
      return newNode;
   }
   
   /**
    * Deletes a node, given its predecessor
    * O(1)
    * @param prevNode The node before the node to delete
    * @param node The node to delete
    */

   public void delete(int prevNode, int node) {
      nextValues[prevNode] = nextValues[node];
      availableStack[stackSize] = node;
      stackOrderedTo = Math.min(stackOrderedTo,stackSize);
      stackSize++;
   }
   
   /**
    * Deletes a node, and any nodes after this in the list.
    * O(listLength)
    * @param prevNode
    * @param node
    */

   public void cropList(int prevNode, int node) {
      nextValues[prevNode] = -1;
      stackOrderedTo = Math.min(stackOrderedTo,stackSize);
      while(node > 0) {
         availableStack[stackSize] = node;
         stackSize++;
         node = nextValues[node];
      }
   }
   
   /**
    * Gets the next node.
    * O(1)
    * @param node The node who's successor is wanted
    * @return The next node in the list, -1 or 0 indicate no next node.
    */

   public int nextNode(int node) {
      return nextValues[node];
   }
   
   /**
    * Gets the int value associated with a node
    * O(1)
    * @param node The node to get a value for
    * @return The value
    */

   public int getValue(int node) {
      return nextValues[node+1];
   }
   
   /**
    * Sets the value for a node
    * O(1)
    * @param node
    * @param value
    */

   public void setValue(int node, int value) {
      nextValues[node+1] = value;
   }
   
   /**
    * Increases size to 1.5x current capacity.
    * O(poolSize)
    * If the pool is not empty this does nothing.
    */

   public void resize() {
      if(!isEmpty()) return;
      int newSize = (availableStack.length*3)/2;

      int[] newNextValues = new int[newSize*2];

      System.arraycopy(nextValues,0,newNextValues,0,nextValues.length);
     
      int[] newAvailable = new int[newSize];
      System.arraycopy(availableStack,0,newAvailable,newAvailable.length-availableStack.length,availableStack.length);
      for(int i = 0; i < newSize-availableStack.length; i++)
         newAvailable[i] = (availableStack.length+i)*2;

      stackSize = newSize-availableStack.length;
      stackOrderedTo += stackSize;
      nextValues = newNextValues;
      availableStack = newAvailable;
   }
}
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (30 views)
2014-12-15 09:26:44

Mr.CodeIt (20 views)
2014-12-14 19:50:38

BurntPizza (42 views)
2014-12-09 22:41:13

BurntPizza (76 views)
2014-12-08 04:46:31

JscottyBieshaar (37 views)
2014-12-05 12:39:02

SHC (51 views)
2014-12-03 16:27:13

CopyableCougar4 (49 views)
2014-11-29 21:32:03

toopeicgaming1999 (115 views)
2014-11-26 15:22:04

toopeicgaming1999 (105 views)
2014-11-26 15:20:36

toopeicgaming1999 (31 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!