/usr/share/GNUstep/Documentation/Performance/GSSkipMutableArray.gsdoc is in libperformance-dev 0.5.0-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | <?xml version="1.0"?>
<!DOCTYPE gsdoc PUBLIC "-//GNUstep//DTD gsdoc 1.0.3//EN" "http://www.gnustep.org/gsdoc-1_0_3.dtd">
<gsdoc base="GSSkipMutableArray">
<head>
<title>GSSkipMutableArray documentation</title>
<author name="Matt Rice">
<email address="ratmice@yahoo.com">
ratmice@yahoo.com
</email>
</author>
<copy>2006 Free Software Foundation, Inc.</copy>
</head>
<body>
<front><contents /></front>
<chapter>
<heading>
Software documentation for the
NSMutableArray(GSSkipMutableArray)
category
</heading>
<category name="GSSkipMutableArray" class="NSMutableArray">
<declared>GSSkipMutableArray.h</declared>
<desc>
<p>
An NSMutableArray category to provide an NSMutableArray
instance which uses a skip list variant for it's
underlying data structure.
</p>
<p>
While a skip list is typically sorted and represents
a dictionary. the indexed skip list is sorted by index
and maintains deltas to represent the distance between
linked nodes.
</p>
<p>
The underlying data structure looks much like the
figure below:
</p>
<example>
index -> HEAD 1 2 3 4 5 6 TAIL
5| ---------------------> # ------> #
3| -----------> 2 ------> # ------> #
1| -> 1 -> 1 -> 1 -> 1 -> 1 -> # -> #
</example>
<p>
Where the numbers represent how many indexes it is to
the next node of the appropriate level. The bottom
level always points to the next node.
</p>
<p>
Finding a specific index starts at the top level,
until the current depth + the next nodes delta is
larger than wanted index, then it goes down 1 level,
and repeats until it finds the wanted index.
</p>
<p>
Addition and removal of indexes requires an update
of the deltas of nodes which begin before, and end after
the wanted index, these are the places where it goes
down a level.
</p>
<p>
The rationale behind it was where a linked list based
mutable array will quickly add and remove elements,
it may perform poorly at accessing any random index
(because it must traverse the entire list to get
to the index).
</p>
<p>
While a C array based mutable array will perform good
at random index access it may perform poorly at adding
and removing indexes (because it must move all items
after the altered index).
</p>
<p>
While a GSSkipMutableArray may not outperform a
linked list or a C array based mutable array at
their specific strengths, it attempts to not suffer
from either of their weaknesses, at the cost of
additional memory overhead.
</p>
</desc>
<method type="NSMutableArray*" factory="yes">
<sel>skipArray</sel>
<desc>
Creates and returns an autoreleased NSMutableArray
implemented as a skip list for rapid
insertion/deletion within very large
arrays.
</desc>
</method>
</category>
</chapter>
</body>
</gsdoc>
|