[0T} Extended smart pointers
Borneq
borucki.andrzej at gmail.com
Tue Mar 22 14:41:41 UTC 2022
Hi, I search place to discuss about graph algorithms.
I start creating experimental language with extended smart
pointers.
Goal: while smart pointers in C++ and pointers in Swift need
carefully handle with shared and weak pointers and knowing where
using weak instead shared, here should be language which disabled
making leaking code by developer; like garbage collector but
using reference counting and other fields.
Sample program in Smart language:
```csharp
public class Elem {
internal Elem next;
string name;
public Elem(string name)
{
this.name = name;
}
~Elem() {
Console.Printf("delete %s",name);
}
}
public static class Program
{
static void Main()
{
Elem a = new Elem(“Apartment”);
Elem b = new Elem(“Person”);
a.next = b;
b.next = a;
}
}
```
This should be translated to C++ code:
```c++
void main() {
Shadow shadow;
Elem* a = new Elem("Apartment");
Elem* b = new Elem("Person");
link_assign(a,&shadow,(Object**)&a->next, b);
link_assign(b,&shadow,(Object**)&b->next, a);
try_release(&shadow, b);
try_release(&shadow, a);
}
```
In C++ is struct Elem which inherits from Object from runtime.
Is defined:
```C++
struct Object {
int ref_count;
int weak_count;
int out_count;
int link_number;
Object() {
ref_count = 1;
out_count = 0;
link_number = 0;
}
virtual ~Object(){}
};
```
ref_count is number links to object, in some cases finding
automatic , ref_count will not increment, but for releasing
purpose is also weak_count.
out_count – umber outgoing objects
link_number- subsequent number in shadow variable, not creating
by each creating object, but objects which have outgoing links.
In other hand pointers have standard width unlike fat(double)
smartpointers in C++.
Struct shadow is local variable with substructures for each graph
defined locally.
For each graph is stored number of cycles.
Naive approach to cycles: each element in graph 1 is marked with
1, in graph 2 with 2 and so on. If we links from element with 1
to element with 1 – is cycle.
Has disadvantages: If we have millions objects and link from
object with 1 to object with 2, this should be replaced all
millions 2 to 1, And when we remove edge – all in second half
should be renamed from 1 to 2.
Shadow size is near proportional to number of graphs, not graphs
size.
Main routine is link_assign
https://github.com/parstools/smart/blob/7b6b6910dadbb37f1df0b263415d1a1a15b42476/testCpp/dyncycles.cpp#L53
Problems:
- threads, ref_count in shared_ptr in C++ is atomic, but here is
element from and element to
- shadow with both local elements and field elements, if elements
will fields, shadow also must be field, but how do if a.next =b ,
one root is point from fields, second from local?
But for all tested examples is good,
**Is possible proof correctness of this algorithm or find leaks?**
for all possible sets of graphs, with cycles or not, and possible
adding/deleting vertices and edges?
More information about the Digitalmars-d
mailing list