looking for a Btree not recursive implementation, string keys

[legacy]

btree is a complex algorithm, especially if implemented without recursion.
Anyway, I need to search string-keys, that return uint32_t

uint32_t ans=btree_find(string_t key);

let me know about books, papers, or chunks of good C code! 

[brucehoult]

Why would you want to implement it without recursion?

By design, btrees are always balanced, and with typically large branching factors they are not very deep. Therefore there is almost no stack used, but it does make the algorithms simpler.

It's not hard to set some memory aside to use as a fake stack with an on the surface iterative algorithm. But it complicates the code. And, perhaps worse on small computers (and like the processor stack), makes that memory unavailable for other function to use when you're not manipulating the btree.

[legacy]

Why would you want to implement it without recursion?

Design constraint.

[brucehoult]

Why would you want to implement it without recursion?

Design constraint.

Why?

There's no good reason, other than as a school exercise.

Which I guess this must be.

[NorthGuy]

It's not hard to set some memory aside to use as a fake stack with an on the surface iterative algorithm. But it complicates the code. And, perhaps worse on small computers (and like the processor stack), makes that memory unavailable for other function to use when you're not manipulating the btree.

I don't think you need a "fake stack" for tree search. You don't need to walk the whole tree.

You create a variable which represents a node. Let's call it NodeVar. You assign the root to NodeVar. Then you loop. On each pass of the loop you select the node which would contain the element being searched and assign this node to NodeVar. As the next loop comes, it'll be searching within new NodeVar. And so on until the element is found (or not found). So, you only need one variable.

[brucehoult]

It's not hard to set some memory aside to use as a fake stack with an on the surface iterative algorithm. But it complicates the code. And, perhaps worse on small computers (and like the processor stack), makes that memory unavailable for other function to use when you're not manipulating the btree.

I don't think you need a "fake stack" for tree search. You don't need to walk the whole tree.

You create a variable which represents a node. Let's call it NodeVar. You assign the root to NodeVar. Then you loop. On each pass of the loop you select the node which would contain the element being searched and assign this node to NodeVar. As the next loop comes, it'll be searching within new NodeVar. And so on until the element is found (or not found). So, you only need one variable.

For simple search, sure. You can still write it as recursive, but as the recursive call will be a tail-call (you just return its result, without any extra work after the call) any decent compiler will turn that into a loop for you.

It's a different matter if you want to insert the key if you find it is missing.

[legacy]

Why?

There's no good reason, other than as a school exercise.

Which I guess this must be.

Don't be arrogant. In avionic you can't have a stack, sometimes.

[legacy]

I don't think you need a "fake stack" for tree search. You don't need to walk the whole tree.

You create a variable which represents a node. Let's call it NodeVar. You assign the root to NodeVar. Then you loop. On each pass of the loop you select the node which would contain the element being searched and assign this node to NodeVar. As the next loop comes, it'll be searching within new NodeVar. And so on until the element is found (or not found). So, you only need one variable.

yes, good idea! Thanks!

[brucehoult]

Why?

There's no good reason, other than as a school exercise.

Which I guess this must be.

Don't be arrogant. In avionic you can't have a stack, sometimes.

If I have a btree I'd be a million times more worried about running out of dynamic memory (whether heap or disk) than about running out of stack.

More than that, if I know how much dynamic memory is available for the btree, I can calculate and PROVE the maximum stack usage.

[westfw]

I can calculate and PROVE the maximum stack usage.

That doesn't help if you work in an industry with "coding standards" the prohibit recursion :-(
You'd think there would be a repository somewhere of "here are a bunch popular C++/Java/whatever containers and algorithms implemented in a way that meets the requirements set forth by MISRA/NASA/ZYZZY"?  Or is that what the "government computing industry" charges the big bucks for?

Did you really mean BTree?  Most of the stuff I was reading online indicates that they're aimed mainly at disks, and optimized to minimize the number of separate disk accesses.  But I'll admit to being unclear on the subtleties of BTree vs Binary Tree vs Binary Search tree, RB Trees and etc...

[brucehoult]

