Re: id management algorithm

From: Karthik Gurusamy (kar1107_at_gmail.com)
Date: 12/01/04 

Date: 1 Dec 2004 13:02:20 -0800

>
> Does this sound practical?

Yes, it is a neat solution. The stack size is guaranteed to be utmost
the largest sequence of continous deletions starting from the latest operation.
This number is going to be very few.And a simple singly linked list can be
used for the stack.

In fact the tree based approach has the drawback of finding a free id.
(How to find a hold in the id space even when we remember the ids in use?)

The other approaches suggested like using the memory address (C pointer) will
also work; but it is using an opaque handle of memory manager for other purposes.

Thanks,
Karthik

"Wavemaker" <jabberdabber@BiteMeHotmail.com> wrote in message news:<QfCdnQvvXrPDiTDcRVn-qA@comcast.com>...
> "Karthik Gurusamy" wrote:
> > Hi,
> >
> > I need to manage a large collection of items. Lets say I use
> > an AVL tree ADT to manage the items. Additions, deletions and search
> > are common operations.
> >
> > At any give time the number of items is less than a billion - so a 32
> > bit unsigned int can hold the number of items. But the number of
> > additions/deletions over the life time of the ADT can well go beyond
> > several billions.
> >
> > To reference an item, I need to assign a unique ID. Lets say we use 32
> > bit id.
> >
> > What could be a low overhead id manager algorithm? overhead in terms
> > of time and space. A straightforward approach is for the id manager to
> > start doling out ids starting from zero and remembering each id in a
> > log N search/add/del datastructure (say avl). But the downside is the
> > memory usage. Considering the only operations are 1) allocate an id 2)
> > free an id is there any better solution? or can we say it can't be
> > done better theoretically?
>
> Instead of an id manager remembering each id, it remembers only the last
> id handed out and the ones that once belonged to items that have been
> deleted; it would store these in a stack. The algorithm would go
> something like this:
>
> For each new item added to the tree.
> - Check a stack to see if there are any old ids available.
> - If yes, pop an id off the stack and give it to the
> new item.
> - Else if no, increment the current id value and give
> that to the new item.
> - Insert item into tree.
>
> For each item deleted from the tree.
> - Retrieve its id.
> - Push id onto a stack.
> - Delete item from tree.
>
> Does this sound practical?

Relevant Pages

  • Re: Self-join question
    ... There are many ways to represent a tree or hierarchy in SQL. ... CREATE TABLE OrgChart ... rgt INTEGER NOT NULL UNIQUE CHECK, ... Here is version with a stack in SQL/PSM. ...
    (microsoft.public.sqlserver.programming)
  • Re: CTE and children count
    ... lft INTEGER NOT NULL UNIQUE CHECK, ... rgt INTEGER NOT NULL UNIQUE CHECK, ... To show a tree as nested sets, replace the nodes with ovals, and then ... Here is version with a stack in SQL/PSM. ...
    (microsoft.public.sqlserver.programming)
  • Re: Stored Proc to Call Same stored proc
    ... Look up the Nested Sets model and avoid procedural code completely. ... There are many ways to represent a tree or hierarchy in SQL. ... lft INTEGER NOT NULL UNIQUE CHECK, ... Here is version with a stack in SQL/PSM. ...
    (microsoft.public.sqlserver.programming)
  • Re: deep list recursion
    ... on system stack usage, it's worthwhile to use the heap instead. ... Now, since we're building a new tree, when we're processing a leaf on ... track the structure of the tree to know how to cons them. ... (define (map-tree-i fun tree stack result) ...
    (comp.lang.scheme)
  • [patch] i386: restore ESP value on return to userspace
    ... exporting the high word of kernel's stack ... Attached patch checks if the userspace ... then kernel switches to the "small" ... done against the Linus tree and/or -mm tree. ...
    (Linux-Kernel)