1

Q: How to programmatically increment several numeric keys of a hash-table.

Background:

I am working on a modificion of speedbar to support the concept of speedbar-get-marked-files -- speedbar -- mark/unmark directories/files -- `speedbar-get-marked-files` I have setup a hash-table that consists of buffer line numbers for the keys, and the values are absolute filenames or directories.

When clicking on a + sign to expand directories, speedbar inserts additional files and directories underneath the expanded node. It is at this point that the hash-table needs to be modified, since puthash replaces existing entries. Programmatically, I already know how many new lines will be inserted.

Example:

A buffer contains 9 lines (in this case all directories), with a corresponding hash-table.

1  "/usr/"
2  "/usr/bin"
3  "/usr/include"
4  "/usr/lib"
5  "/usr/libexec"
6  "/usr/local"
7  "/usr/man"
8  "/usr/sbin"
9  "/usr/share"

We click on the expandable directory /usr/lib and programmatically we know that 8 new directories and 27 new files will be inserted. Therefore, a total of 35 new lines will be added underneath line 4 -- the previous hash-table entries of 5, 6, 7, 8 and 9 all need to be renumbered by adding 35 to each one. The new hash-table should become:

1  "/usr/"
2  "/usr/bin"
3  "/usr/include"
4  "/usr/lib"
40  "/usr/libexec"
41  "/usr/local"
42  "/usr/man"
43  "/usr/sbin"
44  "/usr/share"
3
  • 2
    Hash table entries aren't in any defined order, so "previous" entries is kind of meaningless. Maybe hash tables are the wrong data structure for this? – npostavs Jul 12 '15 at 17:34
  • @npostavs -- Thank you for helping me understand that hash-table entries are not in any particular order. I still need to please learn how to programmatically efficiently change 5 to 40, 6 to 41, 7 to 42, 8 to 43, and 9 to 44. The data structure is used by a different major-mode that is analogous to several components of speedbar, and I'm already familiar with how to obtain the line number if I know the absolute filename, and how to obtain the absolute filename if I know the line number. I would prefer not relying upon querying text-properties to obtain the line number or filename. – lawlist Jul 12 '15 at 17:54
  • Sounds like want you need is an array, no renumbering needed. – politza Jul 12 '15 at 21:25
1

If you know the top index, and you know that the indices are consecutive it might be more efficient to loop over those specific indices:

(let ((table #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data
                           (1 "/usr/" 2 "/usr/bin" 3 "/usr/include" 4 "/usr/lib" 5 "/usr/libexec"
                              6 "/usr/local" 7 "/usr/man" 8 "/usr/sbin" 9 "/usr/share")))
      (lo 5)
      (hi 9)
      (inc 35))
  (if (cl-plusp inc)
      (cl-loop for i from hi downto lo
               do (puthash (+ i inc) (gethash i table) table))
    (cl-loop for i from lo upto hi
             do (puthash (+ i inc) (gethash i table) table))))
 ;; assuming 5..34 are set later
2
  • 1
    I'm not sure if this can happen in OP's case, but in general, consider the situation when lo + inc = some key in the hash-table, in that case you'd overwrite it, but it is also possible that at the same time lo + inc < hi, in which case you are meant to keep it. (This is a famous problem with memmove, one that started a flame war between Linux Kernel devs and GCC devs). – wvxvw Jul 12 '15 at 21:47
  • @wvxvw: oops, very good point, and I believe it does apply to OP's case (suppose /usr/lib contains only 1 file). Updated to handle this. – npostavs Jul 13 '15 at 7:49
3

As npostavs said, it would probably make more sense to use another datastructure, perhaps a B-tree or some other kind of tree, where you wouldn't need to do massive insert / remove operations. Below, however, is a simple example of how one can go about doing this while still using a hash-table:

(let ((example (make-hash-table))
      (offset 5)
      (increment 3))
  (cl-loop for i below 10 do (puthash i (format "value: %d" i) example))
  (cl-loop for k being the hash-keys of example using (hash-values v) do
           (message "before %s => %s" k v))
  (cl-loop for (k . v) in
           (cl-loop for k being the hash-keys of example using (hash-values v)
                    when (> k offset) do
                    (remhash k example)
                    and collect (cons k v))
           do (puthash (+ k increment) v example))
  (cl-loop for k being the hash-keys of example using (hash-values v) do
           (message "after %s => %s" k v)))

;; before 0 => value: 0
;; before 1 => value: 1
;; before 2 => value: 2
;; before 3 => value: 3
;; before 4 => value: 4
;; before 5 => value: 5
;; before 6 => value: 6
;; before 7 => value: 7
;; before 8 => value: 8
;; before 9 => value: 9

;; after 0 => value: 0
;; after 1 => value: 1
;; after 2 => value: 2
;; after 3 => value: 3
;; after 4 => value: 4
;; after 5 => value: 5
;; after 12 => value: 9
;; after 11 => value: 8
;; after 10 => value: 7
;; after 9 => value: 6

Note that there's a caveat: if you increase the key in the same loop, you may accidentally overwrite the value with higher key value.

1
  • All three (3) answers work, but I could only choose one. I will continue to study your example to eventually understand what makes it tick -- it's got a few components that are beyond my present level. I'll review and work on it in my spare time. As always, your help is greatly appreciated! – lawlist Jul 12 '15 at 20:32
0
(let* ((current-line (line-number-at-pos))
       (increment 35)
       (copied-line-to-node-table (copy-hash-table speedbar-line-to-node-table))
       (copied-node-to-line-table (copy-hash-table speedbar-node-to-line-table)))
  (maphash
    (lambda (line filename)
      (when (> line current-line)
        (puthash (+ line increment) filename speedbar-line-to-node-table)))
    copied-line-to-node-table)
  (maphash
    (lambda (filename line)
      (when (> line current-line)
        (puthash filename (+ line increment) speedbar-node-to-line-table)))
    copied-node-to-line-table))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.