Did you really mean BTree?  Most of the stuff I was reading online indicates that they're aimed mainly at disks, and optimized to minimize the number of separate disk accesses.  But I'll admit to being unclear on the subtleties of BTree vs Binary Tree vs Binary Search tree, RB Trees and etc...

This 'ere topic (and the first post) says "btree". I took him at his word. Maybe he's confused.

BTrees were originally designed for disk, it's true, but given the way modern CPUs are designed (at least higher end ones with caches and MMUs) they are also better for in-memory use than binary trees. Chasing pointers is cheaper than a disk seek, but it's still a *lot* of CPU cycles if the result has to come from RAM. And TLB misses are very costly, needing usually a number of reads from tables in RAM.

Most programmers have absolutely NO IDEA that even i7 CPUs like Nehalem or Skylake have only 64 or 128 TLB entries, meaning that only that number of 4 KB pages (256KB - 512KB) can be used before you get TLB misses. The ARM processors in most phones have fewer, though not all that much fewer these days ..  for example the Cortex A15 has 32 L1 data TLB entries.

So, once you get a 4 KB page mapped into the TLB it makes sense to use as much information as possible from it, not just a 16 byte (maybe) RB-tree node and then follow a pointer to a different 4 KB page.

The same applies to cache lines. Once you fetched a cache line, it makes sense to look at all of it. Most modern caches are 64 bytes per line, so you should at least make your tree nodes *that* big in some useful way. So, for example, on a 32 bit machine you might put 7 32-bit keys and 8 pointers in each tree node. With standard BTree balancing you should have at least 6 pointers used in every node, so a tree with a million items will be 8 levels deep instead of 20 levels minimum (about 25-28 in practice) for a balanced binary tree. That's a lot less pointer chasing.

[legacy]

This 'ere topic (and the first post) says "btree". I took him at his word. Maybe he's confused.

btree means btree, and I mean btree with the meaning of btree
b+tree is a variant, that I may consider

[legacy]

MISRA/NASA/ZYZZY"

must be DO178C/level_D compliant! (1)
dynamic memory can't be used
recursion can't be used
stack must be checked for its maximal usage in the worse case

reasons don't matter, we have to it that way if we want to get paid 


yes, someone has asked us to have a btree module, tested, and certified. Of course I still have to design it.

edit:
(1) level_D means not critical

[legacy]

Most programmers have absolutely NO IDEA that even i7 CPUs like Nehalem or Skylake have only 64 or 128 TLB entries

There is no data-cache in the final hw.

[legacy]

I don't know really really what is the final purpose, my user-level is classified like if was a guest, in fact I have a pass-level in my badge that doesn't open the toilette's door of the same floor where someone must have done a mistake on allocating my ass to a seat for my desk *IF* I have to go downstairs and my badge only opens the door of the toilette used by visitors 

- Mistakes in desk-allocation are irrelevant - so I was said, and I can believe it since I also have tons of cameras and microphones pointed to my desk and I can't say a blasphemy without being heard by someone with badge. - keep your the language polite, mr P, please! - Thus I consider myself as the same level. And I am a consultant, anyway, not an employed.

I mean, I can't question, I can't do questions, the module I have to write is just a tiny piece of library to the application that runs on the top of the BSP, and details are so unknown that I look like the kind of man who has to look at the keyhole to understand what is in the room beyond to the door! In fact  I have no idea about the system integration, the only information I have to the next piece of software is what I have recently heard some rumors about the final target in the lab: there was a black-box on the table fully covered by resin, with some interfaces that, from the point of view of the documentation , are just a listing of data-types. But, if I got, and if i understand correctly, they want a sort of database to query details on tactical maps.

It's for sure for a flying board something, for an aircraft, but it may be for an Helicopters, or for a space ship. Who knows  ?

Discretion is advised, and it's the promise you did - keep the language polite, and don't do questions if you want to keep your ass on the allocated desk - Not a good affair, but oh, I can stay in Norway for a long time and here Secretaries are all blond pretty pretty girls, and, the air is fresh, and the food is excellent 

[brucehoult]

MISRA/NASA/ZYZZY"

must be DO178C/level_D compliant! (1)
dynamic memory can't be used
recursion can't be used
stack must be checked for its maximal usage in the worse case

reasons don't matter, we have to it that way if we want to get paid 


yes, someone has asked us to have a btree module, tested, and certified. Of course I still have to design it.

Good luck making a btree (or any kind of tree) without dynamic memory.

Sure, you could pre-allocate a bunch of nodes as global/static (or on disk), and then check for running out of them ... but that's no different than checking for malloc() running out of space and returning 0. You're exactly equally fucked in both cases.

[legacy]

oh, another interesting details that I have only recently got says that it must be a "disk-btree" algorithm!

It means you have to access 1Kbyte by some provided API's functions (e.g. disk_read(..), disk_write(..), ..) and you will get 1Kbyte of structure where your BTREE/B+TREE's data must reside.

(btree != b+tree, but I have one degree of freedom, I can change the request into b+tree if it's better)

seeks are assumed << 5mSec, but it down't matter, since now we know that it's a disk-btree! So, we have to consider: pointers to memory, vs disk access, and this changes a bit of things in my previous design draft  (at least the data structure )

The good news is that disk is not an electro-mechanical device, and it's not pATA/sATA, it's a custom solid state device with it's custom protocol, and probably it's made with FeRAM chips, but chips may be flash-chips. Who knows ? 

From a low-level requirement I read that there is also a bit super capacitor able to keep the device powered for enough time to flush data from RAM into the chips. There is a specific interrupt for that, and algorithms must keep flying-datas written onto chips as fast as possible.

Thanks god there is no (not yet?) request for "journaling". Not related to the btree.

But there is a request for a chunk of data that needs to be written into chips collecting information about failures during the missions, warm/cold start, and tons of other information. That is the easiest part, since it doesn't imply btree. It's just a circular buffer!

So, the module I have to prepare is composed by two sub-modules: btree, and circular buffer.

I will reserve the first blocks to the circular buffer, and the rest to the database.

[legacy]

Good luck

don't worry about that, in the worst case I will get fired 
already sent my CV to a company in Norway looking for a guardian of polar bears

(edit: kidding)

[NorthGuy]

Sure, you could pre-allocate a bunch of nodes as global/static (or on disk), and then check for running out of them ...

malloc() is not allowed, but custom-made dynamic allocators as you have just described are Ok? This is certainly a very strange set of rules.

[legacy]

malloc() is not allowed, but custom-made dynamic allocators as you have just described are Ok? This is certainly a very strange set of rules.

good point!

in my draft I am using a custom-made set of allocators.
They need to be approved, anyway 

Code: [Select]

private p_btree_node_t  node_make
(
    p_btree_t p_btree
)
{
    p_btree_node_t p_node_new;

    p_node_new = mem_alloc(sizeof(btree_node_t));
    if (p_node_new isEqualTo NULL)
    {
        panic(module, id, "p_node_new creation");
    }

    p_node_new->is.leaf = false;
    p_node_new->item.n  = 0;
    p_node_new->head    = NULL;
    p_node_new->next    = NULL;
    return p_node_new;
}

"panic" is for the draft version, it will removed/changed into the final version!

[legacy]

Considering the B+tree structure ...

if it wasn't to be disk-B+tree, I would been tempted to do this way

Code: [Select]

typedef struct
{
    uint32_t key;
    map_t map_item; /* custom map's item */
    p_this_t p; /* to leaf or to internal b+tree_node */
} btree_node_item_t;


Code: [Select]

typedef struct
{
    btree_node_item_t it[btree_node_item_N];
    uint32_t          n; /* how many items have been used */
} btree_node_items_t;

the pointer "p" is useful to point to leaf, or to internal nodes
but now I have to consider that the b+tree needs to be loaded and saved from/to a storage device

I wonder if I can change "ram pointers" (uint32_t*) into "(block,sub-block) pointer" (uint32_t,uint32_t)

to do something like this:

disk_read (block_pointer) ---> 1Kbyte of data loaded into ram as "btree_node_items_t"
item = btree_node_item_t it[sub_block_pointer]

does it make sense?

[legacy]

I mean, leaves can also be "packed" that way, so iterating a tree (e.g. full scan or range scan) should be very efficient, because you read hundreds/thousands data-rows per single block 

[Jr460]

It was over 30 years ago, but I had full blown set of Btree code in FORTRAN.   Want no recursion or dynamic memory....   Try FORTRAN-77.   I didn't even think I have a hard copy of it anywhere.  Of course it had some limits, depth of trees for example, based not he compile time size of some arrays.  Since it was used for disk access of files, it also did a bunch of caching of pages.

[asgard20032]

If you need to implement a recursive algorithm without using an hardware stack, thus avoiding recursion, then do a fake recursion implementation. A software stack. Most recursive algorithm can easily be converted to a non recursive algorithm using a software stack (a simple array with a limited length). And you can do check to ensure you never exceed the array length. Also, you can use a counter to make sure it dosen't jam in the algorithm.

[brucehoult]

Sure, you could pre-allocate a bunch of nodes as global/static (or on disk), and then check for running out of them ...

malloc() is not allowed, but custom-made dynamic allocators as you have just described are Ok? This is certainly a very strange set of rules.

Exactly so.

[westfw]

I need to search string-keys, that return uint32_t

Do you need to implement add and delete as well?  Implementing just search without recursion doesn't look too bad.
Hmm.  Do BTrees require a fixed number of keys at each node, or can you fix the size of a node (ie "a disk block") and just cram as many variable-length keys (in the case of a string) in there as will fit?

[legacy]

At the end, I am moving to B+Tree for convenience.

I need to search string-keys, that return uint32_t

Do you need to implement add and delete as well? 

Sure!

Keys (strings) need to
- being inserted
- being deleted
- being queried
- being of fixed size

leaves contain iblock pointers.

Implementing just search without recursion doesn't look too bad.

With B+tree only leaves can contain values, and they each leaf works like a list's item: it points to the parent, and to the next. This is also good when you have to list all the leaves's content, but ... in my case I also need to provide an interactive method to list the content!

Each time you call a function, it must return NULL if no more item in the list, or the next item. I have already designed the "core", but I still need to define details like ... how to do it? 

require a fixed number of keys at each node

yep. Fixed number of keys of fixed size at each node.

[NorthGuy]

Sure!

Keys (strings) need to
- being inserted
- being deleted
- being queried
- being of fixed size

You can do all this without recursion or "fake stack".

What presents a problem is balancing. When you isert, you need to make sure that your tree maintains low depth and doesn't look like linked list instead. Depending on the application, you may not need balancing. If you do need balancing, storing pointers to parents may help to avoid "fake stack" or recursion.

[legacy]

balancing is needed to keep the load of searching as log(N)

[alank2]

Why do B+trees have a pointer in all the leaf nodes stringing them together?

[NorthGuy]

balancing is needed to keep the load of searching as log(N)

If you keep it always perfectly balanced, it is becoming less efficient than a binary search on a sorted array. Therefore, you need to give it some slack. Depending on the specific situation, it may be the best not to do balancing at all, do a little bit of a balancing, or do a lot of balancing. This is more art than science.

[brucehoult]

Why do B+trees have a pointer in all the leaf nodes stringing them together?

So you can visit every data item sequentially without bothering your pretty head keeping a stack of index nodes.

Waste of disk space (and program code to maintain the pointer) if you ask me, unless you have so little RAM you can't keep one or two index nodes in memory at the same time as a leaf node.

[grumpydoc]

Sure, you could pre-allocate a bunch of nodes as global/static (or on disk), and then check for running out of them ...

malloc() is not allowed, but custom-made dynamic allocators as you have just described are Ok? This is certainly a very strange set of rules.

Exactly so.

It's not totally mad - code often gets written as though malloc() and friends cannot fail. On larger systems this might not be unreasonable (for various reasons) but in an embedded system with limited resources (and no swap file) it is more likely and the consequences of not handling it gracefully might be more serious.

Pre-allocating and drawing from a pool of fixed-size/fixed-use objects makes it more obvious to the programmer that the resource is finite and more likely that the code will handle running out of that resource gracefully.

It also compartmentalises the issue so one bit of functionality running out of resource does not necessarily stop other system functions.

[legacy]

Code: [Select]

p: populate the btree with {0..19} keys
i: insert a coin and value (value = coin)
f: find the value associated with a coin
d: delete a coin and its associated value
l: show coins of the leaves
> p
> l
0 1 2 3 4  | 5 6 7 8 9  | 10 11 12 13 14  | 15 16 17 18 19
> f 9
btree_coin_find_leaf: [[5 10 15 ]] 1 -> Leaf [5 6 7 8 9 -> Record
coin 9, value 9.
> d 9
btree_coin_find_leaf: [[5 10 15 ]] 1 -> Leaf [5 6 7 8 9 -> Record
> l
0 1 2 3 4 5 6 7 8  | 10 11 12 13 14  | 15 16 17 18 19

The first (demo) draft version 

[legacy]

I am using integer-coins for simplicity, I will replace methods for string-coins 

First step: replace pointers to memory, with pointers to disk's block.

[alank2]

So you can visit every data item sequentially without bothering your pretty head keeping a stack of index nodes.
Waste of disk space (and program code to maintain the pointer) if you ask me, unless you have so little RAM you can't keep one or two index nodes in memory at the same time as a leaf node.

I agree; I don't see the logic in it at all.  Just seems like another pointer to have to maintain with very little payoff.  You built the tree to navigate the list, just use it.

[legacy]

it may be the best not to do balancing at all, do a little bit of a balancing, or do a lot of balancing. This is more art than science.

Yup, I have designed the core of the library in a way there are chances to tune it on specific needs. I haven't already got any more constraints from my customer, so I have to be generic at this step, in fact in the above demo there is a sub-optimal balancing-algorithm, doing just a little bit of a balancing 

[legacy]

You built the tree to navigate the list, just use it.

the "next" field is useful for the iterator!

You call the item_get function, and this function read a leaf node, and get the next value available if it's available, if not ... it points to the NEXT leaf.

NODE0 (leaves) --next--> NODE1 (leaves) --next--> NULL

Navigating the whole tree by internal nodes ( != leaves ) requires MORE steps ( = more seeks ) and it's also more complex to be implemented in a sort of interactive way.


In my DEMO, every items listing is performed by a loop

Code: [Select]

done = btree_leaves_list_init(p_btree);
while (done isEqualTo False)
{
    is_done = btree_leaves_list_item_get(p_btree);
    btree_leaves_list_item_show(p_btree);
}

e.g. leaves list

Code: [Select]

> l
0 1 2 3 4 5 6 7 8 9 | 10 11 12 13 14  | 15 16 17 18 19


[brucehoult]

You built the tree to navigate the list, just use it.

the "next" field is useful for the iterator!

You call the item_get function, and this function read a leaf node, and get the next value available if it's available, if not ... it points to the NEXT leaf.

NODE0 (leaves) --next--> NODE1 (leaves) --next--> NULL

Navigating the whole tree by internal nodes ( != leaves ) requires MORE steps ( = more seeks ) and it's also more complex to be implemented in a sort of interactive way.

Assuming your internal nodes have about 100 keys/pointers in them (e.g. 32 byte keys and 8 byte pointers in a 4 KB node), it's only about 1% MORE seeks. You'd struggle to notice it.

[legacy]

but nodes need to rewritten to have string-coins (keys) of 100 chars each, and a disk block size is 1Kbyte.

Not so many, in the final code 

[rhb]

It sounds to me as if the actual requirement is fast table search in a provably bounded time.  This has then been translated into "build us a btree" by a PHB  who doesn't understand the impact of the other  rules but has heard of btrees.

Consider using a linked list implemented as a table  of compile time defined size and  use a binary search.  You can give a hard real time bound on access and an error return if data exceeds the size of the linked list.  This provides a provably correct mechanism that cannot fail without a clear error condition.

The requirement not to use dynamic memory makes a great deal of sense in an embedded environment.  Especially if the "btree" is being used for a "would be nice" feature and is part of a "must work correctly" system such as the control system for an airplane.

[legacy]

Especially if the "btree" is being used for a "would be nice" feature and is part of a "must work correctly" system such as the control system for an airplane.

must work correctly, but "must" is under the Level D definition, i.e. if it fails nobody dies, just the mission is failed 

A level-A (usually involved with supersonic fly boards, i.e. Mach 1, Mach 2, etc military airplanes) would be much more critical, since if it fails people dies and the mission is of course failed and this level of failure may drag you under a kind of martial court, and being fired from the job is the last of your problems. But my user-level is not enough classified to give an eye, thus I don't worry too much. Oh, and a Level-A badge has access to every toilette in every floor of the building as well as a free unlimited access to the topgun coffee machines, whose quality is really the topgun and the choice include Decaffeinated, Not Decaffeinated, coffee + milk, coffee + chocolate, etc, and unlimited free access to the swimming pool; while with my shitty level-D ... the coffee is offered by a shitty coffee machine with a coin of 0.50E per cup, you have only two choices (Decaffeinated, Not Decaffeinated), and accessing the swimming pool is rather giving them an eye and a leg in daily payment, plus the only toilette I can open with the badge is located downstairs.

That means: I don't worry too much on the strategy/whatever, they (PHP-badged guys) can have what they ask and pay, it's not my responsibility, otherwise I want a level-B/level-A badge! 

[legacy]

Consider using a linked list implemented as a table  of compile time defined size and  use a binary search.  You can give a hard real time bound on access and an error return if data exceeds the size of the linked list.  This provides a provably correct mechanism that cannot fail without a clear error condition.

I can try to offer them an alternative solution, but ... I am afraid of the their reaction, since they would be happy to make me also acquiring the responsibility of the design, which is ... huge an unpaid hazard, and I don't want to say that I am so good at software designing 

[legacy]

table  of compile time

ummm, there is an hidden constraint that sounds of run-time. May be they want to be able to update their mission's maps on demand during the mission(1). I haven't got told directly, but I see a note about a radio-link that can access the FeRAM disk to write new data chunk. Thus the B+tree request might make sense 

(1) I have to sign the code, as well as I have to sign the test report, but if my algorithm fails then the map is corrupted, and this may compromise the mission. This map is not related to fly map, thus there is no probability to cause a disaster in term of an airplane that crashes due to a software bug. In the worst case the pilot has to turn the plane on its tail and return home. Of course someone may be angry with me and asking me to pay the fuel, which is not so cheap as car's petrol (but I have an insurance for that).

[rhb]

Mmmm. Forgive my saying this, but perhaps you should be doing something else.

The reason that recursive routines and dynamic memory allocation are proscribed is that the run time behavior is unpredictable.  An error in a calling routine can cause resource exhaustion.  A table based linked list of predetermined size either works or says to the caller, "table full".  Unit test validation is easy to write.

If you can't write a linked list table using bisection search you need to get a copy of Sedgewick or the MIT algorithm book and read it cover to cover before the start of the new year.  I can't tell you any details about B-trees.  I have never had an occasion to need to use one.  But I have the references and can come up to speed in a few days at most.  That is what professional programming is about.  Anything less is sub-standard.  You don't need to know anything off the top of your head.  But you do need to be sufficiently familiar with all aspects of the field and have the references so that you can come up to speed in a few days.

An important aspect of professional programming is being able to translate a vague or garbled requirement into a proper specification.  It is not the users responsibility to do this.  It is the programmer's.  "Oh, you want wheels with your car?  We can do that.  You want a steering wheel and brake?  We can do that too, but we'll have to slip the schedule a bit and it will cost extra."  The programmer's job is to translate between human beings and machines.

FWIW I did a port of 500,000 lines of VAX FORTRAN code from VMS to Unix in the early 90's.  At the suggestion of another contractor on the project, I built a regression test facility.  Every time we wrote a new module we wrote a basic test suite for it.  Every time we found a bug in the old code, we wrote a test for it.  Every build ran hundreds of test cases and compared thousands of output files.  This package was used by affiliates of a major oil company all over the world.  After the first year I was tasked with writing up the release notes for an enhanced version.  We had fewer than a dozen user submitted bug reports.  It went down from there.  There were lots of bugs, but they did not get out the door.  We found them first.  After a merger the code ran completely unsupported for another 10-15 years.  It finally went off line when there was no longer any need for the functionality.  There were a couple of 15,000 line libraries which I wrote  which never needed any maintenance except when Sun Microsystems broke getcwd(3c) and did not set errno correctly.  So the logic was changed to check if the string returned was null instead of checking errno.  The really cool code was a set of C routines called from FORTRAN which parsed user defined input.  It built a table of function pointers on the first call.  After that it simply executed the table of functions.  This got us a 6x speed up, which for input files with millions of lines of ASCII text was a huge improvement.   I sweated bullets over that code because if I got it wrong it would have been hell to debug.  It worked perfectly.  Of all the work I've done, that project is the thing I am most proud of.  Very few people can claim that level of reliability in their code.

[westfw]

If you can't write a linked list table using bisection search...
An important aspect of professional programming is being able to translate a vague or garbled requirement into a proper specification.

I don't think "can't" is the problem, and I don't think the requirement was either "vague" or "garbled."  It was "write some B-tree code that meets our coding standards."  Now, that may have been an inappropriate level of detail from the "user", but I think you're talking about an industry with many layers of bureaucracy and I doubt that the "programmer" gets to change the requirement.   It was probably set by some "systems engineer", "data analyst" or "scientist" and handed down, like in the old days...

[rhb]

If you can't write a linked list table using bisection search...
An important aspect of professional programming is being able to translate a vague or garbled requirement into a proper specification.

I don't think "can't" is the problem, and I don't think the requirement was either "vague" or "garbled."  It was "write some B-tree code that meets our coding standards."  Now, that may have been an inappropriate level of detail from the "user", but I think you're talking about an industry with many layers of bureaucracy and I doubt that the "programmer" gets to change the requirement.   It was probably set by some "systems engineer", "data analyst" or "scientist" and handed down, like in the old days...

I always managed to change the requirement if such an issue came up.  I simply quoted chapter and verse until everyone's  eyes glazed over. However, you *do* have to be able to explain the conflicting requirement in excruciating detail to at the level of a 5th grader.  I did have one fool who pounded on the table and screamed at me in a meeting when I did this.  Everyone was quite shocked.  I just sat there.  He did get his way, but the application was a failure and was discarded a few months later after a merger.  I learned from industry friends that the acquiring company  kept the scientific libraries I wrote, but junked the rest.

However, I am an outlier as my training was as a scientist.  Programming was just something I picked up because I needed to be able to do it.  So I was on the same level as the senior scientists in the application domain.  And much more knowledgeable in the CS domain.

It comes down to  simply this.  If someone requests dry water, you are obligated to explain why that's not possible.  And do so before you start work, not 6 months later.

[NorthGuy]

I always managed to change the requirement if such an issue came up.

I just sat there.  He did get his way ...

These two statements contradict each other

[legacy]

I doubt that the "programmer" gets to change the requirement.   It was probably set by some "systems engineer", "data analyst" or "scientist" and handed down, like in the old days...

Yes, as "programmer" with a Level-C badge I can neither do criticism. I am an executor. The only things they accept is a note for some requirements that are not clear (and I have to say "they are not clear TO me, can't say they are wrong or too vague).

I know that part of the design comes from someone with an higher user-level than me, i.g.  "systems engineer", "data analyst", "scientist" ... who knows? I can't interface directly with them, from my console their comments are not catch directly, I only get echos from the information propagation  - from my question, to the answer - through the rigid hierarchy, and it's always a one-way divine revelation  from outer space entities with a god certificate.

Anyway, my email can't physically reach their server because even the internal lan needs a user-level to operate. I can interface only to a guy in the middle, who will interface with someone higher than me in the hierarchy, who will interface to someone higher in the hierarchy, .... until someone who has a user-level badget that allows him to enter into the divine circle of those who do "the design"!

The development chain follows the command chain, thus it is unable to bend or be forced out of shape. Not flexible, and forget democracy. Someone gives orders, and you have to obey. Someone gives requirements, and you have to code.

I usually don't know more details than how many they want to give (usually ... a few, and it's not useful to do your job, but you can't question), I only know that they use the tool "Stood" as support for AADL design, and this tool uses Ada and artificial intelligence that implies tons of statistical data used in the